Saya melihat apa yang telah dilakukan oleh orang-orang di Kompetisi AI Mario dan beberapa dari mereka telah membangun beberapa bot Mario yang cukup rapi menggunakan Algoritma Pathing A * (A-Star).
( Video Mario A * Bot Beraksi )
Pertanyaan saya adalah, bagaimana A-Star dibandingkan dengan Dijkstra? Melihat mereka, mereka tampak serupa.
Mengapa seseorang menggunakan yang satu di atas yang lain? Terutama dalam konteks pathing dalam game?
Jawaban:
Dijkstra adalah kasus khusus untuk A * (ketika heuristik adalah nol).
sumber
Dijkstra:
Ini memiliki satu fungsi biaya, yang merupakan nilai biaya riil dari sumber ke setiap node:
f(x)=g(x)
.Ia menemukan jalur terpendek dari sumber ke setiap simpul lain dengan hanya mempertimbangkan biaya riil.
Pencarian:
Ini memiliki dua fungsi biaya.
g(x)
: sama dengan Dijkstra. Biaya nyata untuk mencapai simpulx
.h(x)
: perkiraan biaya dari simpulx
ke simpul sasaran. Ini adalah fungsi heuristik. Fungsi heuristik ini seharusnya tidak melebih-lebihkan biayanya. Itu berarti, biaya riil untuk mencapai simpul tujuan dari simpulx
harus lebih besar dari atau samah(x)
. Ini disebut heuristik yang dapat diterima.Total biaya setiap node dihitung oleh
f(x)=g(x)+h(x)
Pencarian * hanya memperluas node jika tampaknya menjanjikan. Ini hanya berfokus untuk mencapai node tujuan dari node saat ini, bukan untuk mencapai setiap node lainnya. Ini optimal, jika fungsi heuristik diterima.
Jadi, jika fungsi heuristik Anda bagus untuk memperkirakan biaya di masa depan, maka Anda harus menjelajahi lebih sedikit node daripada Dijkstra.
sumber
Apa yang dikatakan poster sebelumnya, ditambah karena Dijkstra tidak memiliki heuristik dan pada setiap langkah memilih tepi dengan biaya terkecil, ia cenderung "menutupi" lebih banyak grafik Anda. Karena itu Dijkstra bisa lebih berguna daripada A *. Contoh yang baik adalah ketika Anda memiliki beberapa node target kandidat, tetapi Anda tidak tahu, yang mana yang paling dekat (dalam kasus A * Anda harus menjalankannya beberapa kali: satu kali untuk setiap kandidat node).
sumber
Algoritma Dijkstra tidak akan pernah digunakan untuk merintis jalan. Menggunakan A * adalah hal yang sulit jika Anda dapat menemukan heuristik yang layak (biasanya mudah untuk gim, terutama di dunia 2D). Bergantung pada ruang pencarian, Iterative Deepening A * kadang-kadang lebih disukai karena menggunakan lebih sedikit memori.
sumber
Dijkstra adalah kasus khusus untuk A *.
Dijkstra menemukan biaya minimum dari titik awal ke titik lainnya. A * menemukan biaya minimum dari simpul awal ke simpul sasaran.
Algoritma Dijkstra tidak akan pernah digunakan untuk pencarian jalur. Menggunakan A * satu dapat datang dengan heuristik yang layak. Bergantung pada ruang pencarian, A * iteratif lebih disukai karena menggunakan lebih sedikit memori.
Kode untuk algoritma Dijkstra adalah:
Kode untuk algoritma A * adalah:
sumber
Dijkstra menemukan biaya minimum dari titik awal ke titik lainnya. A * menemukan biaya minimum dari simpul awal ke simpul sasaran.
Oleh karena itu, tampaknya Dijkstra akan kurang efisien ketika yang Anda butuhkan adalah jarak minimum dari satu node ke node lainnya.
sumber
Anda dapat mempertimbangkan A * versi panduan Dijkstra. Artinya, alih-alih menjelajahi semua node, Anda akan menggunakan heuristik untuk memilih arah.
Untuk membuatnya lebih konkret, jika Anda menerapkan algoritma dengan antrian prioritas maka prioritas node yang Anda kunjungi akan menjadi fungsi dari biaya (biaya node sebelumnya + biaya untuk sampai ke sini) dan perkiraan heuristik dari sini ke tujuan. Sementara di Dijkstra, prioritas hanya dipengaruhi oleh biaya aktual untuk node. Dalam kedua kasus, kriteria berhenti mencapai tujuan.
sumber
Algoritma Dijkstra menemukan jalur terpendek dengan pasti. Di sisi lain A * tergantung pada heuristik. Untuk alasan ini A * lebih cepat daripada algoritma Dijkstra dan akan memberikan hasil yang baik jika Anda memiliki heuristik yang baik.
sumber
Jika Anda melihat kode psued untuk Astar:
Sedangkan, jika Anda melihat yang sama untuk Dijkstra :
Jadi, intinya adalah, Astar tidak akan mengevaluasi sebuah node lebih dari sekali,
karena ia percaya bahwa melihat suatu node saja sudah cukup, karena
heuristiknya.
OTOH, algoritma Dijkstra tidak malu mengoreksi dirinya sendiri, kalau
- kalau sebuah node muncul lagi.
Yang seharusnya membuat Astar lebih cepat dan lebih cocok untuk pencarian jalur.
sumber
Di A *, untuk setiap node Anda memeriksa koneksi keluar untuk mereka.
Untuk setiap simpul baru Anda menghitung biaya terendah sejauh ini (csf) tergantung pada bobot koneksi ke simpul ini dan biaya yang harus Anda capai untuk simpul sebelumnya.
Selain itu Anda memperkirakan biaya dari node baru ke node target dan menambahkannya ke csf. Anda sekarang memiliki perkiraan total biaya (dll). (etc = csf + perkiraan jarak ke target) Berikutnya Anda memilih dari node baru yang satu dengan yang terendah dll.
Lakukan hal yang sama seperti sebelumnya sampai salah satu node baru akan menjadi target.
Dijkstra bekerja hampir sama. Kecuali bahwa estimasi jarak ke target selalu 0, dan algoritma pertama berhenti ketika target tidak hanya salah satu node baru , tetapi juga satu dengan csf terendah.
A * biasanya lebih cepat daripada dijstra, meskipun ini tidak selalu menjadi masalah. Dalam gim video, Anda sering memilih pendekatan "cukup dekat untuk gim". Oleh karena itu jalur optimal "cukup dekat" dari A * biasanya cukup.
sumber
Algoritma Dijkstra jelas lengkap dan optimal sehingga Anda akan selalu menemukan jalur terpendek. Namun cenderung memakan waktu lebih lama karena digunakan terutama untuk mendeteksi beberapa node tujuan.
A* search
di sisi lain masalah dengan nilai-nilai heuristik, yang dapat Anda tetapkan untuk mencapai tujuan Anda lebih dekat, seperti jarak manhattan ke arah gawang. Ini bisa menjadi optimal atau lengkap yang tergantung pada faktor heuristik. sudah pasti lebih cepat jika Anda memiliki simpul tujuan tunggal.sumber