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).
1. Metode Pencarian Buta
1.1 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.
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 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.
2. Pecarian Heuristik
Pencarian buta tidak selalu dapat diterapkan dengan baik
- Waktu aksesnya yang cukup lama
- Besarnya memori yang diperlukan
- Metode heuristic search diharapkan bisa menyelesaikan permasalahan yang lebih besar.
- Metode heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan disebut fungsi heuristic
- Aplikasi yang menggunakan fungsi heuristic : Google, Deep Blue Chess Machine
Pada prinsipnya metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.
Algoritma:
- Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal).
- Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.
- Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.
2.2. 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 :
Mulai dari keadaan awal, jika merupakan tujuan, maka berhenti; tapi jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
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.
sumber :
https://yanneevelynip.wordpress.com/2013/10/20/metode-pencarian-dan-pelacakan-kecerdasan-buatan/
http://buatugasai.blogspot.co.id/2013/04/metode-pencarian-dan-pelacakan_4.html
Tidak ada komentar:
Posting Komentar