Materi 4, Pencarian

Pada pertemuan keempat, membahas mengenai pencarian..
Nah.. pada pencarian heuristik terdapat 4 macam metode nya yaitu:
1. Pembangkit & Pengujian (Generate and Test)
2. Pendakian Bukit (Hill Climbing)
3. Pencarian Terbaik Pertama (Best First Search)
4. Simulated Annealing

Nah pada pertemuan ini kami membahas metode 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

Kemudian metode ini dibagi menjadi 2:
Dalam pencarian Metode Best First ini, penentuan node berikutnya adalah node yang terbaik yang pernah dibangkitkan dengan menggunakan informasi. Informasi yang digunakan adalah

1. biaya perkiraan
2. biaya sebenarnya

Metode Best First dibagi lagi menjadi 2 jenis, yaitu :

1. Greedy Best First Search.

Algoritma ini Merupakan jenis Best First Search yang hanya mempertimbangkan harga perkiraan (estimated cost) yaitu f(n) = h(n). Sedangkan harga sesungguhnya tidak digunakan. Sehingga solusi yang dihasilkan tidak optimal. Algoritma greedy ini membentuk solusi langkah per langkah (step by step). Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.

biaya perkiraan f(n) = h(n)

2. Algoritma A*

Algoritma A* yang memperhitungkan gabuangan dua biaya, biaya sebenarnya dan biaya perkiraan atau f(n) = g(n) + h(n)

Biaya sebenarnya + Biaya Perkiraan

f(n) = g(n) + h(n)