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).
v 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
a) Tidak akan
menemui jalan buntu
b) Jika ada
satu solusi, maka breadth first akan menemukannya. Dan jika ada lebih dari satu
solusi, maka solusi minimum akan ditemukan.
Ø Kekurangan
a) Membutuhkan
memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.
b) 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.
v Pencarian
Tersusun (Heuristik)
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.
Riyadi Wicaksono 19114555
Bagas Wicaksono 11114977
Riyadi Wicaksono 19114555
Bagas Wicaksono 11114977
