Nama : Burhanudin
Alif Rahmat
NPM : 12114255
Kelas : 3KA31
METODE PENCARIAN
Blind
Search dan Heuristic Search merupakan sub bahasan yang sifatnya fundamental
dalam mata kuliah Kecerdasan Buatan (Artificial Intelligence). Bahkan dalam
dunia nyata, kita sering dituntut untuk berpikir dengan cara-cara tersebut.
Seperti ketika bermain puzzle, catur, kubus cerdas, atau mengira-ngira rute
perjalanan mana yang akan kita tempuh. Semua itu terkait dengan otak kita yang
sudah otomatis berpikir dengan algoritma blind search atau heuristic search,
atau bahkan lebih kompleks lagi.
Heuristic
Search
Heuristik adalah
sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan
kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan
untuk mengevaluasi keadaankeadaan problema individual dan menentukan seberapa
jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
·
Generate & Test
Metode ini
merupakan penggabungan antara depth-first search dengan pelacakan mundur
(backtracking), yaitu bergerak kebelakang menuju pada suatu keadaan awal.
Algoritma:
- Bangkitkan suatu
kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan
tertentu dari keadaan awal).
- Uji untuk melihat
apakah node tersebut benar-benar merupakan solusinya dengan cara
membandingkan node terebut atau node akhir dari suatu lintasan yang
dipilih dengan kumpulan tujuan yang diharapkan.
- 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 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 metode Generate and Test
·
Hill Climbing
Metode ini hampir
sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian
dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya
tergantung pada feedback 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 Hill
Climbing
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 :
No comments:
Post a Comment