METODE PENCARIAN HC(Hill Climbing )

Hill Climbing ( HC ) atau pendakian bukit merupakan salah satu metode yang masuk dalam kategori metode pencarian heuristik. Dinamakan Hill Climbing ( HC ) atau pendakian bukit karena mempunyai aturan produksi dengan cara menukar dua posisi kota yang saling berdekatan seperti orang yang mendaki bukit. Hill Climbing ( HC ) dibagi menjadi dua jenis yaitu Simple HC ( HC sederhana ) dan Steepest-Ascent HC ( HC dengan memilih kemiringan yang paling tajam/curam ).
Simple HC ( SHC ) bekerja dengan cara memilih secara langsung new state yang memiliki keadaan lebih baik dari pada keadaan sebelumnya  tanpa memperhitungkan keadaan lain yang lebih “curam”. Berikut adalah algoritma dari SHC :

1. Evaluasi initial state (keadaan awal). Jika initial state adalah goal state    maka jadikan state ini sebagai solusi dan keluar dari program. Jika bukan goal state, lanjutkan proses dengan initial state sebagai current state.

2.Ulangi sampai solusi ditemukan atau sampai tidak ada operator ( aturan produksi ) baru yang dapat diaplikasikan terhadap current state :

a.Pilih operator yang belum diaplikasikan terhadap current state dan aplikasikan operator tersebut sehingga menghasilkan new state.
b.Evaluasi new state :
i.Jika state ini merupakan goal state maka jadikan state ini sebagai solusi dan keluar dari program.
ii.Jika state ini bukan goal state tetapi lebih baik dari current state maka jadikan state ini sebagai current state baru.
iii.Jika state ini tidak lebih baik dari current state maka kembali ke langkah 2.a.
Sedikit berbeda dengan SHC, Steepest-Ascent HC ( SAHC ) lebih menekankan pada aturan produksinya yaitu SHC akan mengevaluasi semua state yang berada dibawah current state dan memilih state dengan keadaan paling “curam”.  Berikut adalah algoritma dari SAHC :

1.Evaluasi initial state. Jika initial state adalah goal state maka jadikan state ini sebagai solusi dan keluar dari program. Jika bukan goal state, lanjutkan proses dengan initial state sebagai current state.
2.Ulangi sampai solusi ditemukan atau sampai tidak ada perubahan terhadap current state :
a.Misalkan SUK adalah suatu state yang menjadi suksesor dari current    state.
b.Untuk setiap operator yang bisa dilakukan terhadap current state, kerjakan :
i.Aplikasikan semua operator yang ada dan bangkitkan new state.
ii.Evaluasi new state. Jika merupakan goal state, jadikan ini sebagai solusi dan keluar dari program. Jika bukan goal state, bandingkan dengan new state  dengan SUK. Jika new state lebih baik dari SUK maka ganti SUK dengan new state. Jika new state tidak lebih baik dari SUK, tidak perlu diganti.
c.Jika SUK lebih baik dari current state maka ganti current state dengan SUK.