Blind Search merupakan pencarian asal. Jika solusi sudah ditemukan, maka pencarian akan dihentikan. Jika dibuat skemanya, pencarian buta hanya mengenal 3 bagian yaitu [masalah]-[pencarian]-[solusi]. Blind search tidak mempunyai atribut atau informasi tambahan. Algoritma yang termasuk Blind search yaitu
· Breath First Search (BFS)
· Depth First Search (DFS)
· Uniform Cost Search (UCS)
· Depth-Limited Search (DLS)
· Interative-Deeping Search (IDS)
· Bi-directional Search (BDS
Hanya saja yang paling banyak dibahas adalah Breadth Fisrt Search (BFS) dan Depth First Search (DFS)
Pencarian buta (blind search) : tidak ada informasi awal yang digunakan dalam proses pencarian
1. Pencarian melebar pertama (Breadth – First Search)
2. Pencarian mendalam pertama (Depth – First Search)
A. Pencarian Melebar Pertama
(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).
B. PENCARIAN KEDALAM PERTAMA
(Depth-First Search)
· Pada Depth-First Search, proses pencarian akan dilakukanpada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukannya solusi (lihat gambar di bawah).
prosedur depth_first_search
inisialisasi: open = [Start]; closed = []
while open x [] do
begin
hapuskan keadaan berikutnya dari sebelah kiri open, sebutlah keadaan itu dengan X;
jika X merupakan tujuan then return(sukses);
buatlah semua child yang dimungkinkan dari X;
ambilah X dan masukkan pada closed;
eliminasilah setiap child X yang telah berada pada
open atau closed, yang akan menyebabkan loop dalam search;
ambilah child X yang tersisa di ujung kanan open sesuai urutan penemuannya;
end.
Keuntungan :
Ø Membutuhkan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.
Ø Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.
Kelemahan :
Ø Memungkinkan tidak ditemukannya tujuan yang diharapakan
Ø Hanya akan menemukan 1 solusi pada setiap pencarian
