Langkah-langkah yang menjamin keluar dari labirin

14

Diberikan labirin 2 dimensi di mana Anda dapat memberikan 4 perintah "bergerak naik / turun / kanan / kiri". Mengetahui labirin tetapi tidak di mana orang itu berada, bagaimana menemukan urutan minimum perintah yang menjamin keluar dari labirin? Saya mencari satu urutan perintah yang akan bekerja di mana pun di labirin Anda mulai.

Asumsikan bahwa jika pasangan kita diberi perintah "bergerak ke kanan" ketika ada dinding di sebelah kanan, dia hanya akan tetap di tempatnya.

Dengan kata lain, kita diberi labirin, dan kita harus memilih urutan perintah. Kemudian, mitra kami akan ditempatkan di suatu tempat di labirin dan akan mengikuti urutan perintah yang telah kami pilih sebelumnya. Kami ingin urutan ini untuk memastikan pasangan kami akan melarikan diri, di mana pun pasangan kami awalnya ditempatkan. Perhatikan bahwa perintah yang diijinkan tidak memiliki pernyataan kondisional, sehingga tidak dapat mengikuti urutan yang berbeda tergantung pada pasangan Anda.

Apakah ada algoritma waktu polinomial untuk membangun urutan seperti itu, diberi deskripsi labirin?

Yuval Filmus menyebutkan ini adalah kasus khusus dari masalah kata sinkronisasi , dan mungkin terkait dengan urutan traversal universal. Saya juga menemukan makalah yang tampaknya relevan:

Pemecahan Masalah Labirin Simultan . Stefan Funke, André Nusser, Sabine Storandt. AAAI 2017.

Sayangnya untuk grafik umum ini tampaknya menjadi masalah yang belum terpecahkan, tapi saya bertanya-tanya apakah mungkin ada algoritma yang baik untuk kasus khusus ini. Saya datang dengan pendekatan kandidat: Beri label setiap posisi dengan jumlah langkah minimum yang diperlukan untuk keluar, dan catat setiap agen di labirin. Mungkin saja melakukan pencarian A * dengan cara ini.

algorithms graphs graph-traversal seilgu
sumber
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
Kadal diskrit
Strategi Eppstein untuk automata monotonik adalah mengelompokkan negara-negara sehingga daripada mencari lintasan dalam rangkaian daya penuh keadaan, ia mencari lintasan dalam grafik dengan hanya banyak simpul secara polinomi. Generalisasi interval yang paling alami ke 2D yang dapat saya pikirkan adalah convex hull, tetapi sayangnya tidak jelas bahwa jumlah mereka bertambah secara polinomi .
Peter Taylor

Jawaban:

-1

Algoritma yang selalu berfungsi adalah: Letakkan tangan kiri di dinding, dan lanjutkan ke jalan keluar. Tidak dapat menjamin jalur terpendek (untuk melakukannya, Anda harus mengetahui labirin, setidaknya sebagian, dan dapat melihat ke depan. LihatSEBUAH∗Algoritma (bintang-A) , awalnya dirancang hanya untuk tugas-tugas seperti itu).

vonbrand
sumber
Anda tidak dapat menyandikan pengikut dinding sebagai urutan tetap dari arah Kardinal. Pilihannya tergantung pada dinding di sekitar Anda, yang secara khusus tidak diizinkan oleh pertanyaan.
Curtis F
Jika Anda tahu jalur terpendek, Anda dapat menyandikannya sebagai "bergerak ke kiri, lalu lurus, lalu ...". Jika Anda tidak tahu jalan terpendek, Anda tidak bisa memberikan arahan seperti itu untuk jalan keluar terpendek. Jika Anda tidak tahu jalan, Anda tidak bisa memberikan arahan untuk keluar.
vonbrand