PENERAPAN ALGORITMA A* UNTUK MENCARI SOLUSI DALAM PERMAINAN AKARI

22043504, Rudy Tri Hermanto (2011) PENERAPAN ALGORITMA A* UNTUK MENCARI SOLUSI DALAM PERMAINAN AKARI. Final Year Projects (S1) thesis, Universitas Kristen Duta Wacana.

	Text (Skripsi Informatika) 22043504_bab1_bab5_daftarpustaka.pdf Download (1MB)
	Text (Skripsi Informatika) 22043504_bab2-sd-bab4_lampiran.pdf Restricted to Registered users only Download (2MB) | Request a copy

Abstract

Permainan yang menggunakan logika banyak bermunculan, salah satunya permainan yang dikeluarkan oleh perusahaan Nikoli yang bernama Akari (Light Up). Permainan akari terdiri dari papan kotak yang berisi warna hitam dan putih. Pemain meletakkan lampu pada kotak yang berwarna putih dimana tiap baris dan kolom hanya boleh diletakkan satu lampu sampai kotak-kotak tersebut diterangi semua. Lampu akan menerangi kotak yang berwarna putih secara horisontal dan vertikal. Kotak hitam merupakan kotak yang tidak tembus cahaya, sehingga nyala lampu tidak dapat melewati kotak hitam tersebut. Sistem kecerdasan buatan dapat digunakan untuk membantu agar dapat menemukan solusi Permainan Akari. Sistem cerdas dibangun dengan menerapkan algoritma A* yang merupakan salah satu algoritma pencarian terbimbing (informed search), dengan menggunakan fungsi heuristik. Heuristik yang dirumuskan untuk mencari solusi permainan akari ini adalah jumlah antara baris kosong dan kolom kosong serta jumlah kombinasi dari kotak hitam angka dikali dengan konstanta1 dan konstanta2. Secara lengkap dapat dilihat pada persamaan dibawah ini : f(n) = g(n) + h(n) = (lampu kotak hitam + lampu) + ((jbp + jkp + Jumlah rCs – jkh) * konstanta1 * konstanta2) Berdasarkan hasil perumusan fungsi diatas maka algoritma A* ini, terbukti complete untuk menyelesaikan permainan akari. Waktu yang diperlukan untuk menemukan solusi dengan fungsi tersebut relatif cepat yaitu 8.6548 detik. Namun demikian untuk kondisi tertentu algoritma ini tidak dapat menemukan solusi. Kondisi dimana tidak dapat menemukan solusi adalah keadaan dimana jumlah sisi kotak hitam angka lebih besar dari jumlah lampu yang seharusnya berada disekeliling kotak hitam.

Actions (login required)

View Item