Algoritma pencarian A* atau disebut juga A-star
search, merupakan format best-fist search yang banyak diketahui. A* search
mengevaluasi tiap node dengan cara mengkombinasikan g(n) dan h(n), dimana g(n)
merupakanCost yang dicapai sampai di n, dan h(n) adalah Estimasi cost untuk
sampai pd goal dari n. Evaluation function dari A* search bisa dituliskan
sebagai berikut :
f(n) = g(n) + h(n)
dimana f(n) merupakan Estimasi total cost dari path
n sampai goal.
Apabila kita ingin menemukan solusi termurah, suatu
hal layak untuk dicoba pertama kali adalah node dengan nilai g(n) yang paling
rendah + h(n). Hal ini menunjukkan bahwa strategi ini lebih dari sekedar layak
: dengan ketentuan bahwa heuristik function h(n) pada kondisi tertentu telah
sesuai, maka A* search optimal dan lengkap.
Tidak ada komentar:
Posting Komentar