Metode
Pencarian Buta (Blind Search)
Blind Searching adalah
model pencarian buta atau pencarian yang tidak memiliki inforamasi 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 dibuka (node selanjutnya tidak diketahui).
1.
Breadth First Search
Breadth
First Search yaitu model pencarian yang memakai metode melebar. Untuk mencari
hasilnya, model BFS ini menggunakan teknik pencarian persoalannya dengan cara
membuka node (titik) pada tiap levelnya.
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.
Keuntungannya :
·
Tidak akan menemui jalan buntu, menjamin
ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti
solusi yang paling baik.
·
Jika ada 1 solusi, maka breadth – first
search akan menemukannya.
·
Jika ada lebih dari 1 solusi, maka solusi
minimum akan ditemukan.
Kerugiannya :
·
Membutuhkan memori yang banyak, karena
harus menyimpan semua simpul yang pernah dibangkitkan dan hal ini harus
dilakukan agar BFS dapat melakukan penelusuran simpul-simpul sampai di level
bawah.
·
Membutuhkan waktu yang cukup lama.
Algoritma :
ü Buat
sebuah antrian, inisialisasi node pertama dengan Root dari tree.
ü Bila
node pertama, jika ≠ GOAL, diganti dengan anak-anaknya dan diletakkan di
belakang per level.
ü Bila
node pertama = GOAL, selesai.
Contoh BFS :
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.
2.
Depth First Search
DFS
(Depth-first Search) sering disebut juga pencarian mendalam. Sesuai dengan
namanya “pencarian mendalam”, DFS tidak mencari solusi per level, namun mencari
pada kedalaman sebelah kiri terlebih dahulu, kemudian bila belum ditemukan
“goal”nya dilanjutkan ke sisi sebelah kanan dan seterusnya sampai ditemukan
target/goal.
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.
Keuntungannnya :
· Membutuhkan memori relatif kecil, karena
hanya node-node pada lintasan yang aktif saja yang disimpan.
· Dan secara kebetulan, akan menemukan
solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan, jadi jika
solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan
menemukannya dengan cepat (waktunya cepat).
Kerugiannya :
· Memungkinkan tidak ditemukannya atau tidak
adanya tujuan yang diharapkan, karena jika pohon yang dibangkitkan mempunyai
level yang sangat dalam (tak terhingga) Ã tidak complete karena tidak ada
jaminan akan menemukan solusi.
·
Hanya mendapat 1 solusi pada setiap
pencarian, karena jika terdapat lebih dari satu solusi yang sama tetapi berada
pada level yang berbeda, maka DFS tidak menjamin untuk menemukan solusi yang
paling baik & tidak optimal.
Algoritma
:
·
Buat sebuah antrian, inisialisasi node
pertama dengan Root dari tree.
· Bila node pertama, jika ≠ GOAL, node
dihapus diganti dengan anak-anaknya dengan urutan Lchild.
·
Bila node pertama = GOAL, selesai.
Contoh DFS :
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 ditemukansolusi, maka pencarian dilanjutkan pada
level sebelumnya.
4. Demikian seterusnya
sampai ditemukan solusi
Metode
Pencarian Heuristik
Heuristic
Search merupakan metode pencarian yang memperhatikan nilai heuristik (nilai
perkiraan).Teknik pencarian heuristik (heuristic searching) merupakan suatu
strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu
problema secara selektif, yang memandu proses pencarian yang kita lakukan di
sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan
mengesampingkan usaha yang bodoh dan memboroskan waktu.
Heuristik
adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun
dengan kemungkinan mengorbankan kelengkapan (completeness).
Heuristic Search memperkirakan
jarak menuju Goal (yang disebut dengan fungsi heuristik).Fungsi heuristik ini
digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan
seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang
diinginkan.
1.
Generate & Test
Strategi
bangkitkan dan uji (generate and test) merupakan pendekatan yang paling
sederhana dari semua pendekatan yang akan dibicarakan.
Pendekatan
ini meliputi langkah–langkah sebagai berikut :
a. Buatlah/bangkitkan
sebuah solusi yang memungkinkan. Untuk sebuah problema hal ini dapat berarti
pembuatan sebuah titik khusus dalam ruang problema.
b. Lakukan
pengujian untuk melihat apakah solusi yang dibuat benar–benar merupakan sebuah
solusi, dengan cara membandingkan titik khusus tersebut dengan goal-nya
(solusi).
c. Jika
telah diperoleh sebuah solusi, langkah – langkah tersebut dapat dihentikan.
Jika belum, kembalilah ke langkah pertama.
d. Jika
pembangkitan atau pembuatan solusi – solusi yang dimungkinkan dapat dilakukan
secara sistematis, maka prosedur ini akan dapat segera menemukan solusinya
(bila ada). Namun, jika ruang problema
sangat besar, maka proses ini akan membutuhkan waktu yang lama.
e. Metode
generate and test ini memang kurang efisien untuk masalah yang besar atau
kompleks.
Contoh
Generate & Test :
“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 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…..
|
2.
Hill Climbing
Hill
Climbing (mendaki bukit) merupakan salah satu variasi metode buat dan uji
(generate and test) dimana umpan balik yang berasal dari prosedur uji digunakan
untuk memutuskan arah gerak dalam ruang pencarian (search).
Dalam
prosedur buat dan uji yang murni, respon fungsi uji hanyalah ya atau tidak.
Dalam prosedurHill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik
yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan
tujuan (goal).
Prosedur
Hill Climbing :
a. Buatlah
solusi usulan pertama dengan cara yang sama seperti yang dilakukan dalam
prosedur buat dan uji (generate and test). Periksalah apakah solusi usulan itu
merupakan sebuah solusi. Jika ya, berhentilah. Jika tidak, kita lanjutkan ke
langkah berikutnya.
b. Dari
solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat
sekumpulan solusi usulan yang baru.
c. Untuk
setiap elemen kumpulan solusi tersebut, lakukanlah hal-hal berikut ini :
1. Kirimkanlah
elemen ini ke fungsi uji. Jika elemen ini merupakan sebuah solusi, berhentilah.
2. Jika
tidak, periksalah apakah elemen ini merupakan yang terdekat dengan solusi yang
telah diuji sejauh ini. Jika tidak, buanglah.
3. Ambilah
elemen terbaik yang ditemukan di atas dan pakailah sebagai solusi usulan
berikutnya. Langkah ini bersesuaian dengan langkah dalam ruang problema dengan
arah yang muncul sebagai yang tercepat dalam mencapai tujuan.
4. Kembalilah
ke langkah 2.
Masalah-masalah
yang mungkin timbul pada prosedur Hill Climbing :
ü Maksimum
lokal adalah suatu keadaan yang lebih baik daripada semua tetangganya namun
masih belum lebih baik dari suatu keadaan lain yang jauh letaknya darinya.
ü Daratan (Plateau) adalah suatu daerah datar dari
ruang pencarian (search) dimana semua himpunan keadaan tetangganya memiliki
nilai yang sama.
ü Punggung
(Ridge) adalah suatu daerah ruang pencarian (search) yang lebih tinggi daripada
daerah sekitarnya, namun tidak dapat dibalikkan oleh langkah–langkah tunggal ke
arah manapun.
Solusinya:
ü Melakukan
langkah balik (backtracking) ke simpul yang lebih awal dan mencoba bergerak ke
arah yang lain.
ü Melakukan
lompatan besar ke suatu arah untuk mencoba bagian ruang pencarian yang baru.
ü Menerapkan
dua atau lebih aturan sebelum melakukan uji coba. Ini bersesuaian dengan
bergerak ke beberapa arah sekaligus.
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
n!/2!(n-2)! atau sebanyak 6 kombinasi. Fungsi heuristic yang
digunakan adalah panjang lintasan yang terjadi.
Sumber :
