Pengertian dan Konsep Breadth First Search dalam AI | Artificial Intelligent

post ini merupakan kelanjutan dari posting sebelumnya Pencarian Mendalam dalam Kecerdasan Buatan sekarang akan dibahas Konsep yang pertama yaitu Breadth First Search.


Pengertian Breadth First Search

 merupakan pencarian yang dilakukan dengan mengunjungi tiap tiap node secara sistematis pada setiap level hingga keadaan tujuan ditemukan. Penelususran yang dilakukan dengan mengunjungi node node pada level yang sama hingga ditemukan tujuan (goal state) nya.


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 simpul-simpul yang tadi dikunjungi, demikian seterusnya. algoritma BFS menggunakan graf sebagai media representasi persoalan, tidak sulit untuk mengaplikasikan algoritma ini dalam persoalan-persoalan teori graf.


Pengimplementasian Breath First Search dapat ditelusuri dengan menggunakan daftar list open dan closed, untuk menelusuri gerakan pencarian di dalam ruang keadaan. Pada algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yan bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian.

Prosedur BFS

Begin
   Open:=[start]
   Closed:=[];
   While open ≠[] do                
         Begin
             Remove leftmost state from open, call it X
                 IF X is goal then return SUCCESS
                     Else begin
                           Generate children of X;
                            Put X on closed;
                            dischard children of X is already on open or closed;
                             put remaining children on right end of open;
                         end;
                  end;
                 return FAIL
end.

Beberapa keuntungan menggunakan algoritma BFS yaitu tidak akan menemui jalan buntu dan jika ada satu solusi maka BFS akan menemukannya, jika ada lebih dari satu solusi maka solusi minimum akan ditemukan

Langkah langka 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.

Pengertian dan Konsep Breadth First Search dalam AI | Artificial Intelligent Rating: 4.5 Diposkan Oleh: budis

No comments:

Berlangganan Via Email