Algoritma Hill Climbing dan Iterative Deepening Search

Iterative Deepening Search

a.      Pengertian Iterative Deepening Search

Iterative Deepening Search (IDS) merupakan metode yang menggabungkan kelebihan Breadth First Search (BFS) yaitu complete dan optimal dengan kelebihan Depth First Search (DFS) yaitu space complexity rendah atau membutuhkan sedikit memori. Sehingga didapatkan metode searching yang optimal dan menggunakan sedikit storage. Tetapi konsekuensinya adalah time complexity-nya menjadi tinggi.

b.      Alur Algoritma Iterative Deepening Search

Mula mula IDS melakukan pencarian secara iteratif menggunakan metode Depth-Limited-Search DLS, dimulai dengan batasan level 0. Jika belum ditemukan solusi, maka dilakukan iterasi ke-2 dengan batasan level 1. Demikian seterusnya hingga ditemukan solusi.

Penelusuran di setiap proses pencariannya menggunakan cara kerja DFS, yaitu dengan menelusuri satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Demikian seterusnya sampai ditemukan solusi.

Penelusuran ini merupakan metode yang ada pada DFS. Dengan adanya kelebihan pada DFS, maka IDS hanya membutuhkan memori yang kecil. Dengan menggunakan cara BFS, metode IFS dapat menemukan solusi terbaik karena pencarian dilakukan secara merata terlebih dahulu hingga batas bertambah dan pengulangan terjadi.

c.       Implementasi Algoritma Iterative Deepening Search

Algoritma IDS dapat diimplementasikan atau diterapkan dalam penyelesaian permainan teka-teki kakuro.  Kakuro dimainkan pada sebuah tabel kotak-kotak yang mirip dengan permainan teka teki silang. Di dalam kakuro, jumlah dari nilai input harus sama dengan petunjuk yang tertera di kiri atau di atas. Pemain hanya bisa memasukkan angka dari 1 hingga 9, sehingga jumlah angka sama dengan petunjuk. Tidak boleh terdapat angka yang sama pada baris dan kolom yang sama. Hanya akan ada satu solusi untuk setiap puzzle.

Algoritma IDS dapat diimplementasikan kedalam :

1.      Dengan IDS, pembuat soal kakuro dapat menguji apakah soal yang telah dibuatnya mempunyai solusi atau tidak dengan menggunakan metode algoritma pencarian.

2.      Pencarian jawaban dalam kakuro lebih cepat.

3.      Aplikasi merupakan implementasi nyata dari kecerdasan buatan (artificial intelligence), terutama algoritma pencarian IDS untuk mencari penyelesaian dari suatu permasalahan, dalam hal ini soal Kakuro.

Hill Climbing

a.      Pengertian Hill Climbing

Hill Climbing merupakan salah satu metode yang masuk ke dalam metode pencarian heuristik. Metode pencarian heuristic/informed pencarian solusinya dilakukan menggunakan keadaan awal (initial state) dan aturan produksi berupa fungsi heuristik (suatu fungsi untuk menghitung nilai atau biaya perkiraan dari suatu solusi permasalah yang dicari) sebagai modal untuk melakukan iterasi menuju goal state.

b.      Alur Algoritma Hill Climbing

Hill Climbing (HC) dibagi menjadi dua bagian, yaitu: Simple Hill Climbing (SHC) dan SteepestAscent Hill Climbing (SAHC). Secara garis besar, langkah-langkah dari HC adalah sebagai berikut:

1.      Dibentuk lintasan awal sebagai keadaan awal (initial state), kemudian dilakukan pengujian dari keadaan awal tersebut. Pengujian dilakukan dengan menghitung total jarak yang ditempuh pada initial state. Pengujian tersebut dilakukan untuk mendapatkan nilai heuristik sebagai pembanding terhadap nilai-nilai heuristik yang ada setelah dilakukan kombinasi pertukaran dua kota. Hasil dari pengujian tersebut adalah jarak minimal yang ditempuh pada permasalahan TSP. Hasil tersebut akan digunakan sebagai pembanding hasil dari langkah berikutnya.

2.      Setelah dibentuk lintasan awal sebagai keadaan awal, langkah selanjutnya yaitu melakukan kombinasi penukaran dua kota kemudian dilakukan pengujian seperti pada poin a, hingga mencapai kondisi goal, jika tidak maka pilihlah elemen yang lain hingga mencapai goal. Kondisi goal diartikan sebagai keadaan yang merupakan solusi optimum dari permasalahan TSP dengan kondisi: panjang jalur baru < panjang jalur lama.

3.      Jika kondisi goal telah tercapai maka kondisi tersebut adalah solusinya, jika tidak, maka bukan solusinya.

c.       Implementasi Algoritma Hill Climbing

Dalam penggunaannya, algoritma hill climbing dapat diimplementasikan kedalam sistem penjadwalan kuliah. Suyanto (2007) menjelaskan algoritma SAHC sebagai berikut:

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

2)      Ulangi sampai solusi ditemukan atau sampai tidak ada perubahan terhadap current state:

a.      Misalkan SUK adalah suatu state yang menjadi suksesor sari current state.

b.      Untuk setiap operator yang bisa dilakukan terhadap current state, kerjakan:

                                                                             i.            Aplikasikan operator tersebut dan bangkitkan new state.

                                                                            ii.            Evaluasi new state. Jika merupakan goal state, kembalikan state ini sebagai solusi dan keluar dari program. Jika bukan goal state, bandingkan new state dengan SUK. Jika new state lebih baik dari SUK, maka ganti SUK dengan new state. Jika tidak lebih baik, SUK tidak perlu diganti.

3)      Jika SUK lebih baik dari current state, maka ganti current state dengan SUK.

Referensi

Hendrik, Jackri. (2017). Penerapan Algoritma Interative-Deepening Search (Ids) Dalam Penyelesaian Permainan Teka-Teki Kakuro. Informasi dan Teknologi Ilmiah (INTI).

Saifullah, Shoffan & Hermawan, Arief. (2016). Pengembangan sistem penjadwalan kuliah menggunakan algoritma steepest ascent hill climbing.

Irfan, Muhammad. (2018). Penyelesaian Travelling Salesman Problem ( TSP ) Menggunakan Algoritma Hill Climbing dan MATLAB.