Heuristic Search
Heuristic Search adalah
pencarian bersyarat (terbimbing). Artinya, solusi yang diperoleh adalah solusi
yang terbaik, bukan solusi sekali ketemu. Bagian-bagiannya adalah [masalah]-[pencarian]-[syarat]-[solusi].
Misal contoh masalah pada kasus di atas, Ambillah kelereng merah yang tidak
pecah dan tidak lonjong. Sehingga ketika ketemu kelereng merah dan ada
pecahnya, itu masih bukan solusi karena tidak sesuai dengan syarat (tidak pecah
dan tidak lonjong).
Fungsi heuristik digunakan untuk
mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh
hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Generate & Test
Metode ini merupakan penggabungan antara depth-first
search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju
pada suatu keadaan awal. Algoritma:
Bangkitkan suatu kemungkinan solusi (membangkitkan
suatu tititk tertentu atau lintasan tertentu dari keadaan awal).
Uji untuk melihat apakah node tersebut benar-benar
merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari
suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.
Jika solusi ditemukan, keluar. Jika tidak, ulangi
kembali langkah pertama.
Contoh :
“Travelling Salesman Problem (TSP)” Seorang salesman
ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita
ingin mengetahui ruter terpendek dimana setaip kota hanya boleh dikkunjungi
tepat 1 kal i. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota
seperti gambar di bawah ini:
Penyelesaian dengan metode Generate and Test
Hill Climbing.
Metode Hill Climbing hampir sama dengan metode
pembangkitan & pengujian (Generate and Test), hanya saja proses pengujian
dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya
sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa
fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil
terhadap keadaan-keadaan lainnya yang mungkin.
Hill Climbing adalah proses pengujian yang dilakukan
dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat
tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi
heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil
terhadap keadaan-keadaan lainnya yang mungkin.
Contoh: TSP dengan Simple Hill Climbing.
Disini ruang keadaan berisi semua kemungkinan
lintasan yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang
bersebelahan. Apabila ada n kota, dan kita ingin mencari kombinasi l intasan
dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak:
atau sebanyak 6 kombinasi (lihat gambar dibawah).
Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi.
Tidak ada komentar:
Posting Komentar