Blind & Heuristic Search
Blind Search
Blind Search (pencarian
buta) atau biasa disebut pula dengan uninformed
search yaitu pencarian dengan variabel datanya tidak mempunyai atribut / informasi tambahan.
Jadi 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.
·
Breadth-First Search (BFS)
o
Pencarian semua node pada setiap level secara
berurutan dari kiri ke kanan atau atas ke bawah.
o
Jika pada satu level belum ditemukan solusi,
maka pencarian dilanjutkan pada level berikutnya sampai ditemukan solusi.
o
Pencarian dengan sistem FIFO (First In First Out)
o
Solusi yang ditemukan adalah yang paling baik
(Optimal).
o
Tetapi BFS harus menyimpan semua node yang
pernah dibangkitkan. Hal ini harus dilakukan untuk penelusuran balik jika
solusi sudah ditemukan.
o
Pembangkitan suksesor dari suatu node bergantung
pada urutan dari Aturan Produksi yang dibuat
·
Depth-First Search (DFS)
o
Pencarian satu node dalam setiap level dari yang
paling kiri.
o
Jika pada level yang paling dalam, solusi belum
ditemukan, maka pencarian dilanjutkan pada node sebelah kanan.
o
Node yang kiri dapat dihapus dari memori.
o
Jika pada level yang paling dalam tidak
ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya.
o
Demikian seterusnya sampai ditemukan solusi.
Jika solusi ditemukan maka tidak diperlukan proses backtracking (penelusuran
balik untuk mendapatkan jalur yang dinginkan).
Heuristic Search
adalah pencarian bersyarat (terbimbing). yaitu pencarian dengan variabel datanya mempunyai atribut / informasi tambahan. Artinya, solusi yang diperoleh adalah solusi
yang terbaik, bukan solusi sekali ketemu. Bagian-bagiannya adalah
[masalah]-[pencarian]-[syarat]-[solusi]. Misal contoh masalah pada kasus di atas,
Ambillah kelereng merah yang tidak pecah dan tidak lonjong. Sehingga ketika
ketemu kelereng merah dan ada pecahnya, itu masih bukan solusi karena tidak
sesuai dengan syarat (tidak pecah dan tidak lonjong).
Adalah
metode yang paling sederhana dalam teknik pencarian heuristik. Jika pembangkitan sebuah solusi yang mungkin (a
possible solution) dikerjakan secara sistematis, maka prosedur ini menjamin
akan menemukan solusinya. Tetapi jika ruang masalahnya sangat luas, mungkin
memerlukan waktu yang sangat lama.
- Contoh :
Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-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
Refrensi :
- Contoh :
Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-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…..
|
Hill Climbing
Pembangkitan
keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan.
Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai
terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin (SriKusumadewi
2003, h. 34).Ada dua macam metode Hill Climbing Search, yaitu Simple Hill
Climbing dan Steepest-ascent Hill Climbing (SriKusumadewi 2003, h. 39).
Refrensi :
Hari. 2013. “Bahasan Fundamental tentang Blind Search dan Heuristic Search”.
Diakses pada 9 Desember 2017. http://www.elangsakti.com/2013/03/bahasan-fundamental-tentang-blind.html
Zidny. 2016. “Teknik Pencarian 1 Blind Search”.
Diakses pada 9 Desember 2017. zidny.dosen.st3telkom.ac.id/wp-content/uploads/sites/29/2016/10/MKB3462-Kecerdasan
Buatan_3_Blind-Search.pptx.
Firdaus. 2014. “PENERAPAN METODE HILL CLIMBING SEARCH”.
Diakses pada 9 Desember 2017. eprints.mdp.ac.id/1051/1/74m.rezkiJurnal%20Toko%20Virtual.pdf
