Jalur Terpendek pada Grafik Tidak Terarah?

Jadi saya pikir pertanyaan (meskipun agak mendasar) ini ada di sini:

Katakanlah saya memiliki grafik ukuran 100 node yang tersusun dalam pola 10x10 (pikirkan papan catur). Grafik tidak diarahkan, dan tidak berbobot. Bergerak melalui grafik melibatkan bergerak tiga ruang ke depan dan satu ruang ke kanan atau kiri (mirip dengan bagaimana seorang ksatria catur bergerak melintasi papan).

Diberikan simpul awal yang tetap, bagaimana seseorang menemukan jalur terpendek ke simpul lain di papan tulis?

Saya membayangkan bahwa hanya akan ada tepi antara node yang bergerak layak. Jadi, mengingat informasi ini, saya ingin mencari jalur terpendek dari titik awal ke titik akhir.

Pikiran awal saya adalah bahwa setiap sisi diberi bobot dengan bobot 1. Namun, grafiknya tidak terarah, sehingga Djikstras tidak akan menjadi yang ideal. Oleh karena itu, saya memutuskan untuk melakukannya menggunakan bentuk pencarian pertama yang diubah dalam.

Namun, seumur hidup saya tidak bisa memvisualisasikan cara mendapatkan jalur terpendek menggunakan pencarian.

Hal lain yang saya coba adalah meletakkan grafik dalam bentuk pohon dengan simpul awal sebagai root, dan kemudian memilih hasil yang paling dangkal (jumlah baris terendah) yang memberi saya simpul akhir yang diinginkan ... ini berhasil, tetapi sangat tidak efisien, dan dengan demikian tidak akan berfungsi untuk grafik yang lebih besar.

Adakah yang punya ide yang mungkin mengarahkan saya ke arah yang benar tentang ini?

Terima kasih banyak.

(Saya mencoba memasukkan visualisasi grafik, tetapi tidak dapat karena reputasi saya yang rendah)

Jika tepi pada grafik hanya mewakili gerakan yang valid antara posisi tertentu, menggunakan Dijkstra akan bekerja dengan baik. Namun karena grafik tidak tertimbang, itu akan menjadi terlalu banyak pembunuhan. Pencarian sederhana pertama kali akan memberikan jawaban optimal.

Nicholas sudah memberikan jawaban yang sempurna. Namun, izinkan saya mengatasi upaya awal Anda untuk menggunakan pencarian mendalam-pertama.

Pertama, baik Dijkstra (yang berfungsi dengan baik dengan node tidak tertimbang seperti dicatat oleh Nicholas Mancuso) atau pencarian pertama kali dilakukan dalam membuang-buang memori Anda secara eksponensial. Keuntungan mereka, bagaimanapun, adalah bahwa mereka tidak pernah memperluas kembali node sementara mereka dijamin untuk menemukan solusi optimal. Sayangnya, keterbatasan mereka sangat penting dan mereka seharusnya tidak diharapkan untuk meningkatkan secara wajar.

$d_{max}$$k$$i$-Iterasi ke-3, pencarian mendalam-pertama diluncurkan di kedalaman $d_{max} + i\times k$(dengan iterasi pertama diberi nomor 0). Jika$d_{max}=k=1$ maka Anda dijamin akan menemukan solusi optimal saat menggunakan memori linier di kedalaman solusi.

Nah, Anda mungkin berpikir bahwa memperluas kembali node adalah ide yang buruk. Tidak semuanya! Inilah yang menjamin konsumsi memori linier sementara iterasi yang mendominasi keseluruhan waktu berjalan hanyalah yang terakhir sehingga dapat dibuktikan bahwa algoritma ini menimbulkan biaya overhead$\frac{b}{b-1}$ dengan $b$ menjadi faktor percabangan yang efektif, dan ini jelas merupakan penalti yang sangat kecil yang perlu dipertimbangkan ketika menghadapi masalah yang sulit.

Bersulang,