Best First Search

Best First Search 

Pencarian terbaik pertama (Best First Search) merupakan suatu cara yang menggabungkan keuntungan atau kelebihan dari pencarian Breadth-First Search dan Depth-First Search. Pada metode ini, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah jika ternyata node pada level yang lebih tinggi memiliki nilai heuristik yang lebih buruk. Pada setiap langkah proses pencarian terbaik pertama, kita memilih node-node dengan menerapkan fungsi heuristik yang memadai pada setiap node/simpul yang kita pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan penggantinya. Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) yang dinyatakan dengan :

f’ = g + h’ 

dimana
f’ = fungsi evaluasi yang sebenarnya terhadap node n
g = Biaya yang di keluarkan dari keadaan awal sampai node n
h’ = Biaya tambahan dari node n sampai tujuan.

Merupakan metode yang membangkitkan suksesor dengan mempertimbangkan harga (didapat dari fungsi heuristik tertentu) dari setiap node, bukan dari aturan baku seperti DFS maupun BFS. Gambar 3.4 mengilustrasikan langkah-langkah yang dilakukan oleh algoritma Best First Search. Pertama kali, dibangkitkan node A. Kemudian semua suksesor A dibangkitan, dan dicari harga paling minimal.
Pada langkah 2, node D terpilih karena harganya paling rendah, yakni 1. Langkah 3, semua suksesor D dibangkitkan, kemudian harganya akan dibandingkan dengan harga node B dan C. Ternyata harga node B paling kecil dibandingkan harga node C, E, dan F. Sehingga B terpilih dan selanjutnya akan dibangkitkab semua suksesor B. Demikian seterusnya sampai ditemukan node Tujuan.

 

Gambar 3.4 Langkah-langkah yang dilakukan oleh algoritma Best First Search.

 Untuk mengimplementasikan metode Best First Search ini dengan menggunakan graph keadaan , di butuhkan 2 antrian yang berisi node node, yaitu : Open, yang berisi node node yang sudah dibangkitkan , sudah memiliki fungsi heuristik namun belum di uji . Umumnya berupa antrian berprioritas yang berisi elemen elemen dengan nilai heuristik tinggi. Closed berisi node node yang sudah diuji . Algoritma: 1. Tempatkan node awal A pada antrian open 2. Kerjakan langkah2 berikut hingga tujuan ditemukan atau antrian OPEN sudah kosong a. Ambil node terbaik dari open; b. Bangkitkan semua successornya c. Untuk tiap tiap successor kerjakan tiap-kosong. successornya. kerjakan: i. Jika node tersebut belum pernah di bangkitkan sebelumnya , evaluasi sebelumnya, node tersebut dan masukkan ke open ii. Jika node tersebut sudah pernah di bangkitkan sebelumnya , ubah parent sebelumnya, jika lintasan baru lebih menjanjikan Hapus node tersebut dari antrian open. di- di- menjanjikan.