Blind Search

Strategi Pencarian Mendalam

Pencarian boleh jadi merupakan hasil dari suatu solusi atau ruang keadaan yang
mungkin telah terkunjungi semua, tetapi tanpa penyelesaian. Pencarian yang
mendalam (Exhaustive Search Strategy) mungkin dilakukan dengan menggunakan
strategi Breadth First Search atau Depth First Search). Kedua pencarian ini
merupakan pencarian buta (Blind Search)

Breadth First Search

Prosedur Breadth First Search merupakan pencarian yang dilakukan dengan
mengunjungi tiap – tiap node secara sistematis pada setiap level hingga keadaan
tujuan (goal state) ditemukan. Atau dengan kata lain, penelusuran yang dilakukan
adalah dengan mengunjungi node – node pada level yang sama hingga ditemukan
goal state nya. Untuk lebih jelasnya, perhatikan ilustrasi dari Breadth First Search
pada gambar berikut ini.

Pengimplementasian Breadth First Search dapat ditelusuri dengan menggunakan
daftar (List) open dan closed, untuk menelusuri gerakan pencarian di dalam ruang
keadaan, prosedur untuk Breadth First Search dapat dituliskan sebagai berikut

(Luger : 2002) :

Prosedure breadth first search
Begin
Open := [Start];
Closed := [];
While Open ≠ [] do
Begin
S
A D
B F
C E
M N
G
O P
H I
J
Q R
K L
T U V
9
Remove leftmost state from open, call it x
If X is a goal then return SUCCESS
Else
Begin
Generate children of x;
Put x on closed;
Discard children of x is already open or closed;
Put remaining children on right end of open;
End;
End;
Return FAIL
End.

Pada gambar di atas, U* adalah node tujuannya (goal) sehingga bila ditelusuri
menggunakan prosedur Depth First Search, diperoleh :
1. Open = [A]; Closed = []
2. Open = [B, C, D]; Closed = [A]
A
B C D
E F
K L M
S T
G H
N O P
I J
Q
U*
R
10
3. Open = [C, D, E, F]; Closed = [B, A]
4. Open = [D, E, F, G, H]; Closed = [C, B, A]
5. Open = [E, F, G, H, I, J]; Closed = [D, C, B, A]
6. Open = [F, G, H, I, J, K, L]; Closed = [E, D, C, B, A]
7. Open = [G, H, I, J, K, L, M]; Closed = [G, F, E, D, C, B, A]
8. dan seterusnya sampai U diperoleh atau open =[]

Keuntungan :

1. Tidak akan menemui jalan buntu dan jika ada satu solusi maka Breadth First
Search akan menemukannya.
2. Jika ada lebih dari satu solusi maka solusi minimum akan ditemukan

Kerugian :

1. Membutuhkan memori yang besar, karena menyimpan semua node dalam satu
pohon.
2. Membutuhkan sejumlah besar pekerjaan, khususnya bila solusi terpendek cukup
panjang, karena jumlah node yang perlu diperiksa bertambah secara eksponensial
terhadap panjang lintasan.

Depth First Search

Pencarian dengan metode ini dilakukan dari node awal secara mendalam hingga yang
paling akhir n(dead end) atau sampai ditemukan. Dengan kata lain, simpul cabang
atau anak yang terlebih dahulu dikunjungi. Sebagai ilustrasinya dapat dilihat pada
gambar berikut ini.
11

Prosedur Depth First Search dapat diimplementasikan dengan melakukan modifikasi
proses Breadth First Search menjadi 

(Luger : 2002) :

Prosedure depth first search
Begin
Open := [Start];
Closed := [];
While Open ≠ [] do
Begin
Remove leftmost state from open, call it x
If X is a goal then return SUCCESS
Else
Begin
Generate children of x;
Put x on closed;
Discard children of x is already open or closed;
Put remaining children on left end of open;
1
2 11
3 5
8
4 6 7
9
10
12 14
13 15 16
12
End;
End;
Return FAIL
End.

Untuk memeriksa algoritma di atas, dapat dilihat bahwa keadaan – keadaan turunan
(descendant) ditambahkan atau dihapuskan dari ujung kiri open. Untuk lebih jelasnya,
dapat dilihat aplikasi algoritma tersebut untuk contoh sebelumnya seperti pada
Breadth First Search. Langkah penelusuran adalah sebagai berikut.

1. Open = [A]; Closed = []
2. Open = [B, C, D]; Closed = [A]
3. Open = [E, F, C, D]; Closed = [B, A]
4. Open = [K, L, F, C, D]; Closed = [E, B, A]
5. Open = [S, L, F, C, D]; Closed = [K, E, B, A]
6. Open = [L, F, C, D]; Closed = [S, K, E, B, A]
7. Open = [T, F, C, D]; Closed = [L, S, K, E, B, A]
8. Open = [F, C, D]; Closed = [T, L, S, K, E, B, A]
9. Open = [M, C, D]; Closed = [F, T, L, S, K, E, B, A]
10. Open = [C, D]; Closed = [M, F, T, L, S, K, E, B, A]
11. Open = [G, H, D]; Closed = [C, M, F, T, L, S, K, E, B, A]
12. dan seterusnya sampai U diperoleh atau open =[]

http://ibbi.ac.id/ibbiacid/bahan/kecerdasan-buatan.pdf