Algoritma Pencarian A* (A-star) dalam Kecerdasan Buatan

Algoritma ini adalah teknik pencarian yang meminimalkan total cost dari suatu solusi. Algoritma pencarian A^∗ (diucapkan “A-star") adalah teknik pencarian dalam jenis best-first yang paling terkenal. Algoritma ini mengevaluasi node dengan menggabungkan/mengombinasikan fungsi g(n), yaitu cost untuk mencapai node berikutnya (seperti dalam pencarian uniform-cost), dan fungsi h(n), yaitu cost antara suatu node ke node goal/node tujuan (seperti dalam pencarian greedy best first):

f(n) = g(n) + h(n)

Karena g(n) memberikan cost dari node awal ke node n, dan h(n) adalah cost terendah dari n ke goal/tujuan, maka kita akan memiliki f(n) = perkiraan cost dengan solusi termurah melalui n.
[Catatan: untuk fungsi g(n) silahkan lihat ke artikel Algoritma Pencarian Uniform-Cost dalam Kecerdasan Buatan. Sedangkan untuk h(n) silahkan lihat ke artikel Algoritma Pencarian Greedy Best First pada Kecerdasan Buatan]

Jadi, jika kita mencoba menemukan solusi terbaik (termurah), hal yang masuk akal untuk dicoba pertama kali adalah node dengan nilai terendah dari g(n) + h(n). Ternyata, strategi ini lebih dari sekadar masuk akal: asalkan fungsi heuristik h(n) memenuhi kondisi tertentu, maka pencarian A* adalah complete dan optimal. Algoritma ini identik dengan pencarian UNIFORM-COST kecuali bahwa A^∗ menggunakan g + h alih-alih menggunakan g saja.

[Catatan: untuk memahami tentang complete/completeness dan optimal/optimality silahkan lihat kriteria kinerja algoritma pencarian pada artikel Pencarian Breadth First dalam Kecerdasan Buatan  di bagian catatan akhir].

Pada contoh gambar di bawah ini, ditunjukkan proses pencarian pohon A^∗ pada kasus Bucharest sebagai node goal/tujuan.

Proses pencarian pohon A^∗ pada kasus Bucharest. Node-node diberi label f = g + h. Nilai g diambil dari fungsi jarak dari gambar peta Romania seperti yang ada dalam gambar di bawah setelah gambar ini. Dan nilai h didapatkan dari fungsi jarak garis lurus ke Bucharest yang diambil dari tabel di bawah setelah gambar ini.

Gambar peta Romania dan jarak antar node sebagai fumgsi g.

Tabel cost/jarak berdasarkan garis lurus antara suatu node ke Bucharest sebagai fungsi h

Nilai-nilai g dihitung dari cost antar node pada gambar di atas (gambar peta romania), dan nilai-nilai h diberikan seperti yang ada pada tabel di atas.

Perhatikan bahwa Bucharest pertama kali muncul pada langkah (e), tetapi tidak dipilih untuk diturunkan/ekspansi karena f-cost (450) lebih tinggi daripada Pitesti (417). Ini artinya akan mengatakan bahwa mungkin ada solusi yang lebih baik yaitu melalui Pitesti yang cost-nya adalah  417, sehingga algoritma tidak akan menerima solusi yang cost-nya 450.