Metode Pencarian (Heuristic Search)

Heuristic Search

Pencarian tersusun atau pencarian heuristik merupakan suatu teknik yang digunakan untuk meningkatkan efisiensi dalam proses pencarian. Metode heuristik menggunakan suatu fungsi yang menghitung biaya perkiraan dari suatu simpul tertentu menuju ke simpul tujuan. Dalam pencarian state space, heuristik adalah aturan untuk memilih cabang-cabang yang paling mungkin menyebabkan penyelesaian permasalahan dapat diterima.

• Generate and Test

Ini adalah gabungan dari pencarian depth first dengan pelacakan mundur. Nilai dari pengujian ini berupa "ya" atau "tidak". Pencarian ini memiliki beberapa algoritma, yaitu :

1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertendu dari keadaan awal).
2.  Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengancara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih merupakan tujuan yang diharapkan.

      Kelemahan dari generate and test adalah perlunya membangkitkan semua kemungkinan  sebelum dilakukan pengujian, serta membutuhkan waktu yang cukup lama dalam  pencarian.

•       Hill climbing

      Metode ini hampir sama dengan generate and test, perbedaannya ada pada feedback dari  prosedur test untuk pembangkitan keadaan berikutnya. Tes yang dilakukan berupa fungsi  heuristik akan menunjukkan seberapa baik nilai terkaan yang diambil terhadap keadaan  lain yang memungkinkan. Algoritma dari pencarian ini adalah :

1.       Mulai dari keadaan awal, jika merupakan tujuan, maka berhenti; tapi jika tidak,  lanjutkan dengan keadaan sekarang sebagai keadaan awal.
2.       Kerjakan langkah-langkah berikut hingga solusinya ditemukan, atau hingga tidak ada  lagi operator baru yang diaplikasikan pada keadaan sekarang :

•       Cari operator yang belum pernah digunakan sebagai operator untuk keadaan baru
•       Evaluasi keadaan baru tersebut
•       Jika keadaan baru adalah tujuan, keluar.
•       Jika bukan tujuan namun nilai lebih baik, keadaan baru akan digunakan sebagai  keadaan sekarang.
•       Jika  keadaan baru tidak lebih baik, maka lanjutkan interasi.

      Kelemahan pada sistem ini adalah algoritma akan berhenti ketika mencapai optimum  local, urutan penggunaan operator akan sangat berpengaruh, dan tidak diijinkan untuk  melihat langkah sebelumnya.

      Sumber :
      http://buatugasai.blogspot.co.id/2013/04/metode-pencarian-dan-pelacakan_4.html
      https://aiukswkelasgkelompok7.wordpress.com/metode-pencarian-dan-pelacakan/