Pencarian A*
Dijkstra dengan rasa arah. Pada biaya setiap tempat ia menambahkan perkiraan biaya yang tersisa, jadi ia mencoba dulu tempat yang tampak paling dekat dengan tujuan.
- waktu O((V + E) log V)
- memori O(V)
- memakai antrean prioritas
Apa artinya?
- Biaya: harga sebuah langkah. Di labirin, tanah berbiaya 1, lumpur 3, dan air 9; di graf, angka pada sisi.
- Antrean prioritas: antrean tempat yang termurah maju duluan, bukan yang datang duluan.
- Perkiraan (h): tebakan biaya yang tersisa. A* hanya tetap tepat jika tebakan itu tidak pernah terlalu tinggi.
- Relaksasi sisi: memeriksa apakah lewat tempat saat ini memberi tetangga biaya lebih rendah, lalu mengambilnya jika ya.
- dalam antrean
- saat ini
- tuntas
- jalan termurah
- tanah · 1
- lumpur · 3
- air · 9
- dinding
Baru: Mulai di A1 dengan biaya 0 dan perkiraan 26 ke tujuan. Satu-satunya di antrean.
Spasi: putar atau jeda. Panah kiri dan kanan: melangkah. Home dan End: lompat.
Coba ini: Pilih lapangan terbuka dan beralih antara Dijkstra dan A*: keduanya menemukan jalan berbiaya sama, tetapi A* mengambil jauh lebih sedikit sel dari antrean.
Cara kerjanya
A* bekerja seperti Dijkstra, tetapi mengurutkan antrean menurut f = biaya sejauh ini + h, dengan h memperkirakan biaya yang tersisa. Di labirin, h adalah jumlah langkah ke M tanpa menghitung dinding dan lumpur; di graf, jarak garis lurus dibagi 10. Selama h tidak pernah menebak terlalu tinggi, jalan yang dimiliki A* saat mengambil tujuan adalah yang termurah, persis seperti Dijkstra. Makin baik perkiraannya, makin sedikit tempat yang perlu dilihat.
Kapan ini pilihan yang tepat
Gunakan A* saat mencari satu tujuan dan bisa memperkirakan seberapa jauh: pencarian jalan di gim, robot, perencana rute di peta. Dengan h = 0 hasilnya persis Dijkstra. Perkiraan yang bisa terlalu tinggi membuat A* lebih cepat, tapi bisa membuat jalan termurah terlewat.