Metode Hill Climbing

Metode Hill Climbing hampir sama dengan metode pembangkitan & pengujian (Generate and Test), hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin. Hill Climbing adalah proses pengujian yang dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin. Metode Hill climbing merupakan variasi dari depth-first search. Dengan metode ini, eksplorasi terhadap keputusan dilakukan dengan cara depth-first search dengan mencari path yang bertujuan menurunkan cost untuk menuju kepada goal/keputusan. Yaitu dengan selalu memilih nilai heuristik terkecil. Dalam metode heuristik Hill Climbing, terdapat dua jenis Hill Climbing yang sedikit berbeda, yakni Simple Hill Climbing (Hill Climbing sederhana) dan Steepest-Ascent Hill Climbing (Hill Climbing dengan memilih kemiringan yang paling tajam / curam).

Menurut Kusumadewi (2003), cara kerja Hill Climbing adalah menentukan langkah berikutnya dengan menempatkan node yang akan muncul sedekat mungkin dengan sasarannya. Proses Pengujian dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan keadaan lainnya yang mungkin.

1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
2. 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 daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
• Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.

Berikut adalah contoh menyelesaikan Number Puzzle Slider dengan kondisi tertentu menggunakan Simple Hill Climbing; h(n) adalah nilai total heuristik dari kondisi puzzle. Bernilai 0 untuk posisi yang benar dan untuk posisi yang salah nilainya adalah jarak terpendek menuju posisi benar. Proses evaluasi yang dilakukan selalu mengambil nilai heuristik terkecil.