Pencarian Buta : Teori dan Implementasi Breadth First Search pada Java

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. 

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 : 

1. Masukkan node akar (root) ke dalam queue
2. Ambil node dari awal antrian, lalu cek apakah node tersebut merupakan solusi
3. Jika node merupakan solusi, pencarian selesai dan hasil dikembalikan.
4. Jika node bukan solusi, masukkan node yang bertetangga dengan node tersebut (node anak) ke dalam queue 
5. Jika queue kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan
6. Ulangi pencarian dari langkah kedua. 

Implementasi Breadth First Search pada Java

untuk mengimplementasikan java pada BFS, saya menukil kodingannya Mark Watson dalam buku beliau Programming AI with Java. Beliau memberikan dua contoh penerapan BFS untuk pencarian jalur terpendek. 

1. Pencarian jalur terpendek pada game Maze 

2. Pencarian jalur terpendek pada simpul Graph

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. 

Teman-teman bisa mendownload source code implementasi BFS untuk game maze berikut ini :

BFS for Maze

Pencarian Jalur Terpendek pada Graph 

Titik awal adalah simpul 0 dan titik akhir adalah simpul 9, program secara otomatis akan mencari jalur terpendek dari simpul 0 menuju simpul 9 menggunakan metode BFS. Source code implementasi jalur terpendek pada graph menggunakan BFS bisa teman-teman download dan pelajari berikut ini :

BFS for Graph

Sekian semoga bermanfaat ya....