Nama : Ahmad Fauzi
NIM :
G.211.11.0023
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
Description: Blind Search (Kecerdasan Buatan)
Rating: 4.5
Reviewer: Mr simple
ItemReviewed: Blind Search (Kecerdasan Buatan)
Posted by:Mbah Qopet
Mbah Qopet Updated at: 17.25
0 komentar
Posting Komentar