2. Teknik pencarian Hill Climbing
Teknik Hill Climbing adalah
pengembangan dari teknik Generate-and-Test, dengan penambahan adanya umpan
balik dari prosedur test yang sudah digunakan untuk membantu memilih arah mana
yang harus ditelusuri pada setiap area search.
Pada prosedur Generate-and-Test
yang murni, fungsi test hanya ditanggapi dengan Ya atau Tidak. Tetapi pada
Hill-Climbing fungsi test ditambahkan dengan fungsi heuristic atau fungsi
objectif yang memungkinkan perkiraan seberapa dekat simpul yang ditelusuri terhadap
goal state.
Hill-climbing sering kali digunakan
jika fungsi heuristic yang baik tersedia untuk mengevaluasi stata, tapi ketika
tidak ada lagi pengetahuan yang dapat digunakan.
Sebagai contoh, anda berada disuatu
kota yang belum pernah anda kunjungi tanpa memiliki peta. Tujuannya menuju
gedung tertinggi yang terlihat dari tempat anda berada.
Fungsi heuristic adalah hanya
masalah jarak antara lokasi anda berada dengan letak gedung tertinggi dan
bagaimana menemukan jarak yang terdekat atau cara tercepat menuju gedung
tertinggi.
Penyelesaian masalah diatas dimulai
dengan meninjau karakteristik masalah, apakah solusi yang pertama ditemukan
dapat diterima sebagai solusi yang baik ? (mutlak atau relatif ?) Karena tidak
ada peta dan tidak ada pengalaman memilih jalan (tidak ada pengetahuan) maka
dipilih saja jalan yang arahnya menuju solusi sampai kita tiba di tujuan tanpa
mengulangi atau mencoba lagi jalur yang lain dan kita terima itu sebagai solusi
terbaik (dgn mengabaikan kemungkinan lain).
Jadi adalah masuk akal menerapkan
hill-climbing ketika tidak ada alternatif yang dapat diterima untuk memilih
atau menuju pada suatu stata.
Algoritma Simple Hill Climbing :
- Evaluasi
initial state. Jika ini goal state maka return dan keluar. Jika bukan maka
lanjutkan dengan initial state sebagai current state.
- Ulangi
langkah berikut sampai menemukan solusi atau sampai tidak ada lagi
operator yang dapat digunakan pada current state
a.
Pilih operator yang belum digunakan pada current state dan
gunakan untuk menghasilkan/menuju stata baru
b.
Evaluasi stata baru.
i. Jika ini goal state maka return dan keluar
ii. Jika bukan goal state tetapi lebih baik dari
current state
maka jadikan stata baru sebagai current
state
iii.
Jika tidak lebih baik dari current state lanjutkan
perulangan
