Perkuliahan minggu 4
Metode Pencarian dan Pelacakan 1
Hal penting dalam
menentukan keberhasilan sistem cerdas adalah kesuksesan dalam pencarian
Pencarian adalah suatu
proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan
ruang keadaan (state space)
Ruang keadaan merupakan
suatu ruang yang berisi semua keadaan yang mungkin.
Untuk mengukur
performansi metode pencarian terdapat empat kriteria yang dapat digunakan ;
·
Dua teknik pencarian dan pelacakan
·
Pencarian buta (blind search)
·
Pencarian melebar pertama (Breadth-First Search)
·
Pencarian mendalam pertama (Depth-First Search)
4.1
Metode Pencarian Buta (Blind Search) :
4.1.1
Breadth-First Search
·
Semua node pada level n akan dikunjungi
terlebih dahulu sebelum n+1
·
Mulai dari akar terus ke level 1 dari
kiri ke kanan
·
Kemudian ke level selanjutnya hingga
solusi ditemukan
Prosedur
breadth_first_search
Inisialisasi : open =
[start]; closed [ ]
While open = [ ] do
Begin
Hapuskan keadaan paling
kiri dari keadaan open,
sebutlah keadaan itu
dengan X;
Jika X merupakan tujuan
then return (sukses);
Buatlah semua child
dari X,Ambillah X dan masukkan pada closed;
Eliminasilah setiap
child X yang telah berada pada open atau closed,
yang akan menyebabkan loop dalam search;
Ambillah turunan di ujung kanan open sesuai
urutan penemuan-nya;
End;
- 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
Ø Membutuhkan waktu yang cukup lama, karena akan
menguji n level untuk mendapatkan solusi pada level yang ke-(n+1).
4.1.2
Depth-First Search
Proses pencarian dilakukan pada semua anaknya sebelum
dilakukan pencarian ke node-node yang selevel
prosedur depth_first_search
inisialisasi: open = [Start]; closed = []
while open x [] do
begin
hapuskan keadaan berikutnya dari sebelah kiri open,
sebutlah keadaan itu dengan X;
jika X merupakan tujuan then return(sukses);
buatlah semua child yang dimungkinkan dari X;
ambilah X dan masukkan pada closed;
eliminasilah setiap child X yang telah berada pada
eliminasilah setiap child X yang telah berada pada
open atau closed, yang akan menyebabkan
loop dalam search;
ambilah child X yang tersisa di ujung kanan
open sesuai urutan penemuannya;
end.
- Keuntungan :
o
Memori yang relative kecil
o
Secara kebetulan, akan menemukan solusi
tanpa harus menguji lebih banyak lagi
4.2 Metode Pencarian Heuristik
Heuristic adalah sebuah teknik yang mengembangkan
efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan
kelengkapan (completeness). Fungsi heuristic digunakan unuk mendapatkan solusi
yang diinginkan. Jenis –jenis Heuristic Searching :
- Generate and Test
- Hill Climbing
- Best First Search
- Alpha Beta Prunning, Means-End-Analysis, Constraint Satisfication, Simulated Anealing
Pencarian buta tidak selalu diterapkan dengan baik ;
- Waktu aksesnya yang cukup lama
- Besarnya memori yang diperlukan
Metode heuristic search diharapkan bisa
menyelesaikan permasalahan yang lebih besar
Metode heuristic search menggunakan suatu fungsi
yang menghitung biaya perkiraan (estimasi)
dari suatu simpul tertentu menuju ke simpul tujuan disebut Fungsi Heuristic
4.2.1
Generate
and Test
Metode ini merupakan pemggabungan antara depth-first
search dengan pelacakan mundur (backtracking),
yaitu bergerak kebelakang menuju pada suatu keadaan awal. Algoritma;
- Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal)
- Uji untuk melihat apakah node tersebut benar-benar merupak solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diaharapkan
- Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama
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
4.2.2
Hill
Climbing
Metode ini hamper sama
dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan
dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung
pada feedback (timbal balik) dari prosedur pengetesan. Tes yang berupa fungsi
heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil
terhadap keadaan-keadaan lainnya yang mungkin.
Algoritma
Simple HillClimbing
Kerjakan
langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada
operator baru yang akan diaplikasikan pada keadaan sekarang:
- Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
- Evaluasi keadaan baru tersebut :
- Jika keadaan baru merupakan tujuan, keluar
- Jika bukan tujuan, namun nilainya lebih baik dari pada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
- Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
Pada
simple Hill Climbing, ada 3 masalah yang mungkin;
- Algoritma akan berhenti kalau mencapai nilai optimum local
- Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi
- Tidak diijinkan untuk melihat satupun langkah sebelumnya.
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, 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 :
http://slideplayer.info/slide/3764086/
http://fryunfirst.blogspot.co.id/2015/06/pencarian-heuristik-heuristic-search.html
