IMPLEMENTASI ALGORITMA SIMPLIFIED MEMORY BOUNDED A* UNTUK PENCARIAN KATA PADA PERMAINAN WORD SEARCH PUZZLE
Abstrak: Permainan word search
puzzle adalah permainan untuk mencari kata yang tersembunyi pada papan
permainan yang disusun dalam bentuk matriks. Kata-kata tersebut dapat disusun
secara horizontal, vertikal maupun tersusun dengan lebih dari satu ruas garis
yang terhubung secara horizontal dan vertikal. Pencarian kata yang tersusun
dengan lebih dari satu ruas garis memiliki karakteristik yang sama dengan
permasalahan pathfinding, sehingga membutuhkan suatu algoritma pathfinding
untuk melakukan pencarian. Algoritma Simplified Memory Bounded A* (SMA*) adalah
salah satu algoritma pathfinding yang dapat digunakan untuk melakukan pencarian
kata pada pada permainan word search puzzle. Algoritma SMA* memiliki kelebihan
pada penggunan memori yang lebih sedikit, hal ini dikarenakan penggunaan memori
dibatasi hingga jumlah simpul tertentu. Berdasarkan hasil pengujian bahwa
semakin panjang karakter pada kata yang dicari maka waktu pencarian akan
semakin lama dan penggunaan memori juga akan semakin besar. Semakin banyak
simpul yang tersedia untuk melakukan pancarian maka waktu pencarian akan
semakin cepat, dimana persentase peningkatan kecepatan pencarian dengan
penambahan simpul sebanyak 100% dapat meningkat hingga 21,99% dibandingkan
dengan tidak ada penambahan simpul.
Penulis : Asih Joko Purnomo, Galih Hermawan
Kode Jurnal: jptinformatikadd160999