Pencarian Heuristik
Ada 4 metode pencarian heuristik
· Pembangkit & Pengujian (Generate and Test)
· Pendakian Bukit (Hill Climbing)
· Pencarian Terbaik Pertama (Best First Search)
· Simulated Annealing
Pencarian Terbaik Pertama
(Best First Search)
ü Metode best-first search ini merupakan kombinasi dari metode depth-first search dan metode breadth-first search dengan mengambil kelebihan dari kedua metode tersebut.
ü Apabila pada pencarian dengan metode hill climbing tidak diperbolehkan untuk kembali ke node pada level yang lebih rendah meskipun node pada level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik, lain halnya dengan metode best-first search ini.
ü Pada metode best-first search, 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.
ü Penentuan node berikutnya adalah node yang terbaik yang pernah dibangkitkan
ü Menggunakan informasi :
o Biaya perkiraan
o Biaya sebenarnya
ü Terdapat 2 jenis :
1. Greedy Best First Search
a. Biaya perkiraan f(n) = h(n)
2. A*
a. f(n) = g(n) + h(n)
b. Untuk mengimplementasikan metode ini menggunakan graph keadaan, dibutuhkan 2 antrian yang berisi node-node yaitu:
o OPEN, berisi node,node yang sudah dibangkitkan, namun belum diuji. Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan nilai heuristik tertinggi.
o CLOSED berisi node-node yang sudah diuji
ü Algoritma:
o Tempatkan node awal A pada antrian OPEN.
o Kerjakan langkah-langkah berikut hingga tujuan ditemukan atau antrian OPEN sudah kosong.
o Ambil node terbaik dari OPEN
o Bangkitkan semua successornya
o Untuk tiap-tiap successor kerjakan
o Jika node tersebut belum pernah dibangkitkan sebelumnya, evaluasi node tersebut dan masukkan ke OPEN
o Jika node tersebut sudah pernah dibangkitkan sebelumnya, ubah parent jika lintasan baru lebih menjanjikan. Hapus node tersebut dari antrian OPEN
