Algoritma Pencarian A*
- Diperkenalkan oleh
- Peter E. Hart, Nils J. Nilsson, and Bertram Raphael
- Tahun
- 1968
- Jenis
- algorithm
- Keluarga
- Graph Algorithms
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Algoritma Pencarian A*, dikembangkan oleh Peter E. Hart, Nils J. Nilsson, dan Bertram Raphael pada tahun 1968, adalah algoritma pencarian jalur optimal yang menggabungkan manfaat algoritma Dijkstra dengan panduan heuristik.
Algoritma ini secara efisien menemukan jalur terpendek dengan menyeimbangkan jarak aktual dari titik awal dengan perkiraan jarak ke tujuan.
Intuisi di balik metode
A* menggunakan fungsi evaluasi f(n) = g(n) + h(n), di mana g(n) adalah biaya aktual dari awal ke node n, dan h(n) adalah perkiraan heuristik dari biaya yang tersisa ke tujuan. Dengan mengeksplorasi node dengan nilai f(n) terendah, algoritma ini secara efisien mempersempit ruang pencarian menuju tujuan sambil mempertahankan optimalitas ketika heuristik bersifat dapat diterima (tidak pernah melebih-lebihkan). Hal ini membuat A* secara signifikan lebih cepat daripada metode pencarian yang tidak terinformasi sambil tetap terjamin menemukan jalur optimal.
Sejarah
Hart, Nilsson, dan Raphael menerbitkan A* pada tahun 1968, menunjukkan bahwa penambahan informasi heuristik ke algoritma Dijkstra dapat secara dramatis meningkatkan efisiensi pencarian sambil mempertahankan optimalitas. Algoritma ini menjadi dasar dalam kecerdasan buatan dan riset operasi. Perkembangan selanjutnya meliputi A* dua arah, IDA* (pendalaman iteratif), dan berbagai perbaikan heuristik. A* tetap menjadi pilihan standar untuk pencarian jalur di mesin permainan modern dan sistem robotika.
Kapan digunakan
Terapkan A* ketika Anda perlu menemukan jalur optimal dalam graf di mana fungsi heuristik yang baik tersedia. Algoritma ini sangat efektif untuk pencarian jalur dalam permainan, robotika, dan perencanaan rute di mana pencarian terinformasi dapat secara substansial mengurangi komputasi. Gunakan ketika kecepatan penting tetapi optimalitas diperlukan. Untuk kasus tanpa heuristik yang andal, gunakan algoritma Dijkstra sebagai gantinya.
Batasan dan pertimbangan
- Optimalitas bergantung pada penerimaan fungsi heuristik
- Kinerja menurun secara signifikan dengan heuristik yang buruk atau tidak dapat diterima
- Penggunaan memori bisa sangat besar dalam ruang pencarian yang luas (mempertahankan himpunan terbuka dan tertutup)
- Memerlukan pengetahuan domain eksplisit untuk merancang fungsi heuristik yang baik
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Pencarian jalur optimal ketika heuristik dapat diterima
- Jauh lebih cepat daripada Dijkstra atau pencarian lebar pertama ketika heuristik yang baik tersedia
- Fleksibel: bekerja dengan fungsi heuristik yang dapat diterima
- Sangat cocok untuk masalah pencarian jalur dengan satu tujuan
- Validasi dunia nyata yang ekstensif dalam permainan, robotika, dan sistem navigasi
Penerapan
- Pencarian jalur video game: navigasi NPC waktu nyata dalam lingkungan permainan dinamis
- Perencanaan gerak robot: perencanaan jalur optimal untuk robot otonom yang menghindari rintangan
- Navigasi GPS: menghitung rute efisien dengan mempertimbangkan jaringan jalan dan lalu lintas
- Pemecahan teka-teki: menemukan solusi optimal dalam masalah kombinatorial seperti teka-teki 15
- Perutean jaringan: menentukan rute paket yang efisien dengan heuristik kualitas taut
- Bioinformatika: pencarian penyelarasan urutan dan prediksi struktur protein
Cara kerjanya
Cara kerjanya
Buat himpunan terbuka dengan node awal, tetapkan nilai g-nya (biaya dari awal) menjadi nol, dan hitung nilai h-nya menggunakan fungsi heuristik.
Pilih node dengan nilai f terendah dari himpunan terbuka, hitung nilai f untuk tetangganya yang belum dikunjungi, dan tambahkan tetangga yang menjanjikan ke himpunan terbuka.
Terus perluas node hingga tujuan tercapai dengan nilai f terendah, yang menjamin jalur optimal; rekonstruksi jalur dengan menelusuri penunjuk induk.
Kesalahan umum
- Menggunakan heuristik yang tidak dapat diterima yang melebih-lebihkan biaya, yang mengarah ke jalur suboptimal
- Memilih heuristik yang terlalu sederhana atau tidak terkait dengan masalah, mengurangi efisiensi pencarian
- Implementasi himpunan terbuka yang tidak efisien (seharusnya menggunakan antrean prioritas), menyebabkan pemilihan node yang lambat
Pertanyaan yang sering diajukan
Apa itu heuristik yang dapat diterima dan mengapa itu penting?
Heuristik yang dapat diterima tidak pernah melebih-lebihkan biaya sebenarnya ke tujuan. Properti ini menjamin bahwa A* menemukan jalur optimal. Jika heuristik melebih-lebihkan, A* mungkin melewatkan jalur yang lebih pendek dan mengembalikan solusi suboptimal.
Bagaimana cara merancang heuristik yang baik untuk suatu masalah?
Heuristik yang baik didasarkan pada pengetahuan domain dan struktur masalah. Untuk pencarian jalur berbasis grid, jarak Manhattan atau Euclidean bekerja dengan baik. Untuk masalah yang lebih kompleks, pertimbangkan untuk melonggarkan batasan atau menggunakan basis data pola untuk menghitung heuristik yang dapat diterima.
Apa perbedaan antara algoritma A* dan Dijkstra?
Keduanya menemukan jalur optimal, tetapi A* menggunakan heuristik untuk memprioritaskan eksplorasi menuju tujuan, membuatnya jauh lebih cepat ketika heuristik yang baik tersedia. Dijkstra menjelajahi secara seragam ke segala arah dan lebih aman ketika heuristik tidak dapat diandalkan.
Bisakah A* menjamin penemuan jalur terpendek?
Ya, A* menjamin jalur terpendek ketika heuristik dapat diterima (tidak pernah melebih-lebihkan biaya sebenarnya). Dengan heuristik yang tidak dapat diterima, optimalitas tidak dijamin.
Metode terkait
Sumber
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
Buka referensi DOIDisalin.Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.
ISBN: 978-0-13-604259-4Disalin.