Metode Blind Search

1.      Metode Pencarian.

A.                      Blind Search.

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.

Algoritma yang termasuk Blind Search yaitu Breadth First Search (BFS), Depth First Search (DFS), Uniform Cost Search (UCS), Depth-Limited Search (DLS), Iterative-Deeping Search (IDS), dan Bi-directional search (BDS). Hanya saja yang paling banyak dibahas adalah Breadth First Search (BFS) dan Depth First Search (DFS).

Breadth First Search.

Pada metode breadth first search, 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, 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 :

o   Tidak akan menemui jalan buntu.

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

Kelemahan :

o   Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.

o   Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1).

Depth First Search.

Pada Depth First Search, proses pencarian akan dilakukan pada 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.

 

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 :

o   Membutuhkan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.

o   Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

Kelemahan :

o   Memungkinkan tidak ditemukannya tujuan yang diharapakan.

o   Hanya akan menemukan 1 solusi pada setiap pencarian.

  

Sumber berasal dari 

http://www.elangsakti.com/2013/03/bahasan-fundamental-tentang-blind.html