A. Breadth First Search
Definisi
Breadth First Search merupakan salah satu dari metode pencarian buta. Mengapa dikatakan pencarian buta ? istilah buta disini lebih dikenal dengan nama blind. Dikatakan buta karena memang tidak ada informasi awal yang digunakan dalam proses pencarian.
Breadth First Search (BFS) juga memiliki alur algoritma yang paling sederhana dibandingkan dengan metode blind yang lain. Itulah alasan mengapa BFS selalu dipelajari lebih dulu ketika membahas masalah pencarian buta.
Sebelum menelaah lebih jauh bagaimana metode BFS dijalankan, kita telisik dulu mengapa metode ini dinamakan pencarian Breadth First. Breadth dapat diartikan dengan luas / lebar, sedangkan first adalah pertama. Jadi, Breadth First adalah lebar pertama, apa maksudnya? Penamaan metode ini disesuaikan dengan konsep algoritma secara garis besar yaitu melakukan proses pencarian pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses pencarian pada node di level berikutnya.
BFS akan mencari satu per satu node secara melebar dari kiri ke kanan secara berurutan berdasarkan tingkat level nodenya. Jika pada satu level belum ditemukan solusi yang diinginkan, maka pencarian dilanjutkan hingga level berikutnya. Demikian seterusnya hingga ditemukan solusi. Maka, dengan cara seperti ini, BFS menjamin ditemukannya solusi apabila solusinya memang ada.
Contoh
Seperti pada gambar, 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 . Contoh lain seperti gambar dibawah ini :
Gambar a : Tentukan jalur terpendek dari simpul 1 hingga kembali ke simpul 1 lagi. !
Gambar b : Tentukan rute dari node 1 hingga node 7 !
Gambar c : Tentukan lintasan terpendek dari kota 1 ke kota 8 !
Maka, solusi yang ditemukan adalah :
Gambar a : 1 - 2 - 3 - 4 - 5 - 6 - 7 - 1
Gambar b : 1 - 2 - 3 - 4 - 5 - 6 - 7
Gambar c : 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8
Dalam implementasinya pada program, maka setiap node yang telah dikunjungi harus dimasukkan dalam sebuah queue (antrian) sebagai tempat menampung urutan node tahap demi tahap. untuk memperjelas bagaimana alur algoritmanya, berikut langkah-langkahnya :
- Masukkan node akar (root) ke dalam queue
- Ambil node dari awal antrian, lalu cek apakah node tersebut merupakan solusi
- Jika node merupakan solusi, pencarian selesai dan hasil dikembalikan.
- Jika node bukan solusi, masukkan node yang bertetangga dengan node tersebut (node anak) ke dalam queue
- Jika queue kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan
- Ulangi pencarian dari langkah kedua.
B. Depth First Search
Definisi
Pada algoritma DFS, pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang di kiri dapat dihapus dari memori. Jika pada level yang paling dalam belum ditemukan solusi, maka pencarian dilanjutkan ke level sebelumnya. Demikian seterusnya sampai ditemukannya solusi. Jika solusi ditemukan, maka tidak diperlukan proses backtracking (penelusuran untuk mendapatkan jalur yang diinginkan). Beberapa kelebihan dari algoritma DFS adalah pemakaian memori hanya sedikit karena hanya menyimpan lintasan yang aktif saja. Selain itu kelebihannya adalah jika solusi berada pada level yang paling dalam dan paling kiri, maka DFS akan menemukannya secara cepat. Misal suatu ruang keadaan masalah ditunjukkan dengan suatu seperti gambar berikut ini.
Contoh
Dalam pencarian menggunakan algoritma DFS, simpul-simpul yang paling dalam pada tree yang akan di cari paling awal. Sebagai contoh pada Gambar di atas. Urutan pencarian keadaan awal (S) sampai keadaan tujuan (G) adalah dimulai dari node S, kemudian ke node A, kemudian ke node B, kemudian ke node C, setelah itu akan melewati node B kembali dan menuju ke node E, selanjutnya akan menuju node D, setelah itu akan menuju node F setelah melewati node E, dan yang terakhir akan menuju node G.
kombinasi.
