Pada kesempatan kali ini saya akan menjelaskan apa itu
Metode Pencarian Buta (Blind Search) dan Metode Pencarian Heuristik. Di dalam
Metode Blind Search saya akan menjelaskan 2 metode yaitu Breadth Frist Search
(BFS) dan Depth Frist Search (DFS) dan Metode Heuristic terdapat 2 metode yaitu
Generate nad Test dan Hill Climbing.
METODE BLIND SEARCH
Blind Searching adalah model pencarian buta atau
pencarian yang tidak memiliki informasi awal, model pencarian ini memiliki tiga
ciri-ciri utama yaitu :
- Membangkitkan simpul berdasarkan urutan
- Kalau ada solusi maka solusi akan ditemukan
- Hanya memiliki informasi tentang node yang telah terbuka (node selanjutnya tidak diketahui)
Breadth Frist Search
metode pencarian yang bertujuan untuk memperluas dan
memeriksa semua simpul pada graph atau urutan kombinasi dengan pencarian secara
sistematis melalui setiap solusi.
Contoh :
Implementasi Breadth Frist Search pada java contoh
penerapan BFS untuk pencarian jalur terpendek ialah jalur terpendek pada game
Maze
Game Maze adalah game yang mengharuskan user untuk
menemukan jalan keluar dan melewati banyak halangan dari sebuah ruang yang
mirip labirin. Ketika program dijalankan sistem akan otomatis mencari rute
terpendek panjang rute akan dituliskan dalam bentuk angka disetiap kotak.
Deapth Frist Search
Proses searching sistematis buta yang melakukan ekpansi sebuah
path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi terhadap
path yang lain. Proses searching mengikuti sebuah path tunggal sampai
menemukan goal atau dead end.
contoh :
Studi Kasus : Pada suatu hari ada seorang petani
yang mempunyai seekor kambing dan serigala.Pada saat itu ia baru saja panen
sayuran. Karena membutuhkan uang, petani tersebut hendak menjual kambing,
serigala, dan sayurannya ke pasar Johar. Untuk sampai di pasar Johar, ia harus
menyeberangi sebuah sungai.
Permasalahannya : adalah di sungai itu hanya
tersedia satu perahu saja yang bisa memuat petani dan satu penumpang lainnya
(kambing, srigala, atau sayuran). Jika ditinggalkan oleh petani tersebut, maka
sayuran akan dimakan oleh kambing dan kambing akan dimakan oleh serigala.
Deskripsi
· P
= Petani
· Sy
= Sayuran
· K
= Kambing
· Sg
= Serigala
Ruang Keadaan
· Untuk
daerah asal dan daerah seberang digambarkan. (P, Sy, K, Sg)
Keadaan Awal
· Daerah
Asal = (P, Sy, K, Sg)
· Daerah
seberang = (0, 0, 0, 0)
Tujuan
· Daerah
Asal = (0, 0, 0, 0)
· Daerah
seberang = (P, Sy, K, Sg)
- Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, maka stop.
- Jika Q kosong, tidak ada solusi. Stop.
- Ambil simpul v dari kepala (head) antrian. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2
- Bangkitkan semua anak dari simpul v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q. Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali lagi ke langkah 2.
METODE HEURISTIC
Merupakan metode pencarian yang memperhatikan nilai
perkiraan teknik ini merupakan suatu strategi untuk melakukan proses pencarian
ruang keadaan suatu problema secara selektif. Didalam metode heuristic
searching dibagi menjadi dua metode yaitu :
Generate and Test
Merupakan pendekatan yang paling sederhana dari semua
pendekatan yang akan dibicarakan, Jika pembuatan solusi yang dimungkinkan dapat
melakukan secara sistematis maka prosedur ini akan dapat segera menemukan
solusinya. Namun jika ruang problema sangat besar maka proses akan membutujkan waktu yang lama.
Contoh : Travelling Salesman Problem(TSP)
Seorang salesman ingin mengunjungi n Kota. Jarak antara
tiap-tiap kota sudah diketahui. Kita ingin mengetahui rute terpendek dimana
setiap kota hanya boleh dikunjungi tepat 1 kali. Misalkan ada 4 kota dengan
jarak antara tiap-tiap kota seperti berikut :
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
Merupkan salah satu variasi metode dimana umpan balik
yang berasal dari prosedur digunakan untuk memutuskan arah gerak dalam ruang
pencarian. Tes yang berupa fungsi heursistic ini akan menunjukkan seberapa
baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lain yang mungkin.
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, maka kita akan mendapatan sebanyak n!/2!(n-2)!
Atau sebanyak 6 kombinasi. Fungsi heuristic yang digunakan adalah panjang
lintasan yang terjadi.
