MATERI 4

PENCARIAN

Materi ini membahas lanjutan dari materi sebelumnya,di materi ini kita akan membahas lebih dalam tentang Pencarian Heuristik

PENCARIAN

Ada empat metode pencarian heuristik :

• Pembangkit dan Pengujian (Generate & Test)
• Pendakian Bukit (Hill Climbing)
• Pencarian terbaik pertama (Best First Search)
• Simulated Annealing

Pencarian terbaik pertama (Best First Search)
Pengertian : Metode best-first search ini merupakan kombinasi dari metode depth-first search dan metode breadth-first search dengan mengambil kelebihan dari kedua metode tersebut.
1. Penentuan node berikutnya adalah node yang terbaik yang pernah di bangkitkan
2. Menggunakan informasi

• Biaya perkiraan
Biaya sebenarnya

3. Terdapat dua jenis

• Greedy Best First Search = biaya perkiraan f(n)=h(n)
• A* = f(n)=g(n) + h(n)

Keuntungan :

• Memperbolehkan kembali ke node pada level lebih rendah meskipun node pada level terendah tersebut memiliki nilai heuristik lebih rendah

Untuk mengimplementasikan metode ini menggunakan graph keadaan,dibutuhkan 2 antrian yang berisi node-node yaitu :

• OPEN,Merupakan node yang telah dibangkitkan namun belum di uji
• CLOSED,Merupkan node yang telah di bangkitkan dan telah di uji

ALGORITMA

• Tempatkan node awal A pada antrian OPEN
• Kerjakan langkah-langkah berikut hingga tujuan ditemukan atau antrian OPEN sudah kosong :
• Ambil node terbaik dari OPEN
• Bangkitkan semua successornya
• Untuk tiap-tiap successor kerjakan :
• Jika node tersebut belum pernah dibangkitkan sebelumnya,evaluasi node tersebut dan masukkan ke OPEN;
• Jika node tersebut sudah pernah dibangkitkansebelumnya,ubah parent jika lintasan baru lebih menjanjikan.Hapus node tersebut dari antrian OPEN.