Memahami Breadth First Search

Memahami Metode Breadth First Search

 

Gambar 1 Breadth first search

Pencarian merupakan kegiatan yang banyak dilakukan oleh manusia. Seperti kita pada saat mengingat memori masa lampau maka otak bekerja mencari ingatan masa lalu. Pertanyaan yang muncul adalah, bagaimana cara otak dalam menemukan memori yang terpendam?.

Pada saat mempelajari materi tentang pencarian, kita membayangkan melakukan pencarian tersebut. Padahal cara pandang kita berbeda dengan cara pandang komputer. Komputer melihat sebuah realita sebagai satu node yang harus terlewati sampai ditemukan solusi yang dituju.

Misteri cara kerja otak, masih berusaha diteliti dan dipecahkan oleh ilmuwan. Telah muncul berbagai penelitian tentang syaraf, cara kerja syaraf, cara memori muncul dan sebagainya. Salah satu alat yang dapat digunakan adalah EEG(encepalo....).

Banyak orang dalam mempelajari metode pencarin berhenti ditengah jalan, karena dianggap tidak menguntungkan. Padahal, apabila kita ingin mengetahui kartu apa saja yang telah keluar dalam permainan poker. Maka satu yang kita lakukan adalah mencarinya disetiap pemain.

Seharusnya kita berusaha mempelajari, cara kerja otak dalam melakukan pencarian solusi diantara bermiliar solusi terpendam. Ketika kita memahami bagaimana otak bekerja, maka kita dapat menirunya pada kehidupan. 

Bayangkan pada saat kita mencari wajah seorang dalam ruangan dengan banyak wajah orang. Maka otak kita akan langsung menuju wajah yang dicari. Tanpa terlihat mencari satu persatu wajah dalam ruangan.

Pada saat mencari wajah seorang maka otak menggabungkan ciri dari wajah dalam database otak. Sehingga, otak berkolaborasi dengan mata sebagai masukan untuk mencocokkan dengan data dalam database otak.

Pada komputer dan secara algoritma tidak demikian. Ketika mencari wajah seseorang, maka komputer akan mencari secara satu persatu untuk dicocokkan dengan database. Pencocokan dimulai dari kursi pada baris pertama dan kolom pertama. 

Pencarian berlanjut pada kursi berikutnya sampai pada deretan kursi terakhir. Komputer akan membandingkan satu persatu wajah dengan database. Ketika dalam dalam proses pencocokan tidak ditemukan, maka komputer menyatakan tidak ada wajah yang dicari pada ruangan tersebut.

Untuk melakukan itu semua, butuh berapa proses dan simpanan memori dalam dalam database?. Ketika melakukan proses pencocokan kursi pertama, maka hasilnya disimpan pada database. Hal ini dilakukan agar pencarian tidak dilakukan lagi.

Pencarian jenis ini merupakan pencarian secara buta. Karena melakukan pencarian kedalam suatu senarai satu demi satu, sampai semua senarai tercapai. Pencarian ini kemudian dinamakan dengan blind search.

Salah satu pencarian buta adalah metode pencarian menyamping pertama atau breadth first search. Metode ini melakukan pencarian melalui jalan menyamping terlebih dahulu. Setelah itu melakukan pencarian kebawah atau ke kedalaman.

Sebagai ilustrasi dari pencarian menyamping tersebut, terdapat suatu contoh masalah. Masalah telah dipetakan kedalam bentuk graph. Peta graph tersebut memiliki nilai awal dan memiliki tujuan akhir pencarian.(gambar 1).

Mari kita melihat gambar 1 sebagai awal. Terdapat graph dengan berbagai huruf. Huruf teratas adalah node S awal atau kondisi awal sistem. Dengan graph atau node huruf G sebagai akhir atau tujuan hendak dicapai.

Langkah pencarian dimulai ketika node S menuju A. Mulai dari turun dari sisi kanan satu level dibawahnya. Kemudian berpindah satu level dengan A yaitu node B. Kemudian turun pada node satu level dibawahnya pada node paling kanan(C). Berpindah sesama level, dan lakukan perulangan sampai ketemu node G tujuannya.

Melihat gambar 1 dan cara kerja pencarian melebar pertama ini memastikan solusi ketemu. Karena solusi yang berada pada level node manapun dilewati dan terbaca. Sehingga apabila menggunakan solusi Breadth First Search, solusi akan memiliki kepastian untuk ketemu.

Namun, seperti seorang yang tidak tahu arah maka pencarian akan dilakukan disetiap area atau node sehingga membuat langkah menjadi semakin banyak. Hal ini memboroskan waktu dan memori yang diperlukan.

Setiap langkah yang dilakukan oleh metode pencarian ini disimpan agar pencarian tidak terulang. Jika hal ini dilakukan, maka akan menyebabkan memory simpanan semakin banyak.

Sedangkan pada teknologi komputer saat ini, memory memiliki keterbatasan. Oleh karena itu, jika metode pencarian BFS ini diterapkan maka komputer dapat mengalami masalah, bahkan dapat berakibat buruk bagi sistem.

Kesimpulan yang dapat diambil adalah kita dapat menggunakan metode pencarian Breadth First Search(BFS) untuk ruang masalah kecil. Karena memiliki pemborosan pemakaian memory. Dengan kelebihan solusi pasti ditemukan. Dengan adanya pemakaian memory yang besar maka waktu yang dibutuhkan pun juga besar.