PAPER Breadth-first search
By:
> Muhammad Zamroni Hamzah
(100411100085)
> Moh.
Zein Saedi
(100411100034)
> Yusuf
Machsar
(100411100026)
> Moh.
Aminur Rosyid
(100411100021)
RANCANGAN
ANALISIS ALGORITMA
Teknik
Informatika
Fakultas Teknik
Universitas
Trunojoyo Madura
2012
Breadth-first search
Breadth-first search
PENGERTIAN
ALGORITMA BFS
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
memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi.
Simpulsimpul 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.
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:
Masukkan simpul
ujung (akar) ke dalam antrian
Ambil simpul
dari awal antrian, lalu cek apakah simpul merupakan solusi
Jika simpul
merupakan solusi, pencarian selesai dan hasil dikembalikan.
Jika simpul
bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut
(simpul anak) ke dalam antrian
Jika antrian
kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil
solusi tidak ditemukan
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, 1
Gambar (c)
BFS(1): 1, 2, 3, 4, 5, 6, 7, 8, 9
2. CONTOH PENCARIAN LINTASAN TERPENDEK
DENGAN BFS
Adapun contoh
untuk mencari lintasan terpendek dengan menggukan algoritma BFS adalah sebagai
berkut:
Diketahui sebuah
kota, dengan memiliki inisial seperti yang ditunjukkan dibawah ini. Jarak antar
kota dibentuk dengan sebuah graph terlihat dibawah:
Pertanyaan:
sebutkan rute yang akan ditempuh untuk mencapai kota no. 8. Titik awal
perjalanan adalah kota no. 1. Gunakan algoritma BFS!
Maka dengan
menggunakan algoritma BFS, rute tercepat yang didapat adalah sebagai berikut:
1 – 2 – 3 – 4 –
5 – 6 – 7 – 8
Rute tersebut
didapat dari pencarian secara melebar. Hal; tersebut dapat dijabarkan sebagai
berikut:
- Pertama-tama, pointer menunujuk pada
daun yang ada sebelah kanan, yaitu no.2 (1 – 2)
- Setelah itu, proses dilanjutkan pada
tetangga no.2 yaitu no.3 (1-2-3) dan selanjutnya mengarah pada tetangga
terdekat, yakni no.4 (1-2-3-4).
- Pointer mencari teteangga no.4, namun
karna tidak ada, maka pointer kembali ke kota no.2 dan masuk ke daun berikutnya,
yakni no.5.
- Proses diulang hingga pointer
menunjuk angka 8
Ilustrasi BFS
• Deskripsi keadaan
• Pointer ke
parent
• Kedalaman
simpul
• Operator yang
membuka simpul ini
• Biaya total
dari simpul awal sampai simpul ini
-Root node
-Leaf node
-Branching
factor
-Ancestor /
descendant
-Path
-Level
Ambil fringe
sebagai list berisi keadaan awal
Loop
if fringe kosong return failure
Node ß remove-first (fringe)
if Node is a goal
then return jalur dari keadaan awal sampai Node
else buka semua suksesor Node, dan
(satukan Nodes
baru ke dalam fringe)
tambahkan Nodes
baru ke akhir fringe
End Loop
Algoritma BFS
merupakan mekanisme pencarian sebuah simpul pada graf dengan cara memulai
pencarian pada sebuah simpul dan kemudian mengunjungi semua
simpul yang
bertetangga dengan simpul awal dan baru kemudian semua simpul yang belum
dikunjungi yang bertetanggaan dengan simpul-simpul yang tadi dikunjungi.
Algoritma BFS
memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi.
Simpul-simpul yang telah dikunjungi suatu saat diperlukan sebagai acuan
untuk
mengunjungi simpul-simpul yang bertetangga dengannya. Tiap simpul yang telah
dikunjungi masuk ke dalam antrian hanya satu kali.[1] Algoritma BFS memerlukan
tabel Boolean yang bernama Dikunjungi untuk menyimpan simpul yang telah
dikunjungi agar tidak ada simpul yang dikunjungi lebih dari sekali. Deklarasi
tabel tersebut di dalam kamus adalah [1] Deklarasi
Dikunjungi :
array[1..n] of
boolean
Dalam implementasinya, algoritma
BFS memerlukan matriks ketetanggaan A = [aij] yang berukuran n
× n,
antrean q untuk menyimpan
simpul yang telah dikunjungi dan tabel boolean dikunjungi. Pseudo-code
dari algoritma BFS adalah sebagai berikut:
Algoritma:
BuatAntrian(q) {
buat antrian kosong }
write(v) { cetak
simpul awal yang
dikunjungi }
dikunjungi[v]true
{ simpul v telahdikunjungi, tandai dengan true}
MasukAntrian(q,v) {
masukkan simpulawal kunjungan ke dalam antrian}
{ kunjungi semua
simpul graf selamaantrian belum kosong }
while not
AntrianKosong(q) do
HapusAntrian(q,v) {
simpul v telahdikunjungi, hapus dari antrian }
for wl to n do
if A[v,w] = 1 then
{ v dan w bertetangga }
if not
dikunjungi[w] then
write(w) {cetak
simpul
yang dikunjungi}
MasukAntrian(q,w)
dikunjungi[w]true
endif
endif
endfor
endwhile
{ AntrianKosong(q)
}
{[1]}
|
Kompleksitas waktu algoritma BFS:
Asumsi: setiap
simpul dapat membangkitkan b buah simpul
baru. Misalkan solusi ditemukan pada aras ke-d Jumlah maksimum seluruh simpul:
1 + b + b2 + b3
+ ... + bd = (bd+1 – 1)/(b – 1)
T(n) =
O(bd).
Kompleksitas
ruang algoritma BFS = sama dengan kompleksitas waktunya, karena semua simpul
daun dari pohon harus disimpan di dalam memori
selama proses pencarian.
Keuntungan BFS :
-Menemukan jalur
solusi dengan jalur tersingkat, karena selalu mengambil lebar dari pohon
pencarian.
-Membutuhkan
memori yang relative kecil, karena hanya node-node pada lintasan yang aktif
saja.
-Secara
kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji
lebih banyak lagi dalam ruang keadaan.
Postingan
0 komentar:
Posting Komentar