Algoritma A* Pada Kecerdasan Buatan

Algoritma ini akan menghitung fungsi heuristic dengan cara menambahkan biaya sebenarnya dengan biaya perkiraan. Sehingga didapatkan rumus :

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

g(n)   =   Biaya sebenarnya dari Node Awal ke Node n

h’(n)  =   Biaya perkiraan dari Node n ke Node Tujuan.

Pada gambar dibawah merupakan langkah 1 dari metode pencarian A* yaitu dengan open S,A,B,C,D,E dan closed S mencari nilai f(n).Mencari nilai mana yang paling pendek yaitu nilai f(E) yaitu 84. 

Setelah langkah 1 selesai maka closed S, E  dan open A, B, C, D, E, J .Di langkah 2 cari nilai f dari node yang diopen dan cari nilai yang terkecil, ditemukan nilai f(B) yang memiliki nilai 85.

Dilanjutkan ke langkah 3 pada gambar dibawahclosed  S,E,B dan open A,C,D,J,F,K. Nilai f(A) memiliki nilai terkecil yaitu 90 nilai B menuju K berjumlah 105 maka di close.

Pada langkah ke 4 di gambar dibawah closed S, E, B, A dan open C, D, J, F, K, G. Nilai F(F)  memiliki nilai terkecil yaitu 95 ,

Langkah 5 pada gambar dibawahclosed S, E, B, A open C, D, J, K, G. Cari nilai f  terkecil yaitu nilai F(K) yang bernilai 95.

Langkah ke 6 pada gambar dibawah closed S, E, B, A ,K dan open C, D, J, G cari nilai f terkecil yaitu nilai f(G) yang bernilai 95.

Setelah semua langkah di jalankan maka akan ditemukan solusi yang terdekat yaitu jalur S – A – B – F – K – G dengan total jarak 95, lihat gambar dibawah, walaupun node E masuk dalam node yang closed namun jarak dari S ke A lebih pendek daripada melalui E.

Algoritma A* merupakan algoritma pencarian yang optimal dibandingkan dengan metode algoritma greedy.

Begitulah kawan penjelasan tentang algoritma A* yang memang rada lieur kalo kata bahasa sundanya hehe... tapi ini berguna untuk aplikasi pencarian seperti maps maupun lainya.