Heuristic Search

Heuristic Search

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

1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.

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/