IMPLEMENTASI PEMECAHAN SLIDING TILE PUZZLE MENGGUNAKAN METODE HEURISTIK (ALGORITMA A*, IDA* DAN BDA*)

Abstract

Sliding tile puzzle adalah sebuah permainan acak angka, huruf atau gambar yang harus disusun ke dalam pola yang benar. Permainan ini biasanya terdiri dari 9 kotak angka, satu kotak kosong dan delapan kotak teracak. Tujuan permainan ini adalah menyelesaikan kotak yang sudah teracak menjadi sebuah susunan yang benar. Cara menyelesaikan puzzle ini dengan menggeser kotak – kotak yang ada sehingga mencapai puzzle kembali ke pola dengan angka berurut. Metode Heuristik (Heuristik searching) merupakan salah satu metode yang dapat digunakan untuk menyelesaikan permainan slide tile puzzle secara selektif, dengan memberikan solusi berupa jalur terpendek dan waktu yang efisien, sehingga memungkinkan pengguna dapat menyelesaikan permainan puzzle ini dengan baik, cepat dan relevan. Beberapa algoritma yang menggunakan fungsi heuristik adalah Algoritma A* (A Star), Algoritma Iterative Deepening A* (IDA*) dan Algoritma Bi-directional A* (BDA*). Fungsi heuristik yang digunakan adalah dengan melihat banyaknya kotak pada posisi salah dan total keseluruhan jarak dari kotak yang berada di tempat yang salah untuk mencapai posisi yang benar. Tujuan dari pembuatan proyek akhir ini untuk mengimplementasikan pemecahan Sliding Tile Puzzle Menggunakan Metode Heuristik (Algoritma A*, IDA* dan BDA*). Dari aplikasi ini dapat dilihat bahwa Algoritma A*, IDA* dan BDA* mampu memberikan jalur dalam penyelesaian Sliding Tile Puzzle. Setelah pengujian berulang yang dilakukan dengan menggunakan 200 dataset, dapat dilihat perbandingan hasil antara Algoritma A* dengan Algoritma IDA* dan Algoritma BDA* dimana Algoritma BDA* menghasilkan jalur yang lebih pendek dalam menyelesaikan Sliding Tile Puzzle.