Pencarian heuristik

• Pencarian heuristik
 Ada 4 macam metode dalam pencarian heuristik:
1). Pembangkit & Pengujian (Generate and Test)
2.) Pendakian Bukit (Hill Climbing)
3.) Pencarian Terbaik Pertama (Best First Search)
4.) Simulated Annealing

• Pencarian terbaik pertama ( Best First Search)
merupakan kombinasi dari metode depth-first search dan metode breadth-first search
dengan mengambil kelebihan dari kedua metode tersebut. Pada metode best-first search, ini , pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah,
jika ternyata node pada lebih yang lebih tinggi ternyata memiliki nilai heuristik yang lebih buruk. Kemudian penentuan node berikutnya adalah node yang terbaikyang pernah dibangkitkan, yaitu dengan cara menngunakan informasi yamg terdiri atas biaya perkiraan dan biaya sebenarnya.
 Ada 2 jenis Pencarian Terbaik Pertama ( Best First Search), yaitu :
a.) Greedy Best First Search
 biaya perkiraan f(n) = h(n)
b.) A*
• biaya perkiraan + biaya sebenarnya
• f(n) = g(n) + h(n)
 Cara Untuk mengimplementasikan metode ini yaitu dengan menggunakan graph keadaan, dan dibutuhkan 2 antrian yang berisi node-node,yaitu:
- OPEN,* berisi node,node yang sudah dibangkitkan,namun belum diuji.
- CLOSED, * Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan nilai

heuristik tertinggi
* berisi node-node yang sudah diuji

 Algoritma:
1.) Pertama Tempatkan node awal A pada antrian OPEN.
2.) Kemudian Kerjakan langkah-langkah berikut hingga tujuan ditemukan atau antrian OPEN sudah kosong:
3.) Ambil node terbaik dari OPEN;
4.) Bangkitkan semua successornya;
5.) Untuk tiap-tiap successor kerjakan:
6.) Jika node tersebut belum pernah dibangkitkan sebelumnya,kemudian evaluasi node tersebut dan masukkan ke OPEN;
7.) Jika node tersebut sudah pernah dibangkitkan sebelumnya,setelah itu ubah parent jika lintasan baru lebih menjanjikan.dan langkah terakhir adalah hapus node tersebut dari antrian OPEN