Jalur optimal melalui matriks

19

Diberikan matriks yang terdiri dari bilangan bulat positif, output jalan dengan jumlah terendah ketika melintasi dari elemen kiri atas ke kanan bawah. Anda dapat bergerak secara vertikal, horizontal dan diagonal. Perhatikan bahwa mungkin untuk bergerak ke atas / bawah, kanan / kiri dan diagonal ke semua sisi.

Contoh:

 1*   9    7    3   10    2    2
10    4*   1*   1*   1*   7    8
 3    6    3    8    9    5*   7
 8   10    2    5    2    1*   4
 5    1    1    3    6    7    9*

Jalur yang memberikan jumlah terendah ditandai dengan tanda bintang, dan menghasilkan jumlah berikut: 1 + 4 + 1 + 1 + 1 + 5 + 1 + 9 = 23 .

Kasus uji:

1   1   1
1   1   1
Output: 3

 7    9    6    6    4
 6    5    9    1    6
10    7   10    4    3
 4    2    2    3    7
 9    2    7    9    4
Output: 28

2  42   6   4   1
3  33   1   1   1
4  21   7  59   1
1   7   6  49   1
1   9   2  39   1
Output: 27 (2+3+4+7+7+1+1+1+1)

 5    6    7    4    4
12   12   25   25   25
 9    4   25    9    5
 7    4   25    1   12
 4    4    4    4    4
Output: 34 (5+12+4+4+4+1+4)

1   1   1   1
9   9   9   1
1   9   9   9
1   9   9   9
1   1   1   1
Output: 15

 2   55    5    3    1    1    4    1
 2   56    1   99   99   99   99    5
 3   57    5    2    2    2   99    1
 3   58    4    2    8    1   99    2
 4   65   66   67   68    3   99    3
 2    5    4    3    3    4   99    5
75   76   77   78   79   80   81    2
 5    4    5    1    1    3    3    2
Output: 67 (2+2+3+3+4+5+4+3+3+3+1+2+2+1+3+1+1+4+5+1+2+3+5+2+2)

Ini adalah sehingga kode terpendek dalam setiap bahasa menang.

Stewie Griffin
sumber
Sangat mirip , meskipun tidak memungkinkan gerakan diagonal.
Mego
7
@WheatWizard saya tidak setuju. Terlepas dari perbedaan yang sebagian besar dangkal bahwa tantangan ini memungkinkan untuk pergerakan diagonal dan semua posisi dapat dicapai, tantangan lain membutuhkan pengembalian jalan itu sendiri daripada hanya biaya jalan. Kecuali Anda menggunakan built-in yang mengembalikan keduanya, kode tidak dapat dipertukarkan.
gelas kimia
@ speaker Saya tidak benar-benar melihat perbedaannya. Anda harus menemukan jalan untuk mengetahui panjangnya. Perbedaannya di sini adalah perbedaan yang agak kecil dalam output menurut saya dan tantangan ini tidak menawarkan sesuatu yang baru atau menarik yang belum tercakup oleh tantangan itu.
Wheat Wizard
1
@WheatWizard Solusi saya di sini tidak menemukan jalan. Itu bisa menemukan jalan, tetapi bukan tanpa array dan logika pendahulu yang terpisah untuk menghindari membuat node pendahulunya sendiri. Belum lagi memulihkan jalur di akhir.
Gelas
@ speaker Modifikasi agak sepele menurut saya. Terlepas dari pertanyaan dupes bukan apakah setiap entri yang valid pada satu tantangan dapat porting dengan upaya minimal, ini tentang kasus umum. Saya tidak hanya berpikir bahwa sebagian besar upaya di sini dapat diangkut. Saya tidak berpikir tantangan ini menawarkan sesuatu yang baru atau menarik dari yang lain.
Wheat Wizard

Jawaban:

8

JavaScript, 442 412 408 358 byte

Ini adalah pengiriman PPCG pertama saya. Umpan balik akan sangat dihargai.

(m,h=m.length,w=m[0].length)=>{for(i=0;i<h*w;i++)for(x=0;x<w;x++){for(y=0;y<h;y++){if(m[y][x]%1==0)m[y][x]={c:m[y][x],t:m[y][x]};for(X=-1;X<=1;X++)for(Y=-1;Y<=1;Y++){t=x+X;v=y+Y;if((X==0&&Y==0)||t<0||t>=w||v<0||v>=h)continue;if(m[v][t]%1==0)m[v][t]={c:m[v][t],t:null};c=m[y][x].t+m[v][t].c;if (c<m[v][t].t||m[v][t].t==null)m[v][t].t=c}}}return m[h-1][w-1].t}

