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. Misalkan dalam kotak ada 3 kelereng warna merah, 3 biru, dan 3 kuning. Masalahnya adalah, ambillah satu kelereng yang berwarna merah. Solusi, setelah melakukan pencarian, kemudian didapat satu kelereng warna merah, nah, itulah solusinya.
ciri2 Blind Search :
- Membangkitkan
simpul berdasarkan urutan.
- Kalau ada
solusi, solusi akan ditemukan.
- Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).
BREADTH FIRST SEARCH
Algoritma Breadth-First Search (BFS) atau dikenal juga dengan nama algoritma pencarian melebar adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1.Algoritma ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpul-simpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungi masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang telah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.Breadth-first search (BFS) melakukan proses searching pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya.
Keterangan :
- 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 hingga di temukan solusi.
KELEBIHAN :
- Tidak akan menemui jalan buntu, menjamin ditemukannya solusi (jika solusi memang ada) dan solusi yang ditemukan pasti solusi yang baik.
- Jika ada 1 solusi maka breadth first search akan menemukannya.
- Jika ada lebih dari 1 solusi, maka solusi minimum akan ditemukan.
KELEMAHAN :
- Membutuhkan memori yang banyak, karena harus menyimpan semua simpul yang pernah di bangkitkan dan hal ini harus dilakukan agar BFS dapat melakukan penulusuran simpul-simpul sampai di level bawah.
- Membutuhkan waktu yang cukup lama.
KESIMPULANNYA :
- Completeness : Dimana teknik yang digunakan adanya solusi.
- Optimality : Dimana teknik yang digunakan menemukan solusi yang terbaik saat adanya beberapa solusi berbeda.
- Time Complexity : Waktu yang di butuhkan cukup lama.
- Space Complextity : Memori yang dibutuhkan juga banyak.
CONTOH :
Pencarian jalur terpendek pada game maze.
Game maze adalah game yang mengharuskan user untuk menemukan
jalan keluar dan melewati banyak halangan (obstacle) dari sebuah ruang yang mirip
labirin. Titik awalnya dimulai dari huruf S (Start) dan diakhiri pada kotak
bertuliskan G (Goal). Ketika program dijalankan, sistem akan otomatis mencari
rute terpendek dari kotak S menuju kotak G menggunakan metode BFS. Panjang rute
hasil pencarian dituliskan dalam bentuk angka disetiap kotak.
Cukup sekian ilmu yang telah saya berikan, terima kasih kepada sumber sumber yang telah membantu saya.
Sumber :
Tidak ada komentar :
Posting Komentar