my blog varian: HEURISTIC SEARCH

Definisi

merupakan metode pencarian yang memperhatikan nilai heuristik (nilai perkiraan).
Teknik pencarian heuristik (heuristic searching) merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu.
Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness).
Heuristic Search memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik). Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

Jenis-jenis dari Heuristic Search:

· Generate and Test

· Hill Climbing

· Best First Search

A. Generate and test

Strategi bangkitkan dan uji (generate and test) merupakan pendekatan yang paling sederhana dari semua pendekatan yang akan dibicarakan.
Pendekatan ini meliputi langkah–langkah sebagai berikut :

Buatlah/bangkitkan sebuah solusi yang memungkinkan. Untuk sebuah problema hal ini dapat berarti pembuatan sebuah titik khusus dalam ruang problema.
Lakukan pengujian untuk melihat apakah solusi yang dibuat benar–benar merupakan sebuah solusi, dengan cara membandingkan titik khusus tersebut dengan goal-nya (solusi).
Jika telah diperoleh sebuah solusi, langkah – langkah tersebut dapat dihentikan. Jika belum, kembalilah ke langkah pertama.

Jika pembangkitan atau pembuatan solusi – solusi yang dimungkinkan dapat dilakukan secara sistematis, maka prosedur ini akan dapat segera menemukan solusinya (bila ada). Namun, jika ruang problema sangat besar, maka proses ini akan membutuhkan waktu yang lama.
Metode generate and test ini memang kurang efisien untuk masalah yang besar atau kompleks.

Contoh

A,B,C,D merupakan sebuah pos untuk dilalui dengan jalur yang memiliki nilai berbeda, setiap pos hanya boleh dilalui satu kali setiap perjalanan dengan suatu masalah berupa mencari perjalanan ke seluruh pos yang memiliki nilai paling kecil.

A-B-C-D : 8+5+6= 19

A-C-B-D : 3+5+4=12

A-D-B-C : 7+4+5=16

A-D-C-B : 7+6+5=18

Maka dari algoritma diatas solusi yang diambil adalah rute A-C-B-D

Kelemahan

· Perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian

· Membutuhkan waktu yang cukup lama dalam pencariannya

B. Hill Climbing

Merupakan 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.

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 lintasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak n ! / 2 ! ( n – 2 ) !

C. Best First Search

Pencarian terbaik pertama (Best First Search) merupakan suatu cara yang menggabungkan keuntungan atau kelebihan dari pencarian Breadth-First Search dan Depth-First Search.
Pada setiap langkah proses pencarian terbaik pertama, kita memilih node-node dengan menerapkan fungsi heuristik yang memadai pada setiap node/simpul yang kita pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan penggantinya.

Contoh:

Misalkan kita memiliki ruang pencarian seperti pada gambar berikut. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengannode A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di node A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara node n dengan node tujuan (jalan buntu). Kita bisa merunut nilai untuk setiap node.