1.
Metode Pencarian Buta (Blind Searching)
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 dibuka (node selanjutnya tidak diketahui).
- Kalau ada solusi maka solusi akan ditemukan
- Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).
Jenis-jenis dalam Blind Searching
yaitu :
- · Breadth-First Search (Pencarian Melebar Pertama)
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
metode 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 ke-1 dari kiri ke kanan, kemudian berpindah ke level
berikutnya demikian pula dari kiri ke kanan sampai ditemukannya solusi
.
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
Keuntungan :
– Tidak akan menemui jalan buntu
– Jika ada satu solusi, maka
breadth first search akan menemukannya. Dan jika ada lebih dari satu solusi,
maka solusi minimum akan ditemukan.
Kelemahan :
– Membutuhkan memori yang cukup
banyak, karena menyimpan semua node dalam satu pohon
– Kemungkinan ditemukan optimal
local
Contoh :
1.
Membangkitakan anak dari terminal Senen =
Terminal blok M, Terminal Pulo Gadung, Terminal Manggarai
2.
Karena goal state (Terminal Kp. Rambutan) belum
tercapai maka kita bangkitkan anak dari terminal senen
Terminal Blok M = Terminal Grogol, Terminal Lebak
Bulus
Terminal Lebak Bulus = Terminal Ciputat, Terminal Kp.
Rambutan.
Terminal Pulo Gadung = Terminal
bekasi
Terminal Manggarai = Terminal Cililitan, Terminal Harmoni
3.
Akhirnya tercapai Goal State (Terminal Kp.
Rambutan).
- · Depth-First Search (Pencarian Mendalam Pertama)
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 ditemuakn “goal”nya dilanjutkan ke sisi
sebelah kanan dan seterusnya sampai ditemukan target/goal. Pada Depth First
Search, proses pencarian akan dilaksanakan pada semua anaknya sebelum dilakukan
pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level
yang lebih tinggi. Proses ini diulangi terus hingga ditemukannya solusi.
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
Keuntungan :
– Membutuhkan memori yang relatif
kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan
– Menemukan solusi tanpa harus
menguji lebih banyak lagi dalam ruang keadaan
Kelemahan :
– Kemungkinan terjebak pada
optimal lokal
– Hanya akan mendapatkan 1 solusi
pada setiap pencarian
Contoh:
Pencarian dimulai dari simpul
sebelah kiri yaitu ABD karena D tidak memiliki anak maka lanjut ke sebelah
kanan yaitu E lalu FG. Anak-anak dari simpul B sudah habis maka lanjut ke
simpul C dan di teruskan ke HIJK. K merupakan goal state dari pohon tersebut
Pada prinsipnya, DFS ini
menggunakan tumpukan untuk menyimpan seluruh state yang ditemukan atau bisa
dikatakan bahwa DFS menggunakan metode LIFO (Last In First Out).
2. Metode Pencarian Heuristik
(Heuristic Search )
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.
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.
Jenis-jenis dalam Heuristic
Search yaitu :
- · Generate and Test (membangkitkan dan menguji)
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 :
Pendekatan ini meliputi langkah–langkah sebagai berikut :
11. Buatlah/bangkitkan
sebuah solusi yang memungkinkan. Untuk sebuah problema hal ini dapat berarti
pembuatan sebuah titik khusus dalam ruang problema.
22. Lakukan
pengujian untuk melihat apakah solusi yang dibuat benar–benar merupakan sebuah
solusi, dengan cara membandingkan titik khusus tersebut dengan goal-nya
(solusi).
33. Jika
telah diperoleh sebuah solusi, langkah – langkah tersebut dapat dihentikan.
Jika belum, kembalilah ke langkah pertama.
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.
Metode generate and test ini memang kurang efisien untuk masalah yang besar atau kompleks.
Metode generate and test ini memang kurang efisien untuk masalah yang besar atau kompleks.
“Travelling Salesman
Problem (TSP)” 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 kal i. Misalkan ada 4 kota
dengan jarak antara tiap-tiap kota seperti gambar di bawah ini:
Penyelesaian dengan Generate and Test
- · Hill Climbing (mendaki bukit)
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 prosedur Hill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan (goal).
Dalam prosedur buat dan uji yang murni, respon fungsi uji hanyalah ya atau tidak. Dalam prosedur Hill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan (goal).
Prosedur Hill Climbing :
11. 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.
22. Dari
solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat
sekumpulan solusi usulan yang baru.
33. Untuk
setiap elemen kumpulan solusi tersebut, lakukanlah hal-hal berikut ini :
11. Kirimkanlah
elemen ini ke fungsi uji. Jika elemen ini merupakan sebuah solusi, berhentilah.
22. Jika
tidak, periksalah apakah elemen ini merupakan yang terdekat dengan solusi yang
telah diuji sejauh ini. Jika tidak, buanglah.
33. 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.
44. 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.
Contoh:
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
l intasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan
sebanyak:
atau sebanyak 6 kombinasi (lihat
gambar dibawah). Fungsi heuristic yang digunakan adalah panjang lintasan yang
terjadi
Sumber:
