BFS (Breadth First
Search)
Latar
Belakang Masalah
1.
Pengertian
Breadth First Search (BFS)
2.
Cara
Kerja Breadth First Search (BFS)
3.
Pencarian
Lintasan Terpendek Dengan BFS
Isi
1.
Pengertian
Algoritma Breadth First Search
Breadth First Search (BFS) adalah sebuah
algoritma pencarian berupa graf yang dimulai dari node pangkal dan setelah itu
menjelajahi semua node yang jaraknya berdekatatan. Pencarian yang dilakukan
bertujuan untuk memeriksan dan juga memperluas semua node dari sebuah graf atau
kombinasi dari uutan dengan menggunakan solusi secara sistematis. Pencarian
soluasi dilakukan dengan mengunjungi ( melewati ) simpul-simpul grraf yang
telah tersedua ( dibentuk terlebih dahulu) sebelum pencarian solusinya.
Breadth First Search (BFS) memiliki
kelebihan dimana kelebihannya adalah dalam proses pencarian solusi kita tidak
akan menemui jalan buntu dan menjamin ditemukannya solusi (jika solusinya
memang ada ) dan solusi yang ditemukan pasti solusi yang paling baik. Dan BFS
juga memilikin kekurangan yaitu harus menyediakan memori yang cukup banyak dan
membutuhkan waktu yang lama dalam proses pengerjaannya.
2.
Cara
Kerja Breadth First Search (BFS)
Adapun Cara Kerja Breadth First Search
(BFS) adalah simpul anak yang telah dikunjungi disimpan dalam suatu antrian.
Berikut ad acara atau
langkah-langkah dalam pengerjaan atau penerapan algoritma BFS:
1. Masukkan simpul ujung (akar) ke dalam antrian.
2. Ambil simpul dari awal antrian, lalu
lakukan pengecekan apakah simpul merupakan solusi.
3. Jika simpul merupakan solusi,
pencarian selesai.
4. Jika simpul belum jadi solusinya,
maka lanjutkan ke pencarian node selanjutnya.
5. Jika antrian kosong sementara
solusinya belum ditemukan, maka pencarian selesai.
6. Ulangi pencarian dari langkah yang
kedua
3.
Contoh Kasus Pencarian Lintasan Terpendek
:
Penjelasan Gambar :
1. Membangkitakan anak dari Balige =
Tambunan, Tampahan, OnanRaja
2. Karena Goal State ( Porsea) belum tercapai
maka kita bangkitkan anak dari Balige
-
Tambunan
= Laguboti , Silaen
-
Laguboti
= Sitoluama, Porsea
-
Tampahan
= Tara Bunga
-
Onan
Raja = Pardede Onan, Rs Blige
3. Akhirnya tercapai Goal State ( Porsea).
Penutup
Kesimpulan
Proses pencarian pada semua node
yang telah tersedia dimana pencarian terlebih dahulu dilakukan pada node
terdekat sebelum melanjutkan proses pencarian pada node berikutnya.
Saran
Lebih Memahami lagi ragam
Algoritma.
Nama :
Tentri May Simbolon
NPM : 1144027
Kelas : D4 Teknik Informatika 3C
Kampus : Politeknik Pos Indonesia
Link Github :
Link Plagiarime :
Smallseotools : https://drive.google.com/open?id=0B7tQon2iaQFdNllBd3RyWU45d0k
Link Github : https:https://github.com/D4TI3C/Tentri-May-Simbolon-1144027/blob/master/doc/kuliah/pertemuan6.md
Link Refrensi
Matakuliah Kecerdasan Buatan
