26
b.
A*
A* adalah algoritma best first search
yang
menggabungkan Uniform Cost Search
dan Greedy Best First
Search. Biaya yang diperhitungkan didapat dari biaya
sebenarnya ditambah dengan biaya perkiraan. Dalam notasi
matematika dituliskan sebagai
f(n)= g(n) + h(n).
Dengan
perhitungan biaya seperti ini, algoritma A* adalah
complete dan optimal.
2.9
Metode A* Heuristic
Metode A* adalah salah satu contoh dari metode best first search. Metode A*
dikembangkan pada tahun 1968 oleh Peter Hart, Nils Nilsson, dan Bertram Raphael,
mereka juga menyebut metode tersebut dengan sebutan algoritma A, dengan metode
ini dan fungsi heuristic
yang tepat menghasilkan sebuah hasil yang optimal, yaitu
A*.
Dalam ilmu komputer, A* (dibaca : A star) adalah sebuah graph atau metode
tree search
yang digunakan untuk mencari jalan dari sebuah node
awal ke node
tujuan yang telah ditentukan, metode ini mengunakan “estimasi heuristic” h(n) pada
setiap node
untuk mengurutkan setiap node n berdasarkan estimasi rute terbaik yang
melalui node tersebut.
Metode A* hanya membangun rute yang mungkin digunakan untuk mencapai
tujuan. Untuk mengetahui rute mana yang memungkinkan mengarah ke titik akhir,
A* menggunakan
estimasi heuristik
jarak dari sembarang node
ke node
tujuan.
Prinsip algoritma ini adalah mencari jalur terpendek dari sebuah simpul awal
(starting point) menuju simpul tujuan dengan memperhatikan harga (F) terkecil.
 |