2. HEURISTIC
SEARCH / Pencarian Heuristik
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.
2.1.
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 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 :
a.
Kasus 4 puzzle (kotak permainan)
b.
Kasus 8 puzzle (kotak permainan)
c.
Kasus Travelling Salesman Problem (TSP)
2.2.
Hill Climbing / PENDAKIAN BUKIT
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:
1.
Tukar 1, 2 (menukar urutan posisi kota ke-1 dengan kota ke-2).
2.
Tukar 2, 3 (menukar urutan posisi kota ke-2 dengan kota ke-3).
3.
Tukar 3, 4 (menukar urutan posisi kota ke-3 dengan kota ke-4).
4.
Tukar 4, 1 (menukar urutan posisi kota ke-4 dengan kota ke-1).
5.
Tukar 2, 4 (menukar urutan posisi kota ke-2 dengan kota ke-4).
6.
Tukar 1, 3 (menukar urutan posisi kota ke-1 dengan kota ke-3).
Sumber :
karmila.staff.gunadarma.ac.id/Downloads/folder/0
Tidak ada komentar:
Posting Komentar