tugas 3 informed search

Solusi permasalahan 8 puzzle mengunakan algoritma grady

PENDAHULUAN

Sliding Puzzle atau 8-Puzzle merupakan salah satu jenis permainan puzzle dimana kita harus mencapai goal puzzle dari initial puzzle yang diberikan. Untuk mencapai goal puzzle, sliding puzzle ini menyediakan satu grid kosong agar grid grid lain disekitarnya dapat digerakkan. Contoh puzzle ada dibawah ini.

Pada kesempatan ini, saya ingin memenuhi rasa ingin tahunya untuk penyelesaian puzzle ini dengan suatu algoritma, yaitu algoritma Greedy, dengan menggunakan dua fungsi heuristik sekaligus. 

                     

 Apa itu algoritma greedy?

   Algoritma Greedy merupakan algoritma yang sederhana dan lempeng (straightforward). Secara harafiah greedy artinya rakus atau tamak. Algoritma Greedy membentuk solusi langkah per langkah. Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya. 

Fungsi Heuristik

   Misalkan f(n) didefinisikan sebagai suatu fungsi heuristik. Fungsi heuristik f(n) adalah perkiraan biaya termurah dari node n ke node tujuan. Pada implementasi dari makalah ini, penulis menggunakan dua fungsi heuristik untuk mendapatkan solusi sliding puzzle.

Dua fungsi heuristik tersebut yaitu :

1. Banyak grid yang berada pada tempat yang salah, misal untuk kemudahan selanjutnya fungsi heuristik ini kita namai dengan h1(n). 

2. Total keseluruhan dari jarak tiap grid relatif terhadap tempatnya yang sesuai (manhattan distance). Untuk selanjutnya, fungsi heuristik ini kita namai dengan h2(n).

dari gambar puzzle diatas, kita dapat menghitung kedua fungsi heuristik, yaitu :

 1. h1(n) = 6, didapat dari grid angka 8, 7, 4, 3, 1, dan 5 yang menempati tempat yang salah.

 2. h2(n) = 14, didapat dari jarak dari posisi grid angka 8, 7, 4, 3, 1, dan 5 ke tempat yang seharusnya.

Ada 4 operator yang dapat digunakan untuk menggerakkan dari satu keadaan ke keadaan yang baru.

1. Ubin kosong digeser ke kiri
2. Ubin kosong digeser ke kanan
3. Ubin kosong digeser ke bawah
4. Ubin kosong digeser ke atas