Blind Search merupakan pencarian
asal ketemu. Jika solusi sudah ketemu, maka pencarian akan dihentikan. Jika
dibuat skemanya, pencarian buta hanya mengenal tiga bagian,
[masalah]-[pencarian]-[solusi]. Misalkan dalam kotak ada 3 kelereng warna
merah, 3 biru, dan 3 kuning. Masalahnya adalah, ambillah satu kelereng yang
berwarna merah. Solusi, setelah melakukan pencarian, kemudian didapat satu
kelereng warna merah, nah, itulah solusinya.
(Breadth-First Search)
o Pada metode breadth-first search, semua node
pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada
level n+1.
o Pencarian dimulai dari node akar terus ke
level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya, demikian
pula dari kiri ke kanan hingga ditemukannya solusi (lihat algoritma di bawah
ini).
Prosedur
breadth_first_search
Inisialisasi : open =
[start]; closed [ ]
While open = [ ] do
Begin
Hapuskan keadaan paling
kiri dari keadaan open,
sebutlah keadaan itu
dengan X;
Jika X merupakan tujuan
then return (sukses);
Buatlah semua child dari
X,Ambillah X dan masukkan pada closed;
Eliminasilah setiap child
X yang telah berada pada open atau closed,
yang akan menyebabkan loop
dalam search;
Ambillah turunan di ujung
kanan open sesuai urutan penemuan-nya;
End;
Keuntungan :
Ø Tidak akan menemui jalan buntu
Ø Jika ada satu solusi,
maka breadth-first search akan menemukannya. Dan, jika ada lebih dari satu
solusi, maka solusi minimum akan ditemukan.
· Kelemahan :
Ø Membutuhkan memori yang
cukup banyak, karena menyimpan semua node dalam satu pohon
Ø Membutuhkan waktu yang
cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level
yang ke-(n+1).
Algoritma Breadth-First
Search (BFS) atau dikenal juga dengan nama algoritma pencarian melebar adalah
algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul
secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua
simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya,
simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi
dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua
simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1.
2.2 Cara Kerja
Algoritma BFS
Dalam algoritma BFS,
simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini
digunakan untuk mengacu simpul-simpul yang bertetangga dengannya yang akan
dikunjungi kemudian sesuai urutan pengantrian.Untuk memperjelas cara kerja algoritma
BFS beserta antrian yang digunakannya, berikut langkah-langkah algoritma BFS:
1. Masukkan simpul ujung (akar) ke dalam
antrian.
2. Ambil simpul dari awal antrian, lalu cek
apakah simpul merupakan solusi.
3. Jika simpul merupakan solusi, pencarian
selesai dan hasil dikembalikan.
4. Jika simpul bukan solusi, masukkan seluruh
simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian.
5. Jika antrian kosong dan setiap simpul sudah
dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan.
6. Ulangi pencarian dari langkah kedua.
Depth-first search
Depth-first search (DFS) adalah
proses searching sistematis buta yang melakukan ekpansi sebuah path (jalur)
menuju penyelesaian masalah sebelum melakukan ekplorasi terhadap path yang
lain. Proses searching mengikuti sebuah path tunggal sampai menemukan goal atau
dead end. Apabila proses searching menemukan dead-end, DFS akan melakukan
penelusuran balik ke node terakhir untuk melihat apakah node tersebut memiliki
path cabang yang belum dieksplorasi.
Secara formal, DFS adalah sebuah pencarian
uninformed yang berlangsung dengan memperluas simpul
anak pertama dari pencarian pohon yang muncul dan dengan demikian akan semakin dalam sampai node tujuan
ditemukan, atau sampai hits node yang tidak memiliki anak. Kemudian pencarian backtracks , kembali ke node terakhir kebanyakan belum selesai menjelajahi. Dalam
implementasi non-rekursif, semua node yang baru diperluas ditambahkan ke stack untuk eksplorasi.
Kelebihan dan Kelemahan DFS
Kelebihan DFS adalah:
- Pemakain memori hanya sedikit, berbeda jauh
dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.
- Jika solusi yang dicari berada pada level yang
dalam dan paling kiri, maka DFS akan menemukannya secara cepat.
Kelemahan DFS adalah:
- Jika pohon yang dibangkitkan mempunyai level yang
dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi
(Tidak Complete).
- Jika terdapat lebih dari satu solusi yang sama
tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan
untuk menemukan solusi yang paling baik (Tidak Optimal).
