2.
Heuristic Search
A. Pembangkitan
dan Pengujian (Generate and Test)
Metode ini
merupakan penggabungan antara depth-first search dengan pelacakan mundur
(backtracking), yaitu bergerak kebelakang menuju pada suatu keadaan
awal.
Algoritma:
1.Bangkitkan suatu kemungkinan
solusi(membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan
awal).
2.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.
3.Jika solusi ditemukan, keluar.
Jika tidak, ulangi kembali langkah pertama.
B. Pendakian
Bukit (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:
1. Cari operator yang belum
pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
a) Kerjakan langkah-langkah
berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang
akan diaplikasikan pada keadaan sekarang : Cari operator yang belum digunakan;
gunakan operator ini untuk mendapatkan keadaan yang baru.
b) Evaluasi keadaan baru
tersebut :
– Jika keadaan baru merupakan
tujuan, keluar
– Jika bukan tujuan, namun
nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru
tersebut menjadi keadaan sekarang.
– Jika keadaan
baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
Contoh : Traveling 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. Misal ada 4 kota dengan jarak antara tiap-tiap kota seperti berikut ini :
a) Solusi – solusi yang mungkin dengan menyusun kota-kota dalam
urutan
abjad,
misal :
A –
B – C – D : dengan panjang lintasan (=19)
A –
B – D – C : (=18)
A –
C – B – D : (=12)
A –
C – D – B : (=13)
Metode Simple Hill Climbing
Ruang keadaan
berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk
menukar posisi kota-kota yang bersebelahan. Fungsi heuristik yang digunakan adalah
panjang lintasan yang terjadi. Operator yang akan digunakan adalah menukar
urutan posisi 2 kota dalam 1 lintasan. Bila ada n kota, dan ingin mencari
kombinasi lintasan dengan menukar posisi urutan 2 kota, maka akan didapat
sebanyak
:
Keenam
kombinasi ini akan dipakai semuanya sebagaioperator, yaitu :
Tukar 1,2 =
menukar urutan posisi kota ke – 1 dengan kota ke – 2
Tukar 2,3 = menukar
urutan posisi kota ke – 2 dengan kota ke – 3
Tukar 3,4 = menukar
urutan posisi kota ke – 3 dengan kota ke – 4
Tukar 4,1 = menukar
urutan posisi kota ke – 4 dengan kota ke – 1
Tukar 2,4 = menukar
urutan posisi kota ke – 2 dengan kota ke – 4
Tukar 1,3 = menukar
urutan posisi kota ke – 1 dengan kota ke – 3
Metode Steepest – Ascent Hill Climbing
·
Steepest – ascent hill climbing hampir
sama dengan simple – ascent hill climbing, hanya saja gerakan pencarian tidak
dimulai dari kiri, tetapi berdasarkan nilai heuristik terbaik.
·
Keadaan awal, lintasan ABCD (=19).
·
Level pertama, hill climbing memilih
nilai heuristik terbaik yaitu ACBD (=12) sehingga ACBD menjadi pilihan
selanjutnya.
·
Level kedua, hill climbing memilih nilai
heuristik terbaik, karena nilai heuristik lebih besar dibanding ACBD, maka hasil
yang diperoleh lintasannya tetap ACBD (=12).
Sumber :
http://slideplayer.info/slide/2805739/
lily.staff.gunadarma.ac.id/Downloads/files/17559/Pertemuan2.pdf
Anik Nur Handayani,
ST., MT. T. Sutojo,S.Si.,M.Kom. Edy Mulyanto, S.Si.,M.Kom. Dr. VIncent
Suhartono. (2009). Kecerdasan Buatan. Yogyakarta: Andi.
