Breadth First Search

Breadth First Search

Pencarian dilakukan pada semua level dengan cara per baris level secara beurutan. Dari kiri ke kanan. Jika telah sampai dilevel terakhir maka dilanjutkan ke bagian bawah dari sebelah kiri lagi dan seterusnya. Dengan cara seperti ini BFS menjamin ditemukan nya solusi dengan catatan jika solusi nya emang benar ada dan mengambil solusi yang terbaik jika terdapat 1 lebih solusi yang ditemukan. BFS memiliki pemakaian memori yang besar karena BFS perlu menyimpan semua tingkatan yang telah diproses sebelumnya. Jika b adalah faktor percabangan (jumlah simpul anak yang dimiliki oleh suatu simpul) dan d adalah kedalaman solusi (tingkatan), maka jumlah simpul yang harus disimpan adalah sebanyak O(b^d). Misalkan, untuk b = 10 dan d = 8, maka BFS harus membaca dan menyimpan sebanyak 10⁰ + 10¹ + 10² + 10³ + 10⁴ + 10⁵ + 10⁶ + 10⁷ + 10⁸ = 111.111.111 = 10⁸ simpul. Waktu proses yang dibutuhkan untuk menemukan solusi dilevel 8 adalah 100 detik (1,67 menit). Jika suatu simpul diproses dalam struktur data sebesar 10¹⁵ bytes (10 gigabytes). Dari segi kecepatan masih bisa diterima. Tapi dari sisi memori yang diperlukan. Dengan permasalahan dan komputer yang sama , waktu proses yang diperlukan untuk menemukan solusi dilevel 14 adalah 10⁸ detik (lebih dari 3 tahun) dan diperlukan memori sebesar 10¹⁵ bytes (1.000 terabytes). Itu yang menjadi kan BFS menjadi sulit di implementasikan didunia nyata.