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).
- Metode Pencarian Buta (Blind Search)
Blind Search merupakan pencarian asal. Jika solusi sudah
ditemukan, maka pencarian akan dihentikan. Jika dibuat skemanya, pencarian buta
hanya mengenal 3 bagian yaitu [masalah]-[pencarian]-[solusi]. Blind search
tidak mempunyai atribut atau informasi tambahan.
Algoritma yang termasuk Blind search yaitu :
- Breath First Search (BFS)
- Depth First Search (DFS)
- Uniform Cost Search (UCS)
- Depth-Limited Search (DLS)
- Interative-Deeping Search (IDS)
- Bi-directional Search (BDS
- 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.
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)
1.2 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.
Keuntungannnya :
- Membutuhkan memori relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan
- Dan secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan, jadi jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya dengan cepat (waktunya cepat)
Kerugiannya :
- Memungkinkan tidak ditemukannya atau tidak adanya tujuan yang diharapkan, karena jika pohon yang dibangkitkan mempunyai level yang sangat dalam (tak terhingga) à tidak complete karena tidak ada jaminan akan menemukan solusi
- Hanya mendapat 1 solusi pada setiap pencarian, karena jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka DFS tidak menjamin untuk menemukan solusi yang paling baik à tidak optimal2.
Deskripsi
- P = Petani
- Sy = Sayuran
- K = Kambing
- Sg = Serigala
Ruang
Keadaan
- Untuk daerah asal dan daerah seberang digambarkan. (P, Sy, K, Sg)
Keadaan
Awal
- Daerah Asal = (P, Sy, K, Sg)
- Daerah seberang = (0, 0, 0, 0)
Tujuan
- Daerah Asal = (0, 0, 0, 0)
- Daerah seberang = (P, Sy, K, Sg)
Metode
Penyelesaian :
a. Berikut ini adalah algoritma BFS :
- Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi (goal node), maka stop.
- Jika Q kosong, tidak ada solusi. Stop.
- Ambil simpul v dari kepala (head) antrian, bangkitkan semua anak-anaknya. Jika v tidak mempunyai anak lagi, kembali ke langkah 2 . Tempatkan semua anak dari v di belakang antrian.
- Jika suatu simpul anak dari v adalah simpul solusi, maka solusi telah ditemukan, kalau tidak, kembali lagi ke langkah 2.
Menggunakan algoritma DFS :
- Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, maka stop.
- Jika Q kosong, tidak ada solusi. Stop.
- Ambil simpul v dari kepala (head) antrian. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2
- Bangkitkan semua anak dari simpul v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q. Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali lagi ke langkah 2.
2. Metode pencarian 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.
Dengan adanya teknik heuristic
search diharapkan bisa menyelesaikan permasalahan yang lebih besar. Fungsi dari
teknik heuristic search menggunakan suatu fungsi yang menghitung biaya
perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan. Contoh
aplikasi yang menggunakan fungsi heuristic : Google, Deep Blue Chess Machine.
2.1 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 :
- Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertendu dari keadaan awal).
- 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.
Pendekatan ini meliputi langkah–langkah
sebagai berikut :
- Buatlah/bangkitkan sebuah solusi yang memungkinkan. Untuk sebuah problema hal ini dapat berarti pembuatan sebuah titik khusus dalam ruang problema.
- Lakukan pengujian untuk melihat apakah solusi yang dibuat benar–benar merupakan sebuah solusi, dengan cara membandingkan titik khusus tersebut dengan goal-nya (solusi).
- Jika telah diperoleh sebuah solusi, langkah – langkah tersebut dapat dihentikan. Jika belum, kembalilah ke langkah pertama.
Kelemahan dari generate and test
adalah perlunya membangkitkan semua kemungkinan sebelum dilakukan pengujian,
serta membutuhkan waktu yang cukup lama dalam pencarian. Metode generate and test ini memang kurang efisien untuk masalah yang besar atau kompleks.
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.
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.
contoh kasusa dan penyelesaian :
Sebagai ilustrasi teknik pencarian simple
hill climbing digunakan contoh masalah TSP pada masalah generate and
test . Operator yang digunakan adalah operator yang dapat menghasilkan
kombinasi lintasan kota yang berbeda-beda, yaitu dengan cara menukar posisi
masing-masing kota. Untuk mempermudah penukaran posisi, kita cukup menukar
posisi 2 kota, operator untuk kombinasi lintasan dengan menukar posisi 2 kota
dapat dihitung dengan kalkulasi
Yaitu :
- (1,2) menukar posisi kota kesatu dan kedua
- (1,3) menukar posisi kota kesatu dan ketiga
- (1,4) menukar posisi kota kesatu dengan keempat
- (2,3) menukar posisi kota kedua dengan kota ketiga
- (2,4) menukar posisi kota kedua dengan keempat
- (3,4) menukar posisi kota ketiga dengan keempat
Penggunaan pengurutan operator harus konsisten,
tidak boleh berbeda tiap levelnya.
urutan penggunaan operator juga sangat
menentukan kecepatan dalam menemukan solusi.
Level 1 : (ABCD=10 > BACD =9)
buka node BACD tanpa harus mencek node yang
selevel dengan BACD.
Level 2 : node ABCD dilewati.
(BACD=9 = CABD=9) periksa node tetangga CABD
(BACD=9 < DABC=10) periksa node tetangga DABC
(BACD=9 < BCAD=10) periksa node tetangga BCAD
(BACD=9 < BDAC=10) periksa
node tetangga BDAC
(BACD=9 > BADC=6 ) buka node
BADC
Level 3 : (BADC=6 < ABDC=8)
periksa tetangga ABDC
(BADC=6 < DABC=8) periksa tetangga DABC
(BADC=6 < CADB=8) periksa tetangga CADB
(BADC=6 < BDAC=8) periksa tetangga BDAC
(BADC=6 <BCDA=9) periksa tetangga BCDA
(BADC=6 < BADC=9) selesai.
contoh 1, Generate and Test :
Contoh:
kasus 4 kota
Penyelesaian dengan metode Generate and Test :
Generate RandomPath berdasarkan jumlah kota
Generate candidates list menggunakan permutasi
Pengecekan Rute yang Valid
kesimpulan :
Rute dikatakan valid jika jalur yang dilalui tidak berjarak
0. Jika rute valid, maka jarak dihitung lalu dibandingkan untuk mendapatkan
jarak yang paling optimal.
Setiap rute yang valid akan dibandingkan dengan rute valid
lainnya guna mendapatkan rute terpendek yang merupakan solusi dari kasus
TSP-nya. Yang dalam hal ini dipecahkan menggunakan algoritma Generate &
Test.
Kelebihan dari algoritma ini adalah pencariannya yang
lengkap dan selalu menghasilkan solusi yang optimal. Sedangkan kekurangannya
adalah tidak cocok untuk data yang besar/banyak dan waktu pencariannya yang
lama sesuai dengan banyak datanya.
Sumber :
https://sytachoi.wordpress.com/2016/10/18/pert-4-metode-pencarian-dan-pelacakan/
http://yoosinhay.blogspot.co.id/2011/03/teknik-pencarian-perancangan.html
https://profhadibanoe.wordpress.com/2012/01/13/solusi-tsp-dengan-algoritma-generate-test/
http://anasdharmawan.blogspot.co.id/2016/11/blind-search_3.html
http://webcache.googleusercontent.com/search?q=cache:kepq4N2UeTUJ:omar_pahlevi.staff.gunadarma.ac.id/Downloads/files/31327/pertemuan%2B05.ppt+&cd=8&hl=en&ct=clnk&gl=id
Tidak ada komentar:
Posting Komentar