Pencarian Melebar Pertama (Breadth First Search)

Pencarian Melebar Pertama (Breadth First Search)

Pada metode pencarian ini, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya.

Gambar  Pencarian melebar pertama (Breadth First Search)

(Sumber: Artificial Intelligence , Suyanto.ST.Msc, 2011)

Karena proses breadth first search mengamati setiap node di setiap level graf sebelum bergerak menuju ruang yang lebih dalam, maka mula-mula semua keadaan akan dicapai lewat lintasan yang terpendek dari keadaan awal. Oleh sebab itu, proses ini menjamin ditemukannya lintasan terpendek dari keadaan awal ke keadaan tujuan. Lebih jauh karena mula-mula semua keadaan ditemukan melalui lintasan terpendek sehingga setiap keadaan yang ditemui pada kali kedua didapati pada sepanjang sebuah lintasan yang sama atau lebih panjang. 

Kemudian, jika tidak ada kesempatan ditemukannya keadaan yang identik pada sepanjang lintasan yang lebih baik maka algoritma akan menghapusnya, sehingga keuntungan dari metode pencarian ini adalah:

1.      Tidak akan menemui jalan buntu.

2.      Jika ada satu solusi, maka breadth-first search akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.

Namun demikian, ada tiga persoalan utama berkenaan dengan metode pencarian ini, yaitu:

1.      Membutuhkan memori yang besar, karena menyimpan semua node dalam satu pohon. Jumlah node di setiap tingkat dari pohon bertambah secara eksponensial terhadap jumlah tingkat, dan semuanya ini harus disimpan sekaligus.

2.      Membutuhkan sejumlah besar pekerjaan, khususnya jika lintasan solusi terpendek cukup panjang, karena jumlah node yang perlu diperiksa bertambah secara eksponensial terhadap panjang lintasan.

3.      Tidak relevannya operator akan menambah jumlah node yang harus diperiksa sangat besar.

4.      Relatif membutuhkan waktu yang cukup lama, karena akan menguji semua node pada level ke-n untuk mendapatkan solusi pada level ke- (n + 1)

Share this post