Heuristik adalah sebuah teknik yang
mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan
mengorbankan kelengkapan (completeness).
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 ini, 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.
Contoh algoritma Heuristic Search yaitu Generate and Test, Simple Hill Climbing, Steepest-Ascent Hill Climbing, Simulated Annealing, Greedy, Best-First Search, dan A* (A Star).
A. GENERATE and TEST (PEMBANGKITAN dan
PENGUJIAN)
Metode ini merupakan penggabungan antara depth-first
search dengan pelacakan mundur (backtracking), yaitu bergerak ke
belakang menuju pada suatu keadaan awal.
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 kali. Misalkan ada
4 kota dengan jarak antara tiap-tiap kota seperti gambar di bawah ini :
Penyelesaian dengan metode Generate and
Test
Alur pencarian dengan Generate and Test
Pencarian ke-
|
Lintasan
|
Panjang Lintasan
|
Lintasan Terpilih
|
Panjang Lintasan Terpilih
|
1
|
ABCD
|
19
|
ABCD
|
19
|
2
|
ABDC
|
18
|
ABDC
|
18
|
3
|
ACBD
|
12
|
ACBD
|
12
|
4
|
ACDB
|
13
|
ACBD
|
12
|
5
|
ADBC
|
16
|
ACBD
|
12
|
Dst…
|
B. 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 lainnyayang mungkin.
Algoritma Hill Climbing
2. Kerjakan langkah-langkah berikut sampai
solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan
pada keadaan sekarang :
- Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
- Evaluasi keadaan baru tersebut
- Jika keadaan baru merupakan tujuan, keluar
- Jika bukan tujuan, namun jika nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut sebagai keadaan sekarang
- Jika keadaan baru tidak lebih baik dari sekarang, lanjutkan iterasi
Contoh TSP
• Operator : Tukar kota ke-i dengan kota ke-j (Tk i,j)
• Untuk 4 kota:
– Tk 1,2 : tukar kota ke-1 dengan kota ke-2.
– Tk 1,3 : tukar kota ke-1 dengan kota ke-3.
– Tk 1,4 : tukar kota ke-1 dengan kota ke-4.
– Tk 2,3 : tukar kota ke-2 dengan kota ke-3.
– Tk 2,4 : tukar kota ke-2 dengan kota ke-4.
– Tk 3,4 : tukar kota ke-3 dengan kota ke-4.
• Untuk N kota, akan ada operator sebanyak:
Sumber :
http://www.elangsakti.com/2013/03/bahasan-fundamental-tentang-blind.html
http://wisatapikiran.blogspot.co.id/2013/03/perbedaan-blind-search-dengan.html
https://aiukswkelasgkelompok7.wordpress.com/metode-pencarian-dan-pelacakan/