Metode Pencarian dan Pelacakan

               Pencarian dan pelacakan merupakan suatu hal penting dalam suatu sistem. Karena pencarian dan pelacakan ini adalah hal yang menentukan keberhasilan sistem tersebut. Pada dasarnya, metode pencarian dan pelacakan dibagi dua, yaitu pencarian buta (blind search) dan pencarian tersusun (heuristic search).

• Pencarian Buta
• Pencarian Melebar Pertama (breadth-search first)

                                    Pencarian melebar pertama dilakukan dengan melakukan pencarian dengan cara mencari yang dilakukan dengan cara melebar dari node pertama hingga berlanjut kepada node di level selanjutnya. Dimulai pada node n, dan dilanjutkan n+1. Pencarian akan terus dilakukan dari akar kiri ke kanan hingga hasil ditemukan.

                                    Metode ini memiliki keuntungan dan kekurangan, yaitu :

• Keuntungan
• Tidak akan menemui jalan buntu
• Jika ada satu solusi, maka breadth first akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.

• Kekurangan
• Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.
• Membutuhkan waktu yang cukup lama karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1)

• Pencarian Mendalam Pertama (depth-search first)

                                    Pencarian metode ini melakukan pencarian pada semua node "anaknya" sebelum dilakukan pencarian ke node-node lain yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi, dan proses terus diulang hingga solusi ditemukan. Keuntungan dari metode ini adalah menggunakan memori yang relatif kecil, dan jika pencarian tepat, akan menemukan solusi tanpa harus menguji lebih banyak node. Namun, metode ini tetap memiliki kelemahan, yaitu memungkinkan hasil tidak ditemukan, dan setiap 1 kali pencarian hanya akan menghasilkan satu solusi.

• Pencarian Tersusun

                           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.

• Best first search

 Metode ini adalah kombinasi dari metode depth-search first dan metode breadth-search first dengan mengambil kelebihan keduanya. Ketika pada hill climbing tidak diperkenankan untuk kembali ke node sebelumnya, pada metode ini diijinkan jika ternyata node yang lebih tinggi memiliki nilai heuristik yang lebih buruk.

• Simulated annealing

Metode ini terbentuk dari pemrosesan logam. Annealing (memanaskan kemudian mendinginkan) ini adalah proses bagaimana membuat bentuk cair berangsur-angsur menjadi bentuk yang lebih padat seiring dengan penurunan temperatur. Biasanya, simulated annealing digunakan pada sistem yang sangat luas.


Sumber :
http://www.slideshare.net/ceezabramovic/metode-pencarian-heuristik
http://www.scribd.com/doc/52500558/Metode-Pencarian-Dan-Pelacakan-prolog
http://lecturer.eepis-its.edu/~entin/Kecerdasan%20Buatan/Buku/Bab%204%20Algoritma%20Pencarian.pdf
http://aq-destri.blogspot.com/2010/12/pencarian-heuristik-heuristic-search.html
http://rolliawati.dosen.narotama.ac.id/files/2012/09/teknik-pencarian-heuristik3.pdf
http://elib.unikom.ac.id/files/disk1/483/jbptunikompp-gdl-dewinurulr-24110-4-unikom_d-i.pdf