Tugas 6 Kecerdasan Buatan

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

Searchenginereports : https://drive.google.com/open?id=0B7tQon2iaQFdMmlKR3BYcGFDeFk

Link Github : https:https://github.com/D4TI3C/Tentri-May-Simbolon-1144027/blob/master/doc/kuliah/pertemuan6.md

Link Refrensi

http://yoursknowladge.blogspot.co.id/2015/04/makalah-algoritma-breadth-first-search.html

http://eprints.mdp.ac.id/1431/1/Jurnal.pdf

http://ejournal.stmik-time.ac.id/index.php/jurnalTIMES/article/view/6

Matakuliah Kecerdasan Buatan