Bagaimana menemukan jalur terpendek dengan node wormhole?

Ini adalah contoh dari apa yang ingin saya lakukan melalui kode. Saya tahu Anda dapat menggunakan pencarian titik melompat untuk dengan mudah mendapatkan dari simpul hijau ke simpul merah tanpa masalah, atau bahkan A *. Tetapi bagaimana Anda menghitung ini dengan lungsin.

Pada gambar, Anda dapat melihat bahwa hanya diperlukan 8 gerakan untuk mendapatkan dari simpul hijau ke simpul merah saat mengambil jalur biru. Jalur biru langsung memindahkan posisi Anda dari satu simpul ungu ke simpul berikutnya. Ruang di tengah yang memerlukan 2 gerakan adalah titik di antara dua zona lungsin yang harus Anda pindah ke.

Jelas lebih cepat untuk mengambil jalur biru, karena Anda hanya perlu memindahkan setengah (kira-kira) sejauh jalur kuning, tetapi bagaimana saya melakukan ini secara terprogram?

Untuk tujuan memecahkan masalah ini, mari kita asumsikan ada beberapa "warps" ungu di sekitar grafik yang dapat Anda gunakan, DAN kami tahu persis di mana setiap titik ungu akan melengkung ke, dan di mana mereka berada pada grafik.

Beberapa warp ungu adalah bi-directional, dan beberapa tidak, artinya, kadang-kadang Anda hanya dapat memasukkan warp dari satu sisi, tetapi tidak kembali setelah warping.

Saya telah memikirkan solusinya, dan hanya menyimpulkan bahwa saya akan dapat menghitung masalah dengan memeriksa jarak ke setiap titik warp (minus poin uni-directional), dan perbedaan antara titik-titik itu, dan titik-titik yang dekat dengan mereka .

Program ini harus mencari tahu entah bagaimana bahwa lebih menguntungkan untuk mengambil lungsin kedua, daripada berjalan dari lompatan pertama. Jadi, alih-alih memindahkan 6 titik, lalu membengkokkan, lalu memindahkan 8 langkah tersisa dengan berjalan kaki (yang juga lebih cepat daripada tidak menggunakan bengkok sama sekali), itu akan mengambil 6 langkah, kemudian dua bergerak ke bengkok kedua.

EDIT: Saya menyadari jalur biru sebenarnya akan mengambil 12 langkah, bukan 8, tetapi pertanyaannya tetap sama.

Kebanyakan algoritma pencarian jalur didefinisikan dalam bentuk grafik, bukan dalam bentuk grid. Dalam grafik, koneksi antara dua node yang jauh tidak benar-benar masalah.

Namun, Anda harus berhati-hati dengan heuristik Anda. Dengan lubang cacing, jarak minimum antara dua node tidak lagi jarak euclidean dan jarak tidak memenuhi ketidaksetaraan segitiga. Heuristik seperti itu tidak dapat diterima untuk A *. Karena itu Anda tidak dapat menggunakan A * dengan mudah.

Tentu saja algoritma pencarian jalur seperti Dijkstra yang tidak menggunakan heuristik akan tetap berfungsi. Ini lebih seperti pencarian pertama dan akan memilih lubang cacing Anda tanpa usaha ekstra. Namun, Dijkstra akan mengunjungi lebih banyak node yang A * dengan heuristik yang baik. (Dijkstra setara dengan A * dengan heuristic(x) = 0.)

Saya pikir A * akan bekerja jika Anda menggunakan heuristik yang memperlakukan semua lubang cacing keluar sebagai lubang cacing langsung ke target: heuristik dapat meremehkan jarak, tetapi jangan pernah melebih-lebihkan itu. Yaitu heuristik akan:

def wormhole_heuristic(x):
  return min(euclidean_distance(x, g) for g in [goal, wormholes...])

Untuk heuristik yang sangat akurat, Anda dapat (secara rekursif) menambahkan jarak dari titik akhir lubang cacing ke tujuan atau lubang lubang berikutnya. Yaitu sebagai pra-perhitungan, Anda dapat melakukan pencarian jalur pada subgraf (yang terhubung sepenuhnya) yang berisi semua lubang cacing dan sasaran, di mana jarak antara dua node adalah jarak euclidean mereka. Ini mungkin bermanfaat jika jumlah lubang cacing jauh lebih sedikit daripada jumlah sel yang dapat dijangkau di jaringan Anda. Heuristik baru adalah:

def wormhole_heuristic(x):
  direct = euclidean_distance(x, goal)
  via_wormhole = min(euclidean_distance(x, w) + wormhole_path_distance(w, goal) for w in wormholes)
  return min(direct, via_wormhole)

Seperti @Caleth tunjukkan dalam komentar, ini semua sangat merdu dan kita dapat meningkatkan heuristik lubang cacing pertama tanpa melakukan pencarian jalur penuh melalui jaringan lubang cacing, dengan menambahkan jarak antara pintu keluar lubang cacing terakhir dan tujuan. Karena kita tidak tahu jalan keluar lubang cacing mana yang akan digunakan terakhir dan kita tidak boleh melebih-lebihkan, kita harus mengasumsikan jalan keluar terdekat dengan tujuan:

