Makalah Algoritma Breadth-First Search (BFS)

BAB I

PENDAHULUAN

1.1  Latar Belakang

Dalam ilmu komputer, sebuah algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Sebagian besar algoritma yang dipelajari oleh ilmuwan komputer adalah algoritma pencarian. Himpunan semua kemungkinan solusi dari sebuah masalah disebut ruang pencarian. Algortima pencarian brute-force atau pencarian naif/uninformed menggunakan metode yang sederhana dan sangat intuitif pada ruang pencarian, sedangkan algoritma pencarian informed menggunakan heuristik untuk menerapkan pengetahuan tentang struktur dari ruang pencarian untuk berusaha mengurangi banyaknya waktu yang dipakai dalam pencarian. Adapun dalam metode pencarian blind atau buta digunakan karena memang tidak ada informasi awal yang digunakan dalam proses pencarian. Algoritma Pencarian ini menggunakan Metode BFS, DFS, dll.

1.2  Rumusan Masalah

1.      Apa pengertian BFS ?

2.      Bagaimana algoritma BFS ?

3.      Bagaimana cara kerja BFS ?

1.3  Tujuan

Tujuan dari Pembuatan Makalah ini, antara lain agar :
1.      Mahasiswa mampu memahami apa itu pengertian BFS

2.      Mahasiswa mampu mengetahui algoritma BFS.

3.      Mahasiswa dapat mengetahui cara kerja BFS.

BAB II

PEMBAHASAN

2.1  Pengertian 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. Urutan proses searching BFS ditunjukkan dalam Gambar 2.1 adalah: A,B,C,D,E,F, ...

Gambar 1.1 : Diagram pohon dari BFS.

2.2  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

2.3  Penerapan BFS dalam Algoritma

Adapun penerapan BFS pada algoritma adalah sebagai berikut:

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

2.5 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

Gambar 1.2 : Rute perjalanan

Penjelasan Gambar :

1. Membangkitakan anak dari terminal Senen = Terminal blok M, Terminal Pulo Gadung, Terminal Manggarai
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).

BAB III

PENUTUP

3.1  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://solikhaton.blogspot.com/2014/08/makalah-membahas-tentang-algoritma.html

         

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

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