Pencarian Heuristik
(Heuristic Search)
• Heuristik
adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum
dengan kemungkinan mengorbankan kelengkapan (completeness).
• Fungsi
heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan
menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi
yang diinginkan.
(Generate and Test)
Metode ini merupakan
penggabungan antara depth-first search dengan pelacakan mundur
(backtracking) , yaitu bergerak ke belakang menuju pada suatu keadaan
awal.
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 kali.
Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti berikut ini :
Penyelesaian dengan metode Generate
and Test
Alur pencarian dengan Generate
and Test
Contoh :
Kasus 4 puzzle (kotak permainan)
b. Kasus 8 puzzle (kotak permainan)
c. Kasus Travelling Salesman
Problem (TSP)
PENDAKIAN BUKIT
(Hill Climbing)
Metode ini hampir sama
dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan
dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung
pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini
akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap
keadaan-keadaan lain nya yang mungkin.
Contoh Penerapan
Algoritma Simple Hill Climbing
Salah satu contoh dari
penerapan Algoritma Simple Hill Climbing adalah Traveling Salesman Problem.
Disini ruang keadaan
berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk
menukar posisi kota-kota yang bersebelahan. Fungsi heuristik yang digunakan
adalah panjang lintasan yang terjadi.
Gambar Metode Simple
Hill Clibing Dengan 6 Operator
Operator yang akan
kita gunakan, adalah menukar urutan posisi 2 kota dalam suatu lintasan. Apabila
ada n kota, dan kita ingin mencari kombinasi lintasan dengan menukar posisi
urutan 2 kota, maka kita akan mendapatkan sebanyak :
Sehingga kalau ada 4
kota, kita bisa memperoleh :
kombinasi.
Keenam kombinasi ini
akan kita pakai semuanya sebagai operator, yaitu:
- Tukar 1, 2 (menukar urutan
posisi kota ke-1 dengan kota ke-2).
- Tukar 2, 3 (menukar urutan
posisi kota ke-2 dengan kota ke-3).
- Tukar 3, 4 (menukar urutan
posisi kota ke-3 dengan kota ke-4).
- Tukar 4, 1 (menukar urutan
posisi kota ke-4 dengan kota ke-1).
- Tukar 2, 4 (menukar urutan
posisi kota ke-2 dengan kota ke-4).
- Tukar 1, 3 (menukar urutan
posisi kota ke-1 dengan kota ke-3).
Sumber:
karmila.staff.gunadarma.ac.id/Downloads/folder/0
Komentar
Posting Komentar