def wormhole_heuristic(x):
  direct = euclidean_distance(x, goal)
  to_next_wormhole = min(euclidean_distance(x, w) for w in wormholes)
  from_last_wormhole = min(euclidean_distance(w.exit, goal) for w in wormholes)
  via_wormhole = to_next_wormhole + from_last_wormhole
  return min(direct, via_wormhole)

Anda memiliki grafik dengan 6 simpul pada kisi dengan koordinat:

A ( 0,0)
B ( 4,7)
C ( 7,4)
D (10,4)
E (16,2)
F (16,0)

Anda dapat menghasilkan grafik lengkap pada simpul-simpul itu dan menetapkan biaya untuk setiap sisi di mana biaya MAX( ABS( x1 - x2 ), ABS( y1 - y2 ) )untuk sisi standar dan biaya 0 untuk lubang cacing.

Ini akan memberi Anda biaya (sebagai matriks kedekatan):

   A  B  C  D  E  F
- -- -- -- -- -- --
A  -  7  7 10 16 16
B  7  -  0  6 12 12
C  7  0  -  3  9  9
D 10  6  3  -  0  6
E 16 12  9  0  -  2
F 16 12  9  6  2  -

Jika ada warps satu arah maka hanya membuat tepi dalam grafik (atau matriks adjacency) yang pergi ke arah itu tetapi tidak sebaliknya.

Anda kemudian dapat menggunakan algoritma Dijkstra dengan antrian prioritas .

Mulai dari Adan dorong setiap tepi yang berdekatan ke antrian prioritas:

Format: (jalur: biaya)

queue     = [ (A-B : 7), (A-C : 7), (A-D : 10), (A-E : 16), (A-F : 16) ]

Ketika item didorong ke antrian - melacak biaya minimum untuk setiap titik dan hanya mendorong jalur ke antrian jika biaya lebih rendah daripada biaya minimum yang ada.

min-costs = { A: 0, B: 7, C: 7, D: 10, E: 16, F: 16 }

Hapus item pertama dari antrian dan, jika biayanya masih sesuai dengan biaya minimum, dorong semua jalur komposit yang dibentuk oleh jalur itu dan ujung-ujungnya yang berdekatan kembali ke antrian prioritas (jika jalur komposit memiliki biaya lebih rendah daripada minimum yang ada):

Menghapus: (A-B : 7)

• Coba (A-B-A : 14)- tolak karena biaya lebih tinggi
• Coba (A-B-C : 7)- tolak dengan biaya yang sama
• Coba (A-B-D : 13)- tolak karena biaya lebih tinggi
• Coba (A-B-E : 19)- tolak karena biaya lebih tinggi
• Coba (A-B-F : 19)- tolak karena biaya lebih tinggi

Menghapus (A-C : 7)

• Coba (A-C-A : 14)- tolak karena biaya lebih tinggi
• Coba (A-C-B : 7)- tolak dengan biaya yang sama
• Coba (A-C-D : 10)- tolak dengan biaya yang sama
• Coba (A-C-E : 16)- tolak dengan biaya yang sama
• Coba (A-C-F : 16)- tolak dengan biaya yang sama

Menghapus (A-D : 10)

• Coba (A-D-A : 20)- tolak karena biaya lebih tinggi
• Coba (A-D-B : 16)- tolak karena biaya lebih tinggi
• Coba (A-D-C : 13)- tolak karena biaya lebih tinggi
• Coba (A-D-E : 10)- masukkan ke dalam antrian
• Coba (A-D-F : 16)- tolak dengan biaya yang sama

Sekarang antrian akan terlihat seperti:

queue     = [ (A-D-E : 10), (A-E : 16), (A-F : 16) ]
min-costs = { A: 0, B: 7, C: 7, D: 10, E: 10, F: 16 }

Menghapus (A-D-E : 10)

• Coba (A-D-E-A : 26)- tolak karena biaya lebih tinggi
• Coba (A-D-E-B : 22)- tolak karena biaya lebih tinggi
• Coba (A-D-E-C : 19)- tolak karena biaya lebih tinggi
• Coba (A-D-E-D : 10)- tolak dengan biaya yang sama
• Coba (A-D-E-F : 12)- masukkan ke dalam antrian

Maka antriannya adalah:

queue     = [ (A-D-E-F : 12), (A-E : 16), (A-F : 16) ]
min-costs = { A: 0, B: 7, C: 7, D: 10, E: 10, F: 12 }

Hapus (A-D-E-F : 12), temukan bahwa Anda telah sampai ke simpul tujuan dengan biaya 12.

Catatan: jalur (A-B-C-D-E-F), (A-C-D-E-F)dan (A-D-E-F)semuanya memiliki biaya minimum yang sama yaitu 12.

Atur matriks yang berisi semua simpul dan gunakan Floyd-Wallenstein-Algorithm atau Bellman-Ford-Algorithm. Keduanya akan menghasilkan matriks dengan jalur terpendek yang mungkin antara semua titik. Anda kemudian dapat mengulangi melalui matriks untuk menemukan jalur terpendek yang menghubungkan dua titik. (Masalah Anda sama dengan TSP asimetris).