Ini membutuhkan array multi dimensi sebagai input.

Penjelasan

Pada dasarnya, loop melalui semua sel berulang-ulang menyesuaikan biaya terendah yang diketahui untuk sampai ke masing-masing tetangga. Akhirnya, grid akan mencapai keadaan di mana total biaya untuk mencapai bagian kanan bawah adalah biaya terendah untuk sampai ke sana.

Demo

f=(m,h=m.length,w=m[0].length)=>{for(i=0;i<h*w;i++)for(x=0;x<w;x++){for(y=0;y<h;y++){if(m[y][x]%1==0)m[y][x]={c:m[y][x],t:m[y][x]};for(X=-1;X<=1;X++)for(Y=-1;Y<=1;Y++){t=x+X;v=y+Y;if((X==0&&Y==0)||t<0||t>=w||v<0||v>=h)continue;if(m[v][t]%1==0)m[v][t]={c:m[v][t],t:null};c=m[y][x].t+m[v][t].c;if (c<m[v][t].t||m[v][t].t==null)m[v][t].t=c}}}return m[h-1][w-1].t}

//Tests
console.log(f([[1,1,1],[1,1,1]])===3);
console.log(f([[7,9,6,6,4],[6,5,9,1,6],[10,7,10,4,3],[4,2,2,3,7],[9,2,7,9,4]])===28);
console.log(f([[2,42,6,4,1],[3,33,1,1,1],[4,21,7,59,1],[1,7,6,49,1],[1,9,2,39,1]])===27);
console.log(f([[5,6,7,4,4],[12,12,25,25,25],[9,4,25,9,5],[7,4,25,1,12],[4,4,4,4,4]])===34); 
console.log(f([[1,1,1,1],[9,9,9,1],[1,9,9,9],[1,9,9,9],[1,1,1,1]])===15)
console.log(f([[2,55,5,3,1,1,4,1],[2,56,1,99,99,99,99,5],[3,57,5,2,2,2,99,1],[3,58,4,2,8,1,99,2],[4,65,66,67,68,3,99,3],[2,5,4,3,3,4,99,5],[75,76,77,78,79,80,81,2],[5,4,5,1,1,3,3,2]])===67);

Sunting: Terima kasih khusus kepada @ETHproductions karena membantu saya mencukur lusinan byte lezat.

Terima kasih lagi kepada @Stewie Griffin untuk tips Anda yang membuat 50 byte.

Benjamin Cuningham
sumber
3
Selamat datang di PPCG! Ada beberapa ruang ekstra yang dapat Anda hapus menjelang akhir (saya hitung 5 total), dan Anda tidak memerlukan titik koma langsung sebelum }yang menyimpan beberapa byte. Anda juga tidak perlu mendeklarasikan variabel Anda; Saya pikir menghapus vars akan menghemat total 24 byte lebih.
ETHproduksi
2
Selamat datang di PPCG =) Saya senang Anda memilih salah satu tantangan saya sebagai titik awal. Satu-satunya komentar saya: Saya suka penjelasan. Ini opsional, jadi Anda tidak perlu menambahkannya kecuali Anda mau. :)
Stewie Griffin
Saya pikir mungkin menyimpan m[v][t]sebagai variabel: t=x+X;v=y+Y;k=m[v][t]akan lebih pendek ...?
Stewie Griffin
7

Python 3 + numpy + scipy , 239 222 186 byte

