Pencarian buta merupakan sekumpulan prosedur yang digunakan dalam melacak ruang keadaan. Pencarian berlangsung sampai solusi terakhir ditemukan. Idenya adalah menguji seluruh kemungkinan yang ada untuk menemukan solusi.
1. Pencarian Melebar Pertama (Breadth-First Search).
Pada
metode Breadth-First Search, semua node pada level n akan dikunjungi terlebih
dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari
node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level
berikutnya demikian pula dari kiri ke kanan sampai ditemukannya solusi.
Contoh :
jika
dicari bagaimana jalur dari kota a menuju kota k, maka sistem akan menjelajahi
setiap node hingga menemui titik kota k, sehingga hasil pencarian jalur
terpendeknya adalah : a - b - c - d - e - f - g - h - i - j - k.
2. Depth
First Search.
proses pencarian akan dilaksanakan pada semua anaknya sebelum
dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar
ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukannya
solusi.
Contoh :
Berdasarkan
teori DFS, yang dicari berawal simpul terdalam / paling awal terlebih dahulu.
Setelah itu merambat satu-persatu ke simpul paling ujung. Jadi model
pnecariannya adalah menurun.
Metode
pencarian heuristik.
Merupakan
teknik yang digunakan untuk meningkatkan efisiensi dari proses pencarian Dalam
pencarian state space, heuristik adalah aturan untuk memilih cabang-cabang yang
paling mungkin menyebabkan penyelesaian permasalahan dapat diterima.
1. Metode
Generate-and-Test
Yaitu metode yang paling sederhana dalam pencarian
heuristic. Jika pembangkitan possible solution dikerjakan secara sistematis,
maka prosedur akan mencari solusinya, jika ada. Tetapi jika ruang masalahnya
sangat luas, mungkin memerlukan waktu yang sangat lama.
Contoh : Travelling Salesman Problem.
Seorang
salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui.
Ingin diketahui rute terpendek dimana setiap kota hanya boleh dikunjungi tepat
1 kali.
Generate
& test akan membangkitkan semua solusi yang mungkin:
2. Metode
Pendakian Bukit (Hill Climbing)
yaitu Salah satu metode generate and test
dimana umpan balik yang berasal dari prosedur uji digunakan untuk memutuskan
arah gerak dalam ruang pencarian. Fungsi uji hanyalah ya atau tidak.
Contoh
: menyelesaikan Number Puzzle Slider dengan kondisi tertentu menggunakan Simple
Hill Climbing
menyelesaikan
Number Puzzle Slider dengan kondisi teh(n) adalah nilai total heuristik dari
kondisi puzzle. Bernilai 0 untuk posisi yang benar dan untuk posisi yang salah
nilainya adalah jarak terpendek menuju posisi benar. Proses evaluasi yang
dilakukan selalu mengambil nilai heuristik terkecil
Sumber :
http://www.elangsakti.com/2013/02/implementasi-algoritma-depth-first.html
http://tioramadhani.blogspot.co.id/2015/04/algoritma-metode-pencarian-buta.html
http://www.charisfauzan.net/2015/01/pencarian-buta-teori-dan-implementasi.html
0 comments:
Post a Comment