8/18/2019 Tugas Ai Bfs

1/1

 Ahmad Kurniawan Syarif

D42114518

A.  Algoritma BFS (Breadth First Search) 

Dalam teori graf, breadth first search (BFS) juga merupakan teknik umum dalam

traversal graf. Algoritma pencarian grafnya dimulai dari simpul akar 5 yang kemudian

menelusuri semua simpul tetangganya. Kemudian, untuk setiap simpul yang terdekat itu,

ditelusuri simpul tetangga yang belum diperiksa, dan demikian seterusnya, sampaiditemukan simpul tujuan.

BFS adalah metode pencarian yang bertujuan memperluas dan memeriksa semua

simpul pada graf. BFS merupakan kombinasi dari tiap urutan langkah yang secara

sistematik mencari tiap solusi. Dengan kata lain, BFS secara penuh mencoba mencari pada

keseluruhan graf dengan urutan langkah yang tidak memikirkan tujuan sampai akhirnya

menemukan tujuan itu sendiri. BFS tidak menggunakan heuristik.

B.  Cara Kerja

i.  Mendeklarasikan dua list kosong : Open dan Close

ii. 

Menambahkan simpul awal ke Open

iii.  While do

  Hapus simpul awal dari Open

  Cek dan lihat apakah simpul yang dihapus adalah tujuan kita

a.  if -- Jika simpul yang dihapus adalah tujuan kita, keluar dari loop, tambahkan

simpul ke Close, dan kembali ke nilai dari Close kita.

b.  else -- Jika simpul yang dihapus bukan tujuan kita, lanjutkan loop (ke Langkah

C)

  Ekstrak tetangga dari simpul yang dihapus di atas

  Tambahkan tetangga ke akhir dari Open, dan tambahkan simpul yang dihapus

ke Close.

C.  Implementasi pada gambar satelit

Algoritma lintasan terpendek graf sangat penting pada pemrosesan dari gambar

satelit. Bayangkan satelit mengambil foto dari jalanan kota, algoritma graf dapat

mengidentifikasi jalan tersebut. GPS dapat mengambil gambar tersebut dan menemukan

lintasan terpendek dari satu tempat ke tempat lain, alat tersebut harus bisa menjalankan

algoritma pencarian graf pada gambar, yang akan mencari lintasan terpendek.

Alat ini dapat menjalankan algoritma breadth first search. Algoritma ini dapat

mulai dari titik sumber dan secara sistematik mencari sisi ke setiap simpul yang bisa diraih.

Algoritma ini mengiterasi proses yang sama di setiap simpul yang bisa diraih ke simpul

yang bisa diraih berikutnya. Untuk menyimpan simpul, digunakan FIFO Queue. FIFO

menyimpan simpul yang dapat diraih pada queue.

http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2008-2009/Makalah2008/Makalah0809-054.pdf