Pengertian Best First Search (Pencarian Terbaik Pertama) :
Metode ini merupakan kombinasi dari metode depth-first search dan breadth-first search. Proses dilakukan dengan melakukan penelusuran terhadap setiap node yang memiliki estimasi terpendek.
Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk.
Pada proses searching ini dilakukan dengan cara memberikan estimasi berapa jauh node asal dari solusi yang diinginkan.
Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan :
f’(n) = g(n) + h’(n)
dimana f’ = Fungsi evaluasi
g = cost dari initial state ke current state
h’ = prakiraan cost dari current state ke
goal state
Algoritma :
Contoh Soal :
Misalkan kita memiliki ruang pencarian seperti pada gambar di bawah. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengannode A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di node A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara node n dengan node tujuan (jalan buntu). Kita bisa merunut nilai untuk setiap node.
