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, 8-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
dinamai dengan h1(n).
2. Total keseluruhan dari jarak tiap grid relatif terhadap
tempatnya yang sesuai (manhattan distance). Untuk
selanjutnya, fungsi heuristik ini dinamai dengan h2(n).
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
Berikut ini adalah jawaban dengan menggunakan metode greedy...
H1(N) =
H2(N)=
Perlu diingat bahwa proses evaluasi yang dilakukan akan selalu mengambil nilai heuristic yang paling kecil.
KESIMPULAN: Dengan dilihat dan dibandingkan goal state dari kedua heuristic tersebut, maka H1(N) lebih memungkinkan mendapat jalan atau cost yang lebih sedikit dan efisien daripada H2(N).
Tulisan ini dibuat untuk memenuhi tugas mata kuliah Pengantar Kecerdasan Tiruan (AI) yang diampu oleh Mia Kamayani ST, MT . Prodi Teknik Informatika Fakultas Teknik UHAMKA.
Referensi:
- http://kuliahkusayang.blogspot.co.id/2010/04/8-puzzle-problem-ai.html
- http://andiktaufiq.wordpress.com/2010/05/02/8-puzzle-problem-bagian-2/
- http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2010-2011/Makalah2010/MakalahStima2010-011.pdf
Tidak ada komentar:
Posting Komentar