Metode Pencarian Heuristik

Pencarian Heuristik

lMerupakan teknik yang digunakan untuk meningkatkan efisiensi dari proses pencarian

lDalam pencarian state space, heuristik adalah aturan untuk memilih cabang-cabang yang paling mungkin menyebabkan penyelesaian permasalahan dapat diterima

1.Generate and Test (Pembangkit dan Pengujian)

2.Hill Climbing (Pendakian Bukit)

3.Best First Search (Pencarian Terbaik Pertama)

Generate and Test

(Pembangkit dan Pengujian)

lPengabungan antara depth first

search dengan pelacakan mundur (backtracking)

lNilai Pengujian berupa jawaban ‘ya’ atau ‘tidak’

lJika pembangkit possible solution dikerjakan secara sistimatis, maka prosedur akan mencari solusinya, jika ada.

lLangkah – langkah:

l

Ø Bangkitkan suatu kemungkinan solusi

Ø

ØUji apakah node tersebut merupakan solusi, dengan cara membandingkan node atau node akhir suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan

Jika solusi ditemukan, keluar. Jika tidak, ulangi langkah pertama

Hill Climbing

(Pendakian Bukit)

lHampir sama Generate and Test, perbedaan terjadi pada feedback dari prosedur test untuk pembangkitan keadaan berikutnya.

lTes yang berupa fungsi heuristik akan menunjukkan seberapa baik nilai terkaan yang diambil terhadap keadaan lain yang mungkin

Prosedur Hill Climbing

l1. Buatlah solusi usulan pertama dengan cara yang sama seperti yang dilakukan dalam prosedur buat dan uji (generate and test). Periksalah apakah solusi usulan itu merupakan sebuah solusi. Jika ya, berhentilah. Jika tidak, kita lanjutkan ke langkah berikutnya.

l2.Dari solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat sekumpulan solusi usulan yang baru.

3.Untuk setiap elemen kumpulan solusi tersebut,lakukanlah hal-hal berikut ini :

lKirimkanlah elemen ini ke fungsi uji. Jika elemen ini merupakan sebuah solusi, berhentilah.

lJika tidak, periksalah apakah elemen ini merupakan yang terdekat dengan solusi yang

ltelah diuji sejauh ini. Jika tidak, buanglah.

l l4.Ambilah elemen terbaik yang ditemukan di atas dan pakailah sebagai solusi usulan berikutnya. Langkah ini bersesuaian dengan langkah dalam ruang problema dengan arah yang muncul sebagai yang tercepat dalam mencapai tujuan.

l5.Kembalilah ke langkah 2.

Best-First Search

lMetode yang membangkitkan suksesor dengan mempertimbangkan harga (didapat dari fungsi heuristik tertentu) dari setiap node

l

lKombinasi dari BFS dan DFS

l

lPencarian dilakukan dengan melihat satu lintasan, dan memungkinkan untuk berpindah ke lintasan lain.

Fungsi Heuristik yang digunakan

f’ = g + h’

dimana :

lf’ = prakiraan cost dari initial ke goal

lg= cost dari initial state ke current state

lh’ = prakiraan cost dari current state ke goal state

l