METODE HEURISTIK SEARCH

HEURISTIK SEARCH

  Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun 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 & TEST

   Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu yang bergerak ke belakang menuju pada suatu keadaan awal. Contoh:

Tavelling Salesman Problem (TSP)

  Seorang salesman ingin mengunjungi kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setiap kota hanya boleh dikunjungi tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti berikut.

Contoh :

          a. Kasus 4 puzzle

          b. Kasus 8 puzzle

          c. Kasus Travelling Salesman Problem (TSP)

HILL CLIMBING

   Metode ini hamper sama dengan metode pembangkitan dan pengujian, hanya saja proses penguji 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 lainnya.

Contoh Penerapan Algoritma Simple Hill Climbing

Disini ruang keadaan berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi.

Gambar Metode Simple Hill Climbing dengan 6 Operator

   Operator yang akan kita gunakan adalah menukar urutan posisi 2 kota dalam suatu lintasan. Apabila ada kota dan kita ingin mencari kombinasi lintasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak :

Sehingga kalau ada 4 kota, kita bias memperoleh :

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