Breadth-First Search (BFS)

Pencarian dilakukan pada semua node dalam setiap level secara berurutan dari kiri ke
kanan. Jika pada satu level belum ditemukan solusi, maka pencarian dilanjutkan pada
level berikutnya. Demikian seterusnya sampai ditemukan solusi. Dengan strategi ini,
maka dapat dijamin bahwa solusi yang ditemukan adalah yang paling baik (Optimal).
Tetapi BFS harus menyimpan semua node yang pernah dibangkitkan. Hal ini harus
dilakukan untuk penelusuran balik jika solusi sudah ditemukan. Gambar 2.4
mengilustrasikan pembangkitan pohon BFS untuk masalah Water Jug. Pembangkitan
suksesor dari suatu node bergantung pada urutan dari Aturan Produksi yang dibuat (lihat
gambar 2.3). Jika urutan dari aturan 4 ditukar dengan aturan 5, maka pohon BFS yang
dibangkitkan juga akan berubah.