PENJELASAN MENGENAI ALGORITMA BREADTH-FIRST SEARCH (BFS)

 

Pengertian Algoritma Breadth First Search

    Breadth-first search  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 memerluka-n 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 dikunjungu masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali. Salah satu contoh kakas pencarian yang menggunakan metode BFS adalah WebCrawler. WebCrawler adalah suatu kakas yang membuat indeks isi dari suatu dokumen di Web yang selanjutnya akan dimanfaatkan oleh mesin pencari. Terdapat tiga langkah yang dilakukan oleh WebCrawler ini ketika mengunjungi dokumen, yaitu menandai bahwa suatu dokumen telah dikunjungi, mengenali link yang terdapat pada dokumen tersebut, kemudian isinya didaftarkan pada daftar indeks Pencarian dengan Breadth First Search menggunakan teknik dimana langkah pertamanya adalah root node diekspansi, setelah itu dilanjutkan semua successor dari root node juga di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf (node pada level paling bawah yang sudah tidak mempunyai successor lagi). 

       Pencarian dengan Breadth First Search akan menjadi optimal ketika nilai pada semua path adalah sama. Dengan sedikit perluasan, dapat ditemukan sebuah algoritma yang optimal dengan melihat kepada nilai tiap path di antara node-node yang ada. Selain menjalankan fungsi algoritma BFS, Uniform Cost Search melakukan ekspansi node dengan nilai path yang paling kecil. Hal ini bisa dilakukan dengan membuat antrian pada successor yang ada berdasar kepada nilai path-nya (node disimpan dalam bentuk priority queue).

Keuntungannya :

• 1. Tidak menemui jalan buntu.
• 2. Jika ada suatu solusi, maka Breadth-first search akan menemukannya. Dan jika didapat lebih dari satu solusi, maka solusi minimum akan ditemukan.

Kelemahannya :

• 1. Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam suatu pohon.
• 2. Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level ke-(n + 1).

Cara Kerja Algoritma BFS

    Dalam algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yang bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian.Untuk memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya, berikut langkah-langkah algoritma BFS:

 

1.   Masukkan simpul ujung (akar) ke dalam antrian.

2.   Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi.

3.   Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.

4.   Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian.

5.   Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan.

6.   Ulangi pencarian dari langkah kedua.

Contohnya terlihat dibawah ini:

Maka penyelesaiannya adalah:Gambar (a) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1.Gambar (b) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1Gambar (c) BFS(1): 1, 2, 3, 4, 5, 6, 7, 8, 9

 

Penerapan BFS dalam Algoritma

 Adapun penerapan BFS pada algoritma adalah sebagai berikut:

 

Keuntungan dan Kelemahan BFS

 

Keuntungan dari BFS adalah :

 

*Tidak akan menemukan jalan buntu.

 

* Tidak ada satu solusi, maka BFS search akan menemuknnya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.

 

Kelemahan dari BFS adalah :

 

* 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).

 

 Contoh kasus BFS

Berikut adalah contoh kasus dengan menggunakan metode BFS. Kita akan mencari jalur tujuan dengan menggunakan angkutan umum.Contoh :

Mencari jalur angkutan umum dari terminal senen ke terminal Kp. Rambutan

*        Initial State : Senen

*        Goal State : Kp. Rambutan

RUTE PERJALANAN

Penjelasan Gambar :

1. 1. Membangkitakan anak dari terminal Senen = Terminal blok M, Terminal Pulo Gadung, Terminal Manggarai
2. 2. Karena goal state (Terminal Kp. Rambutan) belum tercapai maka kita bangkitkan anak dari terminal senen

Terminal Blok M = Terminal Grogol, Terminal Lebak Bulus            

Terminal Lebak Bulus = Terminal Ciputat, Terminal Kp. Rambutan.            

Terminal Pulo Gadung = Terminal bekasi            

Terminal Manggarai = Terminal Cililitan, Terminal Harmoni

3. Akhirnya tercapai Goal State (Terminal Kp. Rambutan).

 

 

Kesimpulan

 

     Dari pembahasan diatas dapat ditarik kesimpulan yaitu :

ØBreadth-first search (BFS) melakukan proses searching pada semua node yang berada pada level atau hirarki tetangga yang terdekat terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya.

ØMetode BFS membutuhkan memori yang cukup banyak namun dengan menggunakan metode ini solusinya tidak akan menemukan jalan buntu.

 

 

 

 

 

DAFTAR PUSTAKA

http://en.wikipedia.org/wiki/Breadth-first_search

 

http://ww3.algorithmdesign.net/handouts/BFS.pdf

 

 

 

Tweet

Postingan terkait:

Ditulis blog_kami — Selasa, 06 Oktober 2020 — Add Comment