from numpy import*
from scipy.sparse.csgraph import*
def f(M):m,n=s=M.shape;x,y=indices(s);return dijkstra([(M*(abs(i//n-x)<2)*(abs(i%n-y)<2)).flatten()for i in range(m*n)])[0,-1]+M[0,0]

Cobalah online!

notjagan
sumber
6

Paket Octave + Image Processing, 175 162 157 151 142 139 byte

Disimpan 14 byte berkat @Luis Mendo dan 1 byte terima kasih ke @notjagan

function P(G)A=inf(z=size(G));A(1)=G(1);for k=G(:)'B=im2col(padarray(A,[1,1],inf),[3,3])+G(:)';B(5,:)-=G(:)';A=reshape(min(B),z);end,A(end)

Menggunakan paket Pemrosesan Gambar, karena mengapa tidak? Bukankah begitu bagaimana semua orang memecahkan masalah grafik?

Cobalah online!

Meledak

function P(G)
   A=inf(z=size(G));         % Initialize distance array to all Inf
   A(1)=G(1);                % Make A(1) = cost of start cell
   for k=G(:)'               % For a really long time...
      B=im2col(padarray(A,[1,1],inf),[3,3])+G(:)';
       %  B=padarray(A,[1,1],inf);     % Add border of Inf around distance array
       %  B=im2col(B,[3,3]);           % Turn each 3x3 neighborhood into a column
       %  B=B+G(:)';                   % Add the weights to each row
      B(5,:)-=G(:)';         % Subtract the weights from center of neighborhood
      A=reshape(min(B),z);   % Take minimum columnwise and reshape to original
   end
   A(end)                    % Display cost of getting to last cell

Penjelasan

Diberikan sejumlah bobot:

7   12    6    2    4
5   13    3   11    1
4    7    2    9    3
4    2   12   13    4
9    2    7    9    4

Inisialisasi array biaya sehingga biaya untuk mencapai setiap elemen adalah Infinity, kecuali titik awal (elemen kiri atas) yang harganya sama dengan bobotnya.

  7   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

Ini adalah iterasi 0. Untuk setiap iterasi berikutnya, biaya untuk mencapai sel ditetapkan ke minimum:

  • biaya saat ini untuk mencapai elemen itu, dan
  • biaya saat ini untuk mencapai tetangga elemen + berat elemen

Setelah iterasi pertama, biaya path ke elemen (2,2) (menggunakan indeks berbasis 1) akan menjadi

minimum([  7   Inf   Inf]   [13  13  13]) = 20
        [Inf   Inf   Inf] + [13   0  13]
        [Inf   Inf   Inf]   [13  13  13]

Array biaya penuh setelah iterasi pertama adalah:

  7    19   Inf   Inf   Inf
 12    20   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

Setelah iterasi k, setiap elemen akan menjadi biaya terendah untuk mencapai elemen itu sejak awal mengambil klangkah paling banyak . Misalnya, elemen di (3,3) dapat dicapai dalam 2 langkah (iterasi) dengan biaya 22:

  7    19    25   Inf   Inf
 12    20    22   Inf   Inf
 16    19    22   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

Tetapi pada iterasi ke-4, jalur 4 langkah ditemukan dengan biaya 20:

 7   19   25   24   28
12   20   22   32   25
16   19   20   30   34
20   18   30   34   35
27   20   25   40   39

Karena tidak ada jalur melalui matriks mxn bisa lebih panjang dari jumlah elemen dalam matriks (sebagai batas atas yang sangat longgar), setelah m*niterasi setiap elemen akan mengandung biaya jalur terpendek untuk mencapai elemen tersebut dari awal.

gelas kimia
sumber
-1 byte dengan menghapus spasi antara whiledan ~.
notjagan
@ notjagan saya beralih dari whileke fordan masih bisa menggunakan tip Anda. Terima kasih!
Gelas
5

JavaScript, 197 byte

a=>(v=a.map(x=>x.map(_=>1/0)),v[0][0]=a[0][0],q=[...(a+'')].map(_=>v=v.map((l,y)=>l.map((c,x)=>Math.min(c,...[...'012345678'].map(c=>a[y][x]+((v[y+(c/3|0)-1]||[])[x+c%3-1]||1/0)))))),v.pop().pop())

Mendandani:

a=>(
  // v is a matrix holds minimal distance to the left top
  v=a.map(x=>x.map(_=>1/0)),
  v[0][0]=a[0][0],
  q=[
     // iterate more than width * height times to ensure the answer is correct
    ...(a+'')
  ].map(_=>
    v=v.map((l,y)=>
      l.map((c,x)=>
        // update each cell
        Math.min(c,...[...'012345678'].map(
          c=>a[y][x]+((v[y+(c/3|0)-1]||[])[x+c%3-1]||1/0)
        ))
      )
    )
  ),
  // get result at right bottom
  v.pop().pop()
)
tsh
sumber
4

Mathematica 279 Bytes

Ide dasarnya adalah membuat grafik dengan simpul yang sesuai dengan entri matriks dan tepi terarah antara dua simpul yang dipisahkan oleh ChessboardDistancelebih besar dari nol tetapi kurang dari atau sama dengan 1. Kebetulan, ini dikenal sebagai grafik Raja , karena sesuai dengan langkah sah seorang raja di papan catur.

FindShortestPathini kemudian digunakan untuk mendapatkan jalur minimal. Ini berfungsi EdgeWeight, tidak VertexWeight, jadi ada beberapa kode tambahan untuk didefinisikan EdgeWeightsebagai entri matriks yang sesuai dengan tujuan setiap tepi yang diarahkan.

Kode:

(m=Flatten[#];d=Dimensions@#;s=Range[Times@@d];e=Select[Tuples[s,2],0<ChessboardDistance@@(#/.Thread[s->({Ceiling[#/d[[1]]],Mod[#,d[[1]],1]}&/@s)])≤1&];Tr[FindShortestPath[Graph[s,#[[1]]->#[[2]]&/@e,EdgeWeight->(Last@#&/@Map[Extract[m,#]&,e,{2}])],1,Last@s]/.Thread[s->m]])&

Perhatikan bahwa karakter adalah simbol transpose. Ini akan menempel ke Mathematica apa adanya.

Pemakaian:

%@{{2, 55, 5, 3, 1, 1, 4, 1},
  {2, 56, 1, 99, 99, 99, 99, 5},
  {3, 57, 5, 2, 2, 2, 99, 1},
  {3, 58, 4, 2, 8, 1, 99, 2},
  {4, 65, 66, 67, 68, 3, 99, 3},
  {2, 5, 4, 3, 3, 4, 99, 5},
  {75, 76, 77, 78, 79, 80, 81, 2},
  {5, 4, 5, 1, 1, 3, 3, 2}}

Keluaran:

67

Jika Anda mengatur g=Graph[...,GraphLayout->{"GridEmbedding","Dimension"->d},VertexLabels->Thread[s->m]dan p=FindShortestPath[...kemudian grafik berikut akan secara visual menampilkan solusi (bagian atas matriks sesuai dengan bagian bawah grafik):

HighlightGraph[g,PathGraph[p,Thread[Most@p->Rest@p]]]

masukkan deskripsi gambar di sini

Kelly Lowder
sumber
3

Haskell, 228 byte

Posisi adalah daftar dari dua elemen, karena itu mudah dibuat dengan sequencedan sama mudahnya dengan pola yang cocok dengan 2-tupel.

h=g[[-1,-1]]
g t@(p:r)c|p==m=0|1<2=minimum$(sum$concat c):(\q@[a,b]->c!!a!!b+g(q:t)c)#(f(e$s$(\x->[0..x])#m)$f(not.e t)$zipWith(+)p#s[[-1..1],[-1..1]])where m=[l(c)-1,l(head c)-1]
(#)=map
f=filter
e=flip elem
s=sequence
l=length

Mulai pada -1,-1dan hitung biaya setiap langkah bidang tujuan.

Alternatif dua baris pertama: mulai dari 0,0, hitung bidang keberangkatan, berakhir pada koordinat yang sama dengan dimensi matriks (jadi turun kanan dari tujuan, yang perlu ditambahkan ke daftar tujuan hukum) - persis sama panjang tetapi lebih lambat:

j=i[[0,0]]
i t@(p@[a,b]:r)c|p==m=0|1<2=c!!a!!b+(minimum$(sum$concat c):(\q->i(q:t)c)#(f(e$m:(s$(\x->[0..x-1])#m))$f(not.e t)$zipWith(+)p#s[[-1..1],[-1..1]]))where m=[l c,l$head c]

Menggunakan infix untuk maptidak menghemat byte di sini, tetapi saya menggantinya segera setelah itu tidak memerlukan biaya satu, karena itu hanya bisa lebih baik dengan lebih banyak menggunakan, dan kadang-kadang dengan restrukturisasi lain juga yang memotong sepasang kurung lainnya.

Untuk ditingkatkan: Redundan filters. Penggabungan / di-lapisan mereka untuk filter(flip elem$(s$(\x->[0..x])#m)\\p)dengan import Data.Listuntuk \\biaya 3 byte.

Juga, terlalu buruk (fromEnumTo 0)adalah 2 byte lebih lama dari (\x->[0..x]).

sum$concat cadalah semua biaya bidang diringkas dan dengan demikian batas atas yang dapat diungkapkan secara singkat pada biaya jalur yang diberikan kepada minimumuntuk menghindari daftar kosong (pemeriksa tipe saya telah menentukan semuanya untuk dikerjakan pada Integers, jadi tidak ada hard-coding maksimum , hehe). Tidak peduli bagaimana saya membatasi langkah-langkah berdasarkan yang dibuat sebelumnya (yang akan mempercepat banyak algoritma, tetapi juga biaya byte), saya tidak dapat menghindari jalan buntu yang membuat ini diperlukan kembali mundur.

  • Satu gagasan filter adalah ((not.e n).zipWith(-)(head r))dengan mengekstraksi n=s[[-1..1],[-1..1]], yang mengharuskan penambahan ,[-1,-1]ke jalur awal. Algoritme kemudian menghindari pergi ke tempat yang seharusnya sudah ada pada langkah sebelumnya, yang membuat menginjak bidang tepi secara orthogonal ke tepi itu menjadi jalan buntu.

  • Lain adalah ((>=0).sum.z(*)d)dengan mengekstraksi z=zipWith, yang memperkenalkan argumen baru dpada fungsi rekursif yang diberikan seperti (z(-)p q)pada rekursi dan [1,1]dalam kasus awal. Algoritme menghindari langkah-langkah berurutan dengan produk skalar negatif ( dmenjadi langkah sebelumnya), yang berarti tidak ada putaran tajam 45 °. Ini masih mempersempit pilihan, dan menghindari jalan buntu sepele sebelumnya, tetapi masih ada jalan yang berakhir tertutup di bidang yang sudah dikunjungi (dan mungkin 'pelarian' yang bagaimanapun akan berbelok tajam).

Leif Willerts
sumber
3

Python 2, 356 320 byte

s=input()
r=lambda x:[x-1,x,x+1][-x-2:]
w=lambda z:[z+[(x,y)]for x in r(z[-1][0])for y in r(z[-1][1])if x<len(s)>0==((x,y)in z)<len(s[0])>y]
l=len(s)-1,len(s[0])-1
f=lambda x:all(l in y for y in x)and x or f([a for b in[l in z and[z]or w(z)for z in x]for a in b])
print min(sum(s[a][b]for(a,b)in x)for x in f([[(0,0)]]))

Coba di sini!

-36 bytes terima kasih kepada notjagan !

Menerima daftar daftar sebagai input, dan mengeluarkan biaya terendah saat menavigasi matriks dari kiri atas ke kanan bawah.

Penjelasan

Temukan setiap rute yang mungkin dari kiri atas ke kanan bawah dari matriks, buat daftar koordinat x, y untuk setiap rute. Rute tidak dapat mundur, dan harus berakhir pada (len(s)-1,len(s[0])-1).

Jumlahkan bilangan bulat pada setiap jalur koordinat, dan kembalikan biaya minimum.

The printdapat dengan mudah diubah ke output daftar koordinat untuk rute terpendek.

Solvasi
sumber
-36 byte dengan beberapa perubahan lain-lain.
notjagan
@ notjagan Perubahan besar, terutama penggunaan orconditional. Terima kasih!
Solvation
1

APL (Dyalog Classic) , 33 byte

{⊃⌽,(⊢⌊⍵+(⍉3⌊/⊣/,⊢,⊢/)⍣2)⍣≡+\+⍀⍵}

Cobalah online!

{ } berfungsi dengan argumen

+\+⍀⍵ mengambil jumlah parsial demi baris dan kolom untuk menetapkan batas atas pesimis pada jarak jalur

( )⍣≡ ulangi sampai konvergensi:

  • (⍉3⌊/⊣/,⊢,⊢/)⍣2min jarak ke tetangga, yaitu lakukan dua kali ( ( )⍣2): kolom paling kiri ( ⊣/,) ke self ( ) dan tambahkan kolom paling kanan ( ,⊢/), cari minima dalam tripel horizontal ( 3⌊/) dan transpos ( )

  • ⍵+ tambahkan nilai setiap node ke jarak min ke tetangga

  • ⊢⌊ cobalah untuk mengalahkan jarak terbaik saat ini

⊃⌽, Akhirnya, kembalikan sel kanan bawah

ngn
sumber