Algoritma Heuristik - Best First Search

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness).
Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

– Generate and Test.

– Hill Climbing.

– Best First Search.

– Means-EndAnlysis, Constraint Satisfaction, dll

PENCARIAN TERBAIK PERTAMA (Best-First Search)

Metode ini merupakan kombinasi dari metode depthfirst search dan breadth-first search. 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.
Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan :

f’(n) = g(n) + h’(n)
- f’ = Fungsi evaluasi
- g = cost dari initial state ke current state
- h’ = prakiraan cost dari current state ke goal state

Contoh soal 1 dan jawaban Algoritma Best First Search :
Misalkan kita memiliki ruang pencarian seperti pada gambar berikut. 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.

Contoh soal 2 dan jawaban Algoritma Best First Search :
Selesaikan puzzle di bawah ini dari node awal A ke node tujuan Z, menggunakan algoritma Heuristik yaitu Algoritma Best First Search. Cara mengerjakan seperti studi kasus di bawah ini.