Pencarian Breadth First dalam Kecerdasan Buatan

Pencarian breadth-first (breadth-first search) adalah strategi sederhana di mana node (simpul) akar diturunkan (expanded) terlebih dahulu, kemudian semua node penerusnya diturunkan lagi berikutnya, kemudian node penerusnya diturunkan lagi, demikian dan seterusnya. Secara umum, setiap node akan diturunkan pada kedalaman tertentu di pohon pencarian sebelum node di tingkat berikutnya diturunkan. Lihat contoh ilustrasi gambar di bawah ini.

Gambar ini menunjukkan prosespencarian pada pohon biner sederhana. Di setiap tahap, node yang akan diturunkan ke lapisan berikutnya ditunjukkan oleh tanda panah.

Pencarian breadth-first adalah turunan dari algoritma pencarian berbasis graph umum di mana node terdangkal yang belum diturunkan dipilih untuk diturunkan (ekspansi). Hal ini dicapai dengan cara sangat sederhana dengan menggunakan antrian FIFO (first in first out). Dengan demikian, node baru (yang selalu lebih dalam dari node induknya) berada di antrian belakang, dan node lama/sebelumnya, yang lebih dangkal dari node baru, bisa diturunkan terlebih dahulu. Ada satu modifikasi kecil dibanding pada algoritma pencarian berbasis graph umum, yaitu bahwa tes pada goal (node tujuan) diterapkan pada setiap node ketika diturunkan dan bukan ketika saat dipilih untuk diturunkan (ekspansi). Perhatikan juga bahwa algoritma ini, mengikuti juga bentuk umum untuk pencarian berbasis graph, yaitu membuang setiap jalur baru (dari node-node) ke state yang sudah ada di jalur node sebelumnya atau set/himpunan node yang sudah dikunjungi (explored); jadi ini mudah dipahami bahwa jalur semacam ini setidaknya adalah sedalam node yang sudah didapatkan. Dengan demikian, pencarian breadth-first ini selalu memiliki jalur paling dangkal ke setiap node di jalur nya (batas antar kedalaman node). Pseudocode untuk breadth-first diberikan pada gambar di bawah ini. 

Pseudocode pencarian breadth first pada graph

Bagaimana kinerja pencarian breadth-first menurut empat kriteria? [Kriteria kinerja pencarian ada di catatan di bagian bawah artikel]. Kita dapat dengan mudah melihat bahwa algoritma ini complete (completeness) — jika node goal (node tujuan) berada pada suatu kedalaman d, maka pencarian breadth-first akan menemukannya (goal) setelah menghasilkan semua node yang lebih dangkal (asalkan faktor percabangan b adalah terbatas). Perhatikan bahwa segera setelah node goal diturunkan, kita tahu itu adalah node goal yang paling dangkal karena semua node yang lebih dangkal pasti telah diturunkan dan tidak ditemukan sebagai goal dalam pengujian sebagai node goal. Tetapi, node goal yang paling dangkal tersebut belum tentu sebagai node (goal) yang paling optimal; 

Sampai disini, teori tentang pencarian breadth-first sudah ok. Tetapi untuk teori tentang ruang (memori) dan waktu (execution time) tidak begitu baik. Bayangkan jika mencari di suatu pohon pencarian di mana setiap state/node memiliki sebanyak b turunannya. Root dari pohon pencarian menghasilkan sebanyak b node di tingkat pertama, yang masing-masing node kemudian menghasilkan sebanyak b node lagi, dengan total b² di tingkat kedua. Masing-masing node kemudian menghasilkan sebanyak b node lagi, sehingga menghasilkan b³ node di tingkat ketiga, dan seterusnya. Sekarang anggaplah solusinya (goal) ada di kedalaman d. Dalam kasus terburuk, goal adalah node terakhir yang dihasilkan pada level itu. Maka jumlah total node yang dihasilkan adalah

b + b² + b³ + ・ ・ ・ + b^d = O(b^d).

(Jika algoritma menerapkan uji node goal ke node-node ketika dipilih untuk diturunkan, dan bukan ketika diturunkan, maka seluruh lapisan node pada kedalaman d akan diturunkan sebelum goal terdeteksi dan kompleksitas waktu akan menjadi O(b^{d + 1}) .)

Adapun kompleksitas ruang/memori: untuk segala jenis pencarian berbasis graph, yang menyimpan setiap node yang diturunkan dalam set/himpunan yang dikunjungi (explored), kompleksitas ruang/memori selalu sebagai faktor b (branching/cabang) dari kompleksitas waktu. Untuk pencarian breadth-first, khususnya, setiap node yang diturunkan tetap berada dalam memori. Jadi akan ada O(b^d−1) node dalam set/himpunan yang dikunjungi (explored) dan O(b^d) node di perbatasan, jadi kompleksitas ruangnya adalah O(b^d), yaitu, didominasi oleh ukuran di node perbatasan. 

Suatu kompleksitas eksponensial seperti O(b^d) bukanlah hal yang menggembirakan. Tabel di bawah ini menunjukkan alasannya.

Tabel kebutuhan waktu dan memori untuk breadth-first

Kebutuhan waktu dan memori untuk pencarian breadth-first. Angka-angka yang ditunjukkan dengan asumsi-asumsi sebabagi berikut: faktor percabangan b = 10; 1 juta node / detik; 1000 byte / node.

Dalam daftar tersebut terlihat, untuk berbagai nilai kedalaman solusi d, waktu dan memori yang diperlukan untuk pencarian breadthfirst dengan faktor percabangan b = 10. Tabel ini mengasumsikan 1 juta node dapat diturunkan dalam 1 detik dan bahwa satu node membutuhkan 1000 byte ruang penyimpanan. Banyak problem pencarian yang sesuai dengan asumsi-asumsi ini. Atau kalau dijalankan pada komputer pribadi modern bisa mengambil faktor b 100 .

Ada dua pelajaran yang dapat dipelajari dari tabel di atas. Pertama, persyaratan memori adalah masalah yang lebih besar dalam pencarian breadth-first daripada waktu eksekusi. Orang mungkin menunggu 13 hari untuk solusi dengan kedalaman pencarian 12, tetapi tidak ada komputer pribadi yang memiliki memori ukuran petabyte. 

Untungnya, masih ada strategi pencarian lain yang membutuhkan lebih sedikit memori. Pelajaran kedua adalah bahwa waktu eksekusi masih merupakan faktor utama. Jika misalnya solusi ada pada kedalaman 16, maka (dengan asumsi di atas) akan membutuhkan waktu sekitar 350 tahun pencarian breadth-first untuk menemukan solusinya. 

Secara umum, masalah pencarian dengan kompleksitas-eksponensial tidak dapat dipecahkan dengan metode-metode pencarian uninformed untuk hal apa pun kecuali contoh problem yang sangat kecil.

Catatan:
Empat kriteria untuk pengukuran kinerja algoritma pencarian:

• Completeness (Keselesaian): Apakah algoritma dijamin untuk menemukan solusi jika memang ada solusinya?
• Optimality (Optimalitas): Apakah strategi menemukan solusi optimal (biaya terendah)?
• Time complexity (Kompleksitas waktu): Berapa lama untuk menemukan solusi?
• Space complexity (Kompleksitas ruang/memori): Berapa banyak memori yang dibutuhkan untuk melakukan pencarian?