1. Metode
Pencarian Buta (Blind Search)
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]. Pencarian buta
(blind search) : tidak ada informasi awal yang digunakan dalam proses
pencarian
A. Breadth-First Search ( Pencarian Melebar Pertama )
Pada 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 1 dari kiri ke
kanan, kemudian berpindah ke level berikutnya dari kiri ke kanan hingga solusi
ditemukan. Dibawah ini tree untuk Breath First Search.
Contoh
:
1. Pada metode
ini diperiksa setiap node pada level yang sama sebelum mengolah ke level
berikutnya yang lebih dalam.
2. Pencarian dilakukan
pada semua simpul dalam setiap level secara berurutan dari kiri ke kanan.
3. jika pada
satu level belum ditemukan solusinya, maka pencarian dilanjutkan pada
level berikutnya.
B. Depth
– First Search (Pencarian mendalam pertama )
Pada pencarian Depth – First Search dilakukan pada suatu
simpul dalam setiap level dari yang paling kiri. Jika pada level yang paling
dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada simpul sebelah
kanan dan simpul yang kiri dapat dihapus dari memori. Jika pada level yang
paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level
sebelumnya. Demikian seterusnya sampai ditemukan solusi. Dibawah ini tree untuk
Depth First Search.
Contoh :
1. Pencarian dilakukan pada suatu simpul dalam setiap level dari yang paling kiri.
2. Jika pada level yang terdalam, solusi belum ditemukan, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yang kiri dapat dihapus dari memori
3. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya.
4. Demikian seterusnya sampai ditemukan solusi
Metode pencarian dapat dilihat seperti gambar :
§ Konsepnya hampir sama dengan BFS ( Breadth First Search)
§ Pada
UCS, menggunakan urutan biaya dari yang paling kecil sampai terbesar
§ UCS berusaha untuk menemukan solusi dengan
total biaya terendah.
2.
Metode Heuristic search ( pencarian
Heuristik)
Heuristik
adalah sebuah teknik yang mengembangkan efisiensi dalam proses
pencarian, namum dengan kemungkinan mengorbankan kelengkapan
(completeness).
Fungsi heuristik digunakan untuk mengevaluasi
keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut
dapat digunakan untuk mendapatkan solusi yang diinginkan.
A. Generate
and Test (Pembangkitan dan pengujian)
Metode ini merupakan penggabungan antara
depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke
belakang menuju pada suatu keadaan awal.
Contoh :
“Travelling Salesman
Problem (TSP)”
Seorang salesman ingin
mengunjungi n kota. Jarak antara tiap kota sudah diketahui. Kita ingin
mengetahui ruter terpendek dimana setaip kota hanya boleh dikkunjungi
tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota
seperti berikut ini :
Alur pencarian
dengan Generate and Test
Pencarian
ke-
|
Lintasan
|
Panjang
Lintasan
|
Lintasan
terpilih
|
Panjang
Lintasan terpilih
|
1
|
ABCD
|
19
|
ABCD
|
19
|
2
|
ABDC
|
18
|
ABDC
|
18
|
3
|
ACBD
|
12
|
ACBD
|
12
|
4
|
ACDB
|
13
|
ACBD
|
12
|
5
|
ADBC
|
16
|
ACBD
|
12
|
Dst…..
|
B. Hill
Climbing (Pendakian Bukit )
Metode ini hampir sama dengan metode pembangkitan dan pengujian,
hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan
keadaan berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang
berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan
yang diambil terhadap keadaan-keadaan lainnyayang mungkin. Dibawah ini tree untuk Hill Climbing.
Contoh :
TSP dengan
Simple Hill Climbing Disini ruang keadaan berisi semua kemungkinan lintasan
yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang
bersebelahan. Apabila ada n kota, dan kita ingin mencari kombinasi lintasan
dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak :
atau sebanyak 6
kombinasi. Fungsi heuristic yang digunakan adalah panjang
lintasan yang terjadi.
Referensi
:
2.
http://rifazahralee.blogspot.co.id/2016/11/pencarian-buta-blind-search_3.html\