Apakah jarak Manhattan monoton bila digunakan sebagai fungsi heuristik?

25

Saya memiliki peta berbasis persegi. Hanya gerakan horisontal dan vertikal yang diizinkan (tidak ada diagonal). Biaya perpindahan selalu 1.

Saya menerapkan algoritma A * pada peta itu, menggunakan jarak Manhattan sebagai heuristik jarak. Apakah heuristik ini konsisten? Bisakah saya menghindari pengecekan g(node)terhadap node yang ada di set TERTUTUP?

Sunting: Secara konsisten saya maksudkan monoton.

tiles path-finding geometry Emiliano
sumber
1
Jika biaya pergerakan Anda seragam di setiap ubin, Anda bisa mengganti A * dengan Pencarian Titik Langsung
Nick Caplinger
Hei, itu bagus!
Emiliano

Jawaban:

10

Untuk benar-benar menjawab pertanyaan Anda: jarak manhatten konsisten ketika Anda dibatasi untuk bergerak secara vertikal / horizontal di sepanjang kisi yang tidak berbobot (ini dapat dengan mudah ditunjukkan oleh definisi pada wikipedia) . Jadi ya, dalam kasus Anda, Anda dapat menghindari mengecek ulang node di set tertutup.

Namun, begitu Anda mengizinkan gerakan diagonal atau sudut mana saja, jarak manhatten menjadi diterima karena terlalu melebih-lebihkan biaya diagonal, yang berarti itu tidak konsisten.

BlueRaja - Danny Pflughoeft
sumber
Ya, inilah jawaban yang saya cari. Akan menyenangkan untuk mengetahui apa yang terjadi jika fungsi heuristik adalah h(x) = min(manhattan(p1), manhattan(p2))(yaitu p1 atau p2 adalah titik akhir yang baik dan saya ingin mencapai yang terdekat). Apakah ini h(x)masih monoton?
Emiliano
1
@happy_emi: Ya, jika h(x, p1)dan h(x, p2)konsisten, maka min(h(x,p1), h(x,p2))juga akan konsisten. Ini mudah untuk ditunjukkan dari definisi di wikipedia (kita perlu menunjukkan bahwa min(h(x, p1), h(x, p2)) <= distance(x,y) + min(h(y, p1), h(y, p2))untuk semua node xdan ydengan keunggulan di antara mereka. Sekarang asumsikan itu h(x, p1)adalah minimum; dapatkah Anda menunjukkan bahwa itu pasti <=sisi kanan, menggunakan fakta bahwa kedua heuristik itu konsisten?)
BlueRaja - Danny Pflughoeft
31

Ya, jarak Manhattan antara dua titik selalu sama, seperti jarak reguler di antara mereka. Anda dapat menganggap jarak Manhattan sebagai komponen X dan Y dari sebuah garis yang berjalan di antara dua titik.

Gambar ini ( dari Wikipedia ) menggambarkan hal ini dengan baik:

Jarak Manhattan

Itu hijau adalah jarak yang sebenarnya.

Itu biru , merah dan kuning semuanya mewakili jarak Manhattan yang sama (12 unit). Apa pun kombinasi gerakan ke atas dan kanan yang Anda gambar dari titik kiri bawah ke kanan bawah, Anda akan mendapatkan total jarak Manhattan yang sama.

