Pencarian A*
Algoritma Dijkstra menemukan jalan terpendek ke tujuan, tetapi mencari ke segala arah sekaligus, bahkan menjauhi tujuan. Pencarian A* menambahkan satu pengetahuan, yaitu perkiraan seberapa jauh lagi tujuannya, dan tiba-tiba pencarian langsung menuju ke sana.
Gagasannya
Saat mencari rute di peta, Anda tidak menjelajahi jalan yang menjauhi tujuan dengan sama telitinya seperti jalan yang menuju ke sana. Pencarian A* melakukan hal yang sama. Tiap simpul mendapat skor: jarak dari awal sejauh ini, g, ditambah perkiraan sisa jarak, h. Pencarian selalu berlanjut dari simpul dengan skor terendah, jadi simpul yang mengarah ke tujuan didahulukan.
Langkah demi langkah
Beri awal jarak 0 dan masukkan ke antrean dengan skor h(start). Ulangi: ambil simpul dengan skor terendah, dan tandai jaraknya final. Jika itu tujuan, berhenti: menelusuri kembali simpul-simpul yang diingat menghasilkan jalurnya. Jika bukan, untuk tiap tetangga yang belum final, hitung jaraknya lewat simpul ini. Jika lebih pendek dari jaraknya sejauh ini, turunkan jaraknya, ingat simpul ini sebagai jalan ke sana, dan beri tetangga skor berupa jarak barunya ditambah perkiraannya. Jika dua skor sama, mengambil simpul dengan perkiraan lebih kecil lebih dulu biasanya lebih cepat mencapai tujuan.
Sebuah contoh
Ambil awal A dan tujuan D. A–B panjangnya 2 dan B–D 2, sedangkan A–C 1 dan C–D 5. Perkiraan garis lurus ke D adalah 3 dari A, 2 dari B, dan 3 dari C. A mulai dengan skor 0 + 3 = 3. Mengambil A memberi B skor 2 + 2 = 4 dan C skor 1 + 3 = 4. Karena seri, A* mengambil B, simpul dengan perkiraan lebih kecil, dan B memberi D skor 4 + 0 = 4. Kini D punya skor terendah dengan perkiraan terkecil, jadi D diambil: jalur terpendeknya A → B → D, dengan panjang 4, dan C, yang mengarah ke jalan yang salah, tidak pernah difinalkan. Algoritma Dijkstra akan memfinalkan C lebih dulu, karena C simpul terdekat dari A.
Perkiraan yang baik
Perkiraan tidak boleh lebih panjang dari jarak sebenarnya ke tujuan; perkiraan seperti itu disebut admissible, dan dengannya A* selalu menemukan jalur terpendek. Garis lurus admissible karena tidak ada rute yang lebih pendek dari garis lurus. Jika perkiraan juga tidak pernah turun lebih dari panjang sisi dari satu simpul ke simpul berikutnya, perkiraan itu konsisten, dan simpul yang sudah final tidak perlu diperiksa lagi. Makin dekat perkiraan dengan kenyataan, makin sedikit simpul yang dibutuhkan A*. Perkiraan 0 admissible tetapi tidak berguna: A* lalu menjadi algoritma Dijkstra. Perkiraan yang terlalu besar membuat A* lebih cepat tetapi bisa melewatkan jalur terpendek.
Sejarah dan penggunaan
Peter Hart, Nils Nilsson, dan Bertram Raphael di Stanford Research Institute menerbitkan A* pada 1968, saat mengerjakan Shakey, salah satu robot bergerak pertama. Versi mereka sebelumnya bernama A1 dan A2; bintangnya menandai versi yang mereka buktikan optimal. Kini A* menggerakkan karakter mengitari rintangan di gim video, merencanakan rute dan gerakan robot, serta memecahkan teka-teki seperti 15-puzzle, tempat perkiraan menjumlahkan seberapa jauh tiap ubin dari tempatnya.
Jelajahi
Buka aplikasinya dan tekan Langkah. Angka di sisi adalah panjangnya, yang di sini sesuai dengan panjang gambarnya, dan garis putus-putus menunjukkan perkiraan garis lurus ke tujuan. Antrean di bawah graf mencantumkan simpul menurut skor, yang terendah lebih dulu. Saat tujuan final, baris status membandingkan berapa simpul yang difinalkan A* dengan berapa yang dibutuhkan algoritma Dijkstra. Coba tujuan di sudut jauh graf besar untuk melihat perbedaan terbesar.
Pertanyaan yang sering diajukan
Apa arti bintang pada A*?
Hart, Nilsson, dan Raphael mula-mula menjelaskan algoritma yang mereka sebut A1 dan A2. A* ("A star") adalah versi yang mereka buktikan menemukan jalur terpendek dengan simpul yang diekspansi paling sedikit di antara algoritma sebanding yang memakai perkiraan yang sama, jika perkiraannya konsisten.
Berapa kompleksitas waktu A*?
Dalam kasus terburuk, dengan perkiraan yang tidak berguna, A* bekerja sama banyak dengan algoritma Dijkstra: O((V + E) log V) dengan binary heap. Dengan perkiraan yang baik, A* hanya memfinalkan sebagian kecil simpul, sehingga cepat dalam praktik.
Apa heuristik yang baik untuk A*?
Cepat dihitung, tidak pernah melebih-lebihkan jarak sebenarnya, dan sedekat mungkin dengannya. Pada grid yang hanya bisa bergerak ke atas, bawah, kiri, dan kanan, jarak Manhattan pilihan umum; di peta, jarak garis lurus.
Bagaimana jika heuristik melebih-lebihkan?
Maka A* bisa menghasilkan jalur yang bukan terpendek, karena bisa selesai sebelum memeriksa rute yang lebih baik. Sebagian program sengaja melakukannya (A* berbobot) untuk menukar sedikit kualitas jalur dengan kecepatan yang jauh lebih tinggi.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba pencarian A*