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.
2.1.
Generate and Test /
Pembangkit & Pengujian
Pembangkit & Pengujian : Pada prinsipnya metode
ini merupakan penggabungan antara depth-first search dengan pelacakan mundur
(backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.
Terdapat kelemahan dalam metode ini :
·
Perlu
membangkitkan semua kemungkinan sebelum dilakukan pengujian.
·
Membutuhkan
waktu yang cukup lama dalam pencariannya
Algoritma :
1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu
atau lintasan tertentu dari keadaan awal).
2. 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.
3. 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
2.2.
Hill Climbing
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.
Algoritma Simple Hill Climbing :
1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
2. Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang.
3. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
4. Evaluasi keadaan baru tersebut.
5. Jika keadaan baru merupakan tujuan, keluar.
6. Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
7. Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
2. Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang.
3. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
4. Evaluasi keadaan baru tersebut.
5. Jika keadaan baru merupakan tujuan, keluar.
6. Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
7. Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
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.
Algoritma Steepest Ascent Hill Climbing :
Steepest-ascent hill climbing
sebenarnya hampir sama dengan simple hill climbing, hanya saja gerakan
pencarian tidak dimulai dari posisi paling kiri. Gerakan selanjutnya dicari
berdasarkan nilai heuristik terbaik. Dalam hal ini urutan penggunaan operator
tidak menentukan penemuan solusi.
Sumber :
http://www.elangsakti.com/2013/03/bahasan-fundamental-tentang-blind.html
http://fryunfirst.blogspot.co.id/2015/06/pencarian-heuristik-heuristic-search.html
Tidak ada komentar:
Posting Komentar