MichaelHouse
sumber
2
Jawaban yang bagus: pendek, manis, to the point dan dengan gambar yang cantik.
Tom 'Blue' Piddock
1
Jawaban ini dekat, tetapi salah. Gambar ini tidak menunjukkan bahwa jarak Manhattan konsisten (pada kenyataannya, jika Anda menganggap garis hijau sebagai jarak, itu tidak konsisten!) , Dan alasan bahwa ia tidak perlu memeriksa ulang node karena "jarak Manhattan antara dua poin selalu sama " tidak berlaku (pernyataan itu juga berlaku h(x) = 1000, yang jelas tidak konsisten) . Dia dapat menghindari memeriksa ulang node, tetapi hanya karena jarak Manhatten konsisten, yang jawaban ini tidak ditampilkan.
BlueRaja - Danny Pflughoeft
2
Saya percaya dengan definisi yang Anda tautkan, jarak Manhattan konsisten. Jarak garis hijau akan menggunakan heuristik yang berbeda. Garis Merah, Biru dan Kuning menunjukkan bahwa jarak antara kedua node tetap sama (saat menggunakan heuristik yang sama). Bergerak lebih dekat mengurangi heuristik dan bergerak lebih jauh meningkatkan heuristik. Ini memenuhi persyaratan monoton OP. Ketika grafik dibangun, dengan sebuah simpul di setiap "persimpangan", jarak Manhattan konsisten. Jika itu skenario yang berbeda (seperti memungkinkan gerakan diagonal), heuristik akan menjadi buruk.
MichaelHouse
2
Saya sudah mengatakan bahwa Manhatten Distance konsisten, tetapi tidak untuk alasan yang Anda sebutkan. Jawaban Anda tidak menunjukkan konsistensi, juga argumen Anda dalam komentar. "Heuristik konsisten / monoton" memiliki definisi yang tepat (diberikan dalam tautan saya di atas) , yang tidak sama dengan fungsi monoton yang kelihatannya membingungkan Anda. Menyatakan "bergerak lebih dekat mengurangi heuristik dan bergerak lebih jauh meningkatkan heuristik" tidak cukup untuk menunjukkannya konsisten, misalnya. 2*manhattenmemenuhi itu, tetapi tidak konsisten.
BlueRaja - Danny Pflughoeft
3
Saya tidak tahu mengapa Anda mengatakan itu tidak benar , Anda tampaknya bersikeras jawaban ini tidak lengkap . Buktinya dalam jawaban Anda tampaknya sama lemahnya: "jarak manhatten konsisten ...", Anda kemudian melanjutkan untuk mengulangi spesifikasi asli pertanyaan, mengikuti dengan bagaimana hal itu tidak dapat diterima jika skenario berbeda . Saya tidak merasa seolah-olah jawabannya menuntut bukti matematika lengkap. Jika Anda merasa pertanyaan ini mengharuskan, maka harap sertakan dalam jawaban Anda dan saya akan memilihnya. Terima kasih atas kritik yang membangun.
MichaelHouse
6

Dalam perpanjangan jawaban Byte56 saya ingin menunjukkan, bahwa dalam kumpulan data spesifik Anda, menggunakan Jarak Manhattan sebagai fungsi heuristik Anda sebenarnya akan selalu menjadi heuristik yang sempurna dalam arti bahwa itu akan selalu mengembalikan biaya jalur yang sebenarnya (dengan asumsi ada tidak ada yang "menghalangi" jalan).

Anda juga harus mencatat, bahwa semua node dalam arah yang benar (baik secara horisontally atau vertikal) akan menghasilkan jarak yang diharapkan sama (karena ada banyak jalur yang sama pendeknya dengan tujuan). Anda harus menyadari bahwa antrian prioritas Anda (set terbuka) harus, jika ada prioritas terikat, terlebih dahulu menentukan node yang ditambahkan terakhir (LIFO - Last In First Out). Dengan melakukan itu, Anda hanya akan memeriksa node yang akan berakhir di jalur optimal . Jika Anda memeriksa node yang sama-sama cocok dengan cara FIFO (First In First Out), Anda akan secara efektif memeriksa semua node yang merupakan bagian dari jalur terbaik. Masalah ini muncul karena ada beberapa jalur yang sama baiknya ke simpul tujuan.

Thorkil Holm-Jacobsen
sumber
"(dengan asumsi tidak ada yang menghalangi jalan)" - itu asumsi yang cukup besar. Jika tidak ada yang menghalangi jalur, Anda tidak perlu memulai algoritma pencarian jalur!
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft: Itu benar, itu hanya sebuah pemikiran yang muncul ketika melihat gambar Byte56. Namun sisanya benar.
Thorkil Holm-Jacobsen
4

Saya tidak yakin apa yang Anda maksud dengan "selalu" konsisten. Apakah jarak Manhattan pada jaringan tetap tidak tergantung pada jalur yang diambil? Ya, seperti jawaban Byte56.

Namun, misalnya, jarak Manhattan tidak berubah di bawah rotasi. Misalnya, jarak Manhattan ( norma-L1 ) antara titik asal dan titik (10,10)adalah |10-0| + |10-0| = 20. Namun, jika Anda memutar koordinat Anda dengan 45 derajat (jadi sekarang titik tetap Anda berada di sepanjang salah satu arah grid), sekarang Anda akan menemukan titik yang sama sekarang (10sqrt(2),0), sehingga memiliki jarak Manhattan ke titik asal 10sqrt(2)~14.14.

dr jimbob
sumber
+1 untuk menunjukkan ini; OTOH, jarak Manhattan tidak berubah di bawah rotasi 90 derajat, yang benar-benar satu-satunya yang dapat dibuat 'secara konsisten' pada kotak diskrit.
Steven Stadnicki
1
Tangkapan yang bagus, meskipun dia menyebutkan bahwa hanya gerakan horisontal dan vertikal yang diperbolehkan.
Thorkil Holm-Jacobsen
1
Pertanyaan aslinya adalah tentang konsisten seperti dalam monoton.
Emiliano