METODE PENCARIAN (ARTIFICIAL INTELEJENCE) BREADTH FIRST SEARCH (BFS)

Breadth-first search (BFS) melakukan proses searching pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya.





BFS adalah algoritma yang besar untuk mendapatkan jalur terpendek ke tujuan Anda (tidak berlaku untuk grafik yang memiliki bobot ditugaskan untuk tepi). BFS dengan nama itu sendiri menunjukkan bahwa luasnya pohon pencarian diperluas sepenuhnya sebelum pergi ke langkah berikutnya.

Sekarang tidak seperti Pencarian Pertama Kedalaman kita tidak perlu antrian prioritas untuk ini. Kami menggunakan dua antrian sebaliknya, satu untuk memperluas dan satu untuk menyimpan sementara. Sekali lagi setiap elemen dari antrian adalah jalan dari akar pohon. Algoritma ini menggunakan antrian adalah sebagai berikut:

Insert the root into the expanding queue

While expanding queue is not empty
Copy contents of expanding queue to temporary queue
Empty the expanding queue
For each node in the temporary queue
Dequeue one element from the temporary queue
If the path is ending in the goal state, print the path and exit
Else
Insert all the children of the dequeued element into the expanding queue



Sekarang mari kita menerapkan algoritma pada pohon di atas dan melihat apa yang memberi kita. Kami akan menuliskan keadaan antrian berkembang pada setiap iterasi dan melihat hasil akhir. Setiap elemen dari antrian ditulis sebagai [path].

Initialization: { [ S ] }
Iteration1: { [ S->A ] , [ S->G ] }
Iteration2 gives the final output as S->G.

Hal yang perlu disebutkan:

-> Pembentukan pohon pencarian bukan merupakan bagian dari algoritma. Hal ini hanya untuk visualisasi.

-> Algoritma mengembalikan jalur yang mungkin pertama kali bertemu (dalam hal ini optimal), tidak mencari semua path yang mungkin.

-> Jalur dikembalikan adalah jalur terpendek mungkin dalam pohon pencarian.

Ini akan mencari tingkat pohon demi tingkat, yaitu memperluas semua path yang mungkin sampai setiap node pada ketinggian tertentu dan kemudian pergi untuk tingkat bawah. Oleh karena itu tepat disebut BFS. Ini juga menjelaskan mengapa kita tidak memerlukan antrian prioritas yang digunakan dalam Pencarian Pertama Depth. Ingat bahwa prioritas dari setiap elemen adalah jumlah node yang jalan terkandung. Di sini, setiap elemen memiliki jumlah yang sama node karena kita memperluas tingkat demi tingkat, dan dengan demikian memiliki prioritas tidak masuk akal.

Saya sebutkan sebelumnya BFS yang tidak optimal untuk grafik yang memiliki berat ditugaskan untuk tepi. Salah satu contoh grafik diberikan di bawah ini:



Sebagai contoh ini BFS akan kembali jalan sebagai S-> G sedangkan jalur memiliki biaya minimum yang terkait dengan itu adalah S-> A-> C-> G. Jadi BFS mengembalikan jalur terpendek panjang dan tidak optimal dalam biaya. Kami akan memecahkan masalah ini dengan menggunakan Cari Biaya Seragam di posting berikutnya!