1. METODE PENCARIAN BUTA (BLIND SEARCH).
Pencarian buta
merupakan sekumpulan prosedur yang digunakan dalam melacak ruang keadaan.
Pencarian berlangsung sampai solusi terakhir ditemukan. Idenya adalah menguji
seluruh kemungkinan yang ada untuk menemukan solusi.
A.
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.
jadi hasil dari contoh diatas, kita akan melalui titik simpul A kemudian B,C,D setelah itu ke simpul E,F,G,H,I,J,K,L,M.
Langkah-langkah
algoritma BFS:
1. Masukkan simpul ujung (akar) ke dalam antrian.
2. Ambil simpul dari awal antrian, lalu cek
apakah simpul merupakan solusi.
3. Jika simpul merupakan solusi, pencarian
selesai dan hasil dikembalikan.
4. Jika simpul bukan
solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul
anak) ke dalam antrian.
5. Jika antrian kosong
dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi
tidak ditemukan.
6. Ulangi pencarian dari langkah kedua.
Contoh :
Mencari jalur angkutan umum dari terminal senen ke terminal Kp. Rambutan
* Initial State : Senen
* Goal State : Kp. Rambutan
Penjelasan
Gambar :
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).
B.
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 ditemuakn
“goal”nya dilanjutkan ke sisi sebelah kanan dan seterusnya sampai ditemukan
target/goal.
penjelasannya, node akan terus membaca simpul dari sebelah kiri sampai semua simpul menemukan goal success nya, setelah sebelah kiri habis, maka akan dilanjutkan ke sebelah kanan. rute nya S,A,C,D,B,E,,H,G.
Algoritma
:
1.
Buat
sebuah antrian, inisialisasi node pertama dengan Root dari tree
2.
Bila
node pertama, jika ≠ GOAL, node dihapus diganti dengan anak-anaknya dengan urutan LChild
3.
Bila
node pertama = GOAL, selesai
Contoh :
penjelasannya, jadi dia akan memulai mencari simpul dari sebelah kiri dahulu, baru setelah itu ke kanan sampai semua simpul sudah mendapatkan goalnya. Disini dari simpul A kemudian ke simpul B,D,E,F,G karena sebelah kiri sudah habis, maka rute dilanjutkan ke sebelah kana tree yaitu mulai dari simpul C,H,I,J,K. Maka kita telah menemukan goal dari rute ini.
2. 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).
A.
Generate & Test
Teknik ini merupakan gabungan dari DFS
dan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada
suatu keadaan awal. Dimana nilai pengujian berupa jawaban “ya” atau “tidak”.
Pendekatan ini meliputi langkah–langkah sebagai berikut :
1. Buatlah/bangkitkan sebuah solusi yang memungkinkan. Untuk
sebuah problema hal ini dapat berarti pembuatan sebuah titik khusus dalam ruang
problema.
2. Lakukan pengujian untuk melihat apakah solusi yang dibuat
benar–benar merupakan sebuah solusi, dengan cara membandingkan titik khusus
tersebut dengan goal-nya (solusi).
3. 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.
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
dikunjungin tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap
kota seperti gambar dibawah ini:
Penyelesaian dengan metode Generate
and Test
B.
Hill
Climbing
Hampir sama dengan teknik Generate and
Test dimana roses pengujian dilakukan dengan menggunakan fungsiheuristic.
Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari
prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan
menunjukkan seberapa baik nilai terkaan yang diambil terhadap
kesalahan-kesalahan lainnya yang mungkin. Teknik-teknik pada Hill
Climbing :
1. Teknik simple
hill climbing
Algoritma akan berhenti kalau mencapai
nilai optimum lokal. Urutan penggunaan operator akan sangat berpengaruh pada
penemuan solusi. Tidak diijinkan untuk melihat satupun langkah selanjutnya.
2. Teknik steepest
– ascent hill climbing
Hampir sama dengan simple hill climbing,
hanya saja gerakan pencarian tidak dimulai dari paling kiri. Gerakan
selanjutnya dicari berdasarkan nilaiheuristic terbaik.
Contoh :
Diketahui keadaan awal dan tujuan dari suatu
permainan kotak 8 puzzle, sebagai berikut :
penjelasannya, jadi kotak puzzle ini diselesaikan dengan cara pengurutan seperti hal nya mendaki, atau bisa disebut secara melingkar. Kotak pertama kita isi nilai yang paling kecil, kemudian sebelahnya mengurut sesuai urutan terkecil dan besar.
SUMBER :
