vii
PERBANDINGAN ANSWER SET PROGRAMMING DAN ITERATIVE DEEPENING SEARCH DALAM MENYELESAIKAN GAME N-PUZZLE
TEGUH FAJAR NURBIANSYAH
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012
vii
PERBANDINGAN ANSWER SET PROGRAMMING DAN ITERATIVE DEEPENING SEARCH DALAM MENYELESAIKAN GAME N-PUZZLE
TEGUH FAJAR NURBIANSYAH
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Departemen Ilmu Komputer
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012
vii
ABSTRACT TEGUH FAJAR NURBIANSYAH. Application Solver N-puzzle with Answer Set Programming and Iterative Deepening Search. Supervised by MUSHTHOFA. N-puzzle is one of the known NP-complete problems in the field of puzzles and games. The purpose of N-puzzle is to arrange numbers from 1 to (n2-1) in an n x n grid, with one grid contains a blank square. The research aims to compare the use of Answer Set Programming (ASP), as one of the currently used formalism to express and solve hard computational problems, with the traditional Iterative Deepening Search (IDS) in solving the N-puzzle. An encoding of N-puzzle problem and solver was devised and executed using the DLV system, while IDS is implemented as an ad-hoc program solving the N-puzzle problem. The result of experiment shows that the ASP using DLV is more effective in finding solutions, because it requires no depth parameters to find solutions, while IDS does. On the other hand, the IDS implementation was more efficient in terms of execution time. Keywords : Answer Set Programming, Iterative Deepening Search, Logic Programming, N-puzzle.
viii
Judul Skripsi Nama NIM
: Perbandingan Answer Set Programming dan Iterative Deepening Search dalam Menyelesaikan Game N-puzzle : Teguh Fajar Nurbiansyah : G64086015
Menyetujui: Dosen Pembimbing
Mushthofa SKom MSc NIP. 19820325 200912 1 003
Mengetahui: Ketua Departemen Ilmu Komputer Institut Pertanian Bogor
Dr Ir Agus Buono MSi M Kom NIP. 19660721 99302 1 001
Tanggal Lulus :
vii
PRAKATA Alhamdulillaahirabbil ‘aalamiin, segala puji dan syukur penulis panjatkan kepada Allah Subhanahu wata’ala atas segala curahan rahmat dan karunia-Nya sehingga penelitian ini berhasil diselesaikan. Sholawat dan salam semoga senantiasa tercurah kepada Nabi Muhammad Shalallahu ‘alaihi wassalam, keluarganya, para sahabat, serta para pengikutnya. Karya tulis ini merupakan salah satu syarat memperoleh gelar Sarjana Komputer di Departemen Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA). Judul dari karya ilmiah ini adalah Perbandingan Answer Set Programming dan Iterative Deepening Search dalam Menyelesaikan Game N-puzzle. Penulis juga menyampaikan terima kasih kepada Bapak Mushthofa SKom MSc selaku pembimbing yang telah meluangkan waktu dan tenaganya untuk membimbing penulis, memberikan ilmu-ilmu yang sangat berharga, serta dukungan selama penelitian ini berjalan. Penyelesaian penelitian ini tidak terlepas dari dukungan dan bantuan berbagai pihak, oleh karena itu penulis ingin mengucapkan terima kasih sebesar-besarnya kepada: 1 Kedua orang tua tercinta Ayahanda Deddy Mulyadi, SE dan Ibunda Eti Rohayati, AmKeb, adik penulis yang bernama Dewi Intan Permata Hati, dan segenap keluarga besar penulis atas do’a, dukungan, semangat, kasih sayang, dan perhatian yang tidak pernah berhenti diberikan selama ini, 2 Bapak Endang Purnama Giri, SKom, MKom dan Ibu Dr Yeni Herdiyeni, SSi, MKom selaku dosen penguji, atas waktu, ilmu, kesabaran, nasihat, dan masukan yang diberikan, 3 Mutia Fijri Taufani SKom, Riyan Adi Lesmana, Herman Gusti Anugrah, serta teman-teman mahasiswa Sarjana Penyelenggaraan Khusus Ilmu Komputer, Departemen Ilmu Komputer, FMIPA Institut Pertanian Bogor (IPB) khususnya angkatan 3, serta teman-teman lain yang tidak dapat penulis sebutkan satu per satu atas bantuan, motivasi, kebersamaan, serta semangat kepada penulis, 4 Departemen Ilmu Komputer, Bapak/Ibu Dosen dan Tenaga Kependidikan yang telah begitu banyak membantu baik selama pelaksanaan penelitian ini maupun sebelumnya. Kepada semua pihak lainnya yang telah memberikan kontribusi yang besar selama pengerjaan penelitian ini yang tidak dapat disebutkan satu per satu, penulis ucapkan terima kasih banyak. Segala kesempurnaan hanya milik Allah Subhanahu wata’ala. Semoga hasil penelitian ini dapat bermanfaat, Amin.
Bogor, Juni 2012
Teguh Fajar Nurbiansyah
0
RIWAYAT HIDUP Penulis yang bernama Teguh Fajar Nurbiansyah dilahirkan di Jakarta pada tanggal 11 Juli 1987 sebagai anak pertama dari dua bersaudara dari pasangan Bapak Deddy Mulyadi SE dan Ibu Bidan Eti Rochayati AmKeb. Pada tahun 1999, penulis lulus dari SD Negeri Bangka 3, kemudian pada tahun 2002, penulis lulus dari SLTP Negeri 5 Bogor, dan pada tahun 2005, penulis lulus dari SMU Negeri 8 Bogor. Pada tahun yang sama, penulis diterima sebagai mahasiswa di Institut Pertanian Bogor (IPB) pada Program Studi Diploma 3, Program Keahlian Manajemen Informatika, Direktorat Diploma IPB melalui jalur reguler. Penulis melaksanakan praktek kerja lapang di PT.Unitex,tbk selama dua bulan dan menyelesaikan pendidikan Diploma 3 selama tiga tahun dari tahun 2005 sampai dengan 2008. Setelah lulus, penulis memutuskan untuk melanjutkan pendidikannya sebagai mahasiswa Program Sarjana Penyelenggaraan Khusus, Departemen Ilmu Komputer, IPB pada tahun 2008. Selama melaksanakan kuliahnya, penulis juga pernah bekerja sebagai tenaga bantuan di SIMPEG BKPP Kota Bogor sejak bulan Oktober 2009 sampai dengan Desember 2009.
v
DAFTAR ISI Halaman DAFTAR TABEL ............................................................................................................................ vi DAFTAR GAMBAR ...................................................................................................................... vi DAFTAR LAMPIRAN .................................................................................................................... vi PENDAHULUAN............................................................................................................................. 1 Latar Belakang............................................................................................................................. 1 Tujuan Penelitian ......................................................................................................................... 1 Ruang Lingkup ............................................................................................................................ 1 Manfaat ........................................................................................................................................ 1 METODE PENELITIAN .................................................................................................................. 2 Logic N-puzzle ............................................................................................................................. 2 Back End...................................................................................................................................... 2 Pembangkitan Soal N-puzzle ....................................................................................................... 2 Generate Plan Penyelesaian N-puzzle ......................................................................................... 3 Pembangunan Front End ............................................................................................................. 3 Komunikasi ................................................................................................................................. 4 Arsitektur Sistem ......................................................................................................................... 4 HASIL DAN PEMBAHASAN ......................................................................................................... 4 Domain Masalah dalam DLV ...................................................................................................... 4 Encoding dengan DLV ................................................................................................................ 4 Menjalankan Model Penyelesaian N-puzzle ................................................................................ 5 Struktur Data pada C++ ............................................................................................................... 6 Penyelesaian N-puzzle dengan C++ ............................................................................................. 6 Hasil Pengujian ............................................................................................................................ 8 KESIMPULAN DAN SARAN ....................................................................................................... 10 Kesimpulan ................................................................................................................................ 10 Saran .......................................................................................................................................... 11 DAFTAR PUSTAKA ..................................................................................................................... 11 LAMPIRAN .................................................................................................................................... 12
v
vi
DAFTAR TABEL Halaman 1 Waktu eksekusi dan kondisi selesai dari teknik ASP dan PP untuk 8-puzzle. ............................. 9 2 Waktu eksekusi dan kondisi selesai dari teknik ASP dan PP untuk 15-puzzle. ........................... 9 3 Waktu eksekusi dan kondisi selesai dari teknik ASP dan PP untuk 24-puzzle. ........................... 9 4 Waktu eksekusi dan kondisi selesai dari teknik ASP dan PP untuk 35-puzzle. ......................... 10
DAFTAR GAMBAR Halaman 1 2 3 4 5 6 7 8 9 10 11 12 13
Diagram alur langkah penelitian. ................................................................................................ 2 Langkah awal pengacakan puzzle. .............................................................................................. 3 Langkah pengacakan puzzle. ....................................................................................................... 3 Langkah pengacakan puzzle. ....................................................................................................... 3 Arsitektur sistem. ........................................................................................................................ 4 Diagram alur proses N-puzzle. .................................................................................................... 4 Soal N-puzzle yang dibangkitkan. ............................................................................................... 4 Solusi N-puzzle............................................................................................................................ 6 Menyimpan soal N-puzzle ke array. ........................................................................................... 6 Pergerakan N-puzzle. ................................................................................................................... 7 Pergerakan puzzle pada array...................................................................................................... 7 Path dari soal sampai solved. ...................................................................................................... 8 Backtrack dan prioritas langkah berikutnya. ............................................................................... 8
DAFTAR LAMPIRAN Halaman 1 Pseudo code program C++ untuk pembangkitan soal N-puzzle. ................................................ 13 2 Program DLV, Pembangkitan kemungkinan gerak pada langkah pertama (T=0). .................... 14 3 Program DLV, Pembangkitan kemungkinan gerak pada langkah berikutnya (T>0). ................ 15 4 Program DLV, akibat jika terjadi gerakan (move). ................................................................... 17 5 Program DLV, kondisi state pada nilai yang tidak bergerak (frame axiom). ............................. 18 6 Pseudo code program C++, membaca soal N-puzzle yang dibangkitkan. ................................. 19 7 Pseudo code program C++, memeriksa apakah N-puzzle sudah selesai (solve)......................... 20 8 Pseudo code program C++, iterasi yang memanggil fungsi menggerakan puzzle. .................... 21 9 Hasil Pengujian untuk N-puzzle 3x3 (8-puzzle). ........................................................................ 22 10 Hasil Pengujian untuk N-puzzle 4x4 (15-puzzle)........................................................................ 23 11 Hasil Pengujian untuk N-puzzle 5x5 (24-puzzle)........................................................................ 24 12 Hasil Pengujian untuk N-puzzle 6x6 (35-puzzle)........................................................................ 25
vi
1
PENDAHULUAN Latar Belakang N-Puzzle adalah permainan teka-teki untuk mencari langkah agar puzzle yang berisi sekumpulan angka dapat terurut (Kendall et al. 2008). Salah satu cara penyelesaian Npuzzle dilakukan dengan mencari semua kemungkinan langkah yang mencapai solusi. Gambaran yang sangat baik untuk permasalahan N-puzzle dapat direpresentasikan dengan 8-puzzle, 15-puzzle, dan 24-puzzle. Permainan 8-puzzle mudah untuk diselesaikan sebagai ruang pencarian yang relatif kecil. Teknik *IDA adalah algoritme yang pertama kali berhasil menemukan solusi optimal untuk masalah 15-puzzle. Namun, dengan algoritme ini solusi optimal untuk 24puzzle tidak dapat dihasilkan dalam waktu yang wajar (Kendall et al. 2008). Mencari solusi untuk N-puzzle dengan langkah paling sedikit telah terbukti NP-Complete (Ratner & Warmuth 1990). Pencarian semua kemungkinan solusi dapat menyebabkan kompleksitas dari algoritme penyelesaiannya menjadi eksponensial. Hal tersebut bergantung pada ukuran puzzle. Permasalahan pencarian solusi seperti ini disebut Nondeterministic Polynomial-time Complete (NP-Complete) (Cormen et al. 2001). Penyelesaian N-puzzle pada komputer yang dilakukan dengan paradigma teknik pemrograman imperatif atau prosedural menjadi cukup sulit. Hal tersebut disebabkan programmer harus memberikan sekumpulan perintah langkah-langkah yang harus dilakukan komputer secara detail, mulai dari menerima masukan, menentukan struktur data, banyaknya looping, pemanggilan fungsi, sampai proses perhitungan dilakukan. Perintah-perintah tersebut akan dieksekusi baris per baris secara berurutan oleh komputer. Hal tersebut menyebabkan kode program menjadi panjang dan rumit. Iterative deepening search (IDS) merupakan salah satu teknik pemrograman dengan paradigma imperatif. IDS menggabungkan optimalisasi breadth-first search (BFS) dengan depth-first search (DFS) yang beroperasi dengan batas pencarian yang diperpanjang secara berturut-turut (Reinefed & Marsland 1993).
Untuk itu, penulis mencoba membangun N-puzzle solver dengan menggunakan answer set programming (ASP) sebagai pendekatan yang berbeda dengan IDS. Penulis bermaksud membandingkan ASP dan IDS berdasarkan kinerja model penyelesaian yang dibangun. Hal-hal yang menjadi pertimbangan adalah tingkat kesulitan kontrol pada kode program, panjang-pendeknya kode program, waktu eksekusi, dan kemampuan menyelesaikan puzzle (selesai atau tidak). ASP sendiri merupakan teknik pemrogaman berorientasi deklaratif untuk pencarian solusi pada permasalahan yang sulit (Lifschitz 2008). ASP hanya menggunakan ekspresi logika untuk membuat model penyelesaian suatu permasalahan. Tujuan Penelitian Penelitian ini bertujuan membuat model untuk penyelesaian game N-puzzle masingmasing memanfaatkan ASP dan IDS. Selanjutnya, penelitian ini akan membandingkan kinerja dari model-model penyelesaian tersebut. Ruang Lingkup Ruang lingkup penelitian ini adalah:
permasalahan
pada
1 Model penyelesaian ASP dibuat dengan datalog with disjunction (DLV) dan model penyelesaian IDS menggunakan C++. 2 Pembangkitan soal N-puzzle antarmuka dibuat dengan PHP.
dan
3 Soal N-puzzle yang dibangkitkan dengan bentuk n x n, di antaranya 3-puzzle, 8puzzle, 15-puzzle, dan 24-puzzle. 4 Ukuran perbandingan yang digunakan adalah kemampuan dan kecepatan solver dalam menemukan solusi. Kecepatan solver dihitung berdasarkan waktu penyelesaiannya. Manfaat penelitian ini adalah Manfaat menunjukkan bahwa ASP bisa menyelesaikan masalah NP-Complete pada N-puzzle sebagaimana imperative programming dapat melakukannya. Diharapkan model penyelesaian dengan ASP dapat mencari path yang selalu mencapai solusi, tapi tetap bisa diterima oleh logika manusia.
2
Back End
METODE PENELITIAN
Bagian back end akan melakukan proses pembangkitan dan penyelesaian permainan Npuzzle. Secara lebih spesifik, back end akan terdiri atas empat modul, yaitu:
Studi Literatur
Logika N-puzzle
Representasi Logika
Algoritme IDS
Pembangunan Back end
Encoding
Implementasi C++
DLV Solver
IDS Solver
Pembangunan Front end
Pengujian dengan DLV
Pembangkitan Soal N-puzzle
Pengujian dengan IDS
Analisa Hasil Pengujian
Perbandingan Solusi yang dihasilkan
Gambar 1 Diagram alur langkah penelitian. Logic N-puzzle Seperti pada Gambar 1, bagian logic Npuzzle merupakan elemen paling penting dalam penelitian ini. Bagian ini menerapkan aturan-aturan yang diizinkan pada permainan ini ke pembangkitan dan penyelesaian Npuzzle. Berikut adalah aturan-aturan logic dari N-puzzle: 1 N-puzzle berbentuk segi n atau n x n grid, dengan N = n2 -1. 2 N-puzzle terdiri dari N kotak bernilai 1 sampai N dan 1 buah kotak bernilai 0. 3 Pada pergerakan N-puzzle, hanya kotak bernilai 0 yang dapat bertukar dengan salah satu kotak yang adjacent dengannya. 4 Bergantung pada posisinya, kotak bernilai 0 memiliki dua, tiga, atau empat kotak yang adjacent. 5 Pada langkah pertama, kotak bernilai 0 dapat bergerak ke salah satu dari semua kotak yang adjacent dengannya. 6 Jika waktu sekarang adalah T, langkah ke T+1 kotak bernilai 0 boleh kembali ke posisi ketika bernilai 0 berada pada waktu T-1 boleh kembali secara langsung).
pada tidak kotak (tidak
7 Kondisi selesai (solve) adalah N-puzzle sudah terurut dari 1 sampai N dan kotak bernilai 0 ada di posisi n2 (kanan bawah).
1 Modul generate soal: membangkitkan soal N-puzzle dengan menspesifikasikan kondisi awal puzzle. 2 Modul logic: menangani aturan dan mekanisme berjalannya permainan Npuzzle. 3 Modul generate plan: mencari penyelesaian dari N-puzzle. Pada modul ini, akan ada strategi yang diterapkan untuk menyelesaikan N-puzzle. 4 Modul output: menuliskan ouput penyelesaian N-puzzle untuk komunikasi ke bagian front end. Pembangkitan Soal N-puzzle Pembangkitan soal N-puzzle bergantung pada ukuran puzzle dan banyaknya langkah pengacakan. Soal yang akan dibangkitkan adalah puzzle yang harus bisa diselesaikan atau dijamin terdapat solusi. Langkah pengacakan puzzle harus memenuhi aturan logic permainan N-puzzle. Berikut adalah aturan langkah pembangkitan soal N-puzzle: 1 Membuat N-puzzle yang sudah selesai (solve) berdasarkan ukuran yang dipilih. 2 Langkah pengacakan puzzle dilakukan dengan menukar 0 dengan salah satu kotak yang adjacent dengan posisi 0. 3 Banyaknya arah yang dituju yang tersedia bisa dua, tiga, atau empat bergantung pada posisi 0 dan adjacent yang tersedia. 4 Tujuan pergerakan 0 ke kotak yang adjacent dengannya dilakukan dengan pengacakan terhadap arah 0 yang dapat dituju. 5 Pada langkah berikutnya, langkah kembali ke posisi sebelumnya tidak boleh dilakukan. 6 Lakukan langkah pengacakan puzzle berdasarkan banyaknya langkah pengacakan puzzle yang dipilih. Berikut contoh pembangkitan N-puzzle dengan n=3 dan pengacakan puzzle sebanyak 3 langkah: 1 Mengacak dua arah yang tersedia (semua adjacent dari posisi 0). Pada Gambar 2 di bawah ini, hasil pengacakan arah adalah ke kiri.
3
akan terus dilakukan selama puzzle belum solve.
Gambar 2 Langkah awal pengacakan puzzle. 2 Mengacak dua arah yang tersedia karena tidak boleh kembali ke satu langkah sebelumnya. Pada Gambar 3 di bawah ini, hasil pengacakan arah adalah ke atas.
Gambar 3 Langkah pengacakan puzzle. 3 Mengacak tiga arah yang tersedia karena tidak boleh kembali ke satu langkah sebelumnya. Pada Gambar 4 di bawah ini, hasil pengacakan arah adalah ke kanan.
Gambar 4 Langkah pengacakan puzzle. Generate Plan Penyelesaian N-puzzle Generate plan akan menerapkan strategi untuk mencari solusi yang dapat menyelesaikan permasalahan N-puzzle. Dalam kasus ini, solusi adalah pencarian langkah menuju kondisi selesai (solve). Strategi yang diterapkan tetap harus dapat memenuhi logic dari permainan N-puzzle. Generate plan akan mencari semua kemungkinan gerak yang diizinkan logic N-puzzle dan menghitung langkah menuju solusi. Jika satu solusi sudah ditemukan, pencarian akan dihentikan. Pada ASP, representasi logika dan strategi pendekatan yang digunakan untuk menyelesaiakan masalah adalah guess and check (Musthofa 2010). Penerapan guess and check untuk pencarian solusi pada N-puzzle adalah sebagai berikut: 1 Guess: ASP akan menebak semua kemungkinan path yang menjadi kandidat solusi. Penebakan dilakukan berdasarkan kemungkinan arah gerak dari nilai 0 dengan memanfaatkan disjungsi. Hal ini
2 Check: ASP akan memeriksa semua kandidat solusi yang ditebak dengan memanfaatkan constraint. Kandidat solusi yang tidak diinginkan akan digugurkan oleh constraint. Dalam hal ini, semua path yang tidak mencapai solusi dieliminasi sehingga solusi yang dihasilkan adalah solusi yang benar, yaitu path yang mencapai kondisi solve. Model penyelesaian dengan ASP dibuat pada DLV. DLV adalah tool untuk mengomputasi answer set yang mengimplementasikan pemrograman logika disjungsi dengan menggunakan semantik answer set (Gelfond & Lifschitz 1991). Komputasi DLV adalah sound and complete. Maksud dari sound adalah solusi yang dihasilkan oleh DLV merupakan solusi yang benar, sedangkan maksud dari complete adalah semua solusi yang benar harus muncul. Algoritme iterative deepening search (IDS) digunakan sebagai strategi pembanding. IDS dibuat dengan menggunakan bahasa pemrograman C++. Ide dasar algoritme IDS adalah melakukan DFS dengan batas pencarian yang diperpanjang oleh kedalaman tree. Dengan pendekatan iterative, IDS dijamin menemukan solusi shortest path, seperti pada BFS (Reinefed & Marsland 1993). Pencarian Solusi dengan IDS adalah sebagai berikut: 1 Mendeteksi posisi 0 saat ini. 2 Mengunjungi semua node (adjacent) yang bisa dikunjungi menggunakan cara DFS dengan kedalaman tertentu. 3 Jika belum menemukan solusi (mencapai kondisi solve), lakukan kembali langkah nomor 2 dari awal dengan kedalaman ruang pencarian yang diperpanjang secara berturut-turut setiap pemanggilannya. Pembangunan Front End Front end akan dibangun menggunakan PHP dan JavaScript. Fungsi utama bagian front end adalah sebagai graphic user interface (GUI). Bagian front end terdiri atas tiga modul, yaitu: 1 Modul untuk generate problems akan memilih ukuran puzzle dan banyaknya langkah pengacakan.
4
2 Modul permainan untuk user akan menampilkan graphic user interface berupa soal N-puzzle yang dapat dimainkan oleh user dan solusinya.
HASIL DAN PEMBAHASAN
Bagian komunikasi akan mengodekan (encode) problem menjadi input untuk back end dan harus mengodekan kembali output dari back end menjadi representasi N-puzzle. Modul komunikasi akan dibangun dengan PHP.
Banyaknya arah bergerak untuk nilai 0 bergantung pada banyaknya adjacent dari nilai 0 tersebut. Selain itu, pergerakan Npuzzle tidak boleh kembali pada satu langkah tepat sebelumnya karena akan jadi gerakan yang percuma. Pembangkitan soal dimulai dari puzzle yang solve. Node yang dikunjungi akan dipilih secara random dari adjacent yang tersedia. Pseudo code dari pembangkitan Npuzzle lihat pada Lampiran 1. Penyelesaian Npuzzle dilakukan dengan dua cara yaitu answer set programming (ASP) dengan DLV dan iteration deepening search (IDS) dengan C++.
Arsitektur Sistem
Domain Masalah dalam DLV
3 Modul untuk pengujian akan menampilkan soal yang dibangkitkan, solusi yang dihasilkan, dan waktu penyelesaiannya. Komunikasi
Front end
Komunikasi
Generate problems N-puzzle (pilih ukuran dan pengacakan)
Back end
Generate soal
logic GUI
Parser
Generate plan
Pengujian N-puzzle
output
Gambar 5 Arsitektur sistem. Arsitektur sistem pada Gambar 5 terdiri atas tiga bagian yaitu, back end, front end, dan modul komunikasi. Back end untuk pembangkitan soal dikerjakan oleh PHP. Sedangkan untuk penyelesaian akan dikerjakan oleh DLV dan C++. Berdasarkan arsitektur sistem di atas, diagram alur proses N-puzzle sampai menghasilkan solusi dapat di lihat pada Gambar 6. Pembangkitan soal N-puzzle
N-puzzle solver
N-puzzle solved GUI
Pilih ukuran
N-puzzle
Npuzzle.txt (DLV)
Parsing output dari solver
Pilih jumlah pengacakan
solve5.cpp (solve5.exe)
Menampilkan hasil parsing ke bentuk representasi
Generate.php
solve10.cpp (solve.exe)
N-puzzle
solve15.cpp (solve15.exe)
Pengujian
Soal.dat
Idsgame.php (fungsi exec)
Gambar 6 Diagram alur proses N-puzzle.
Posisi sebuah nilai pada N-puzzle direpresentasikan dengan predikat at(T,N,X,Y). T menunjukkan waktu dari sebuah nilai N pada posisi dengan koordinat X,Y pada grid. Pada soal N-puzzle variabel T dimulai dari 0 dan akan bertambah sampai dengan waktu N-puzzle selesai (solve). Variabel N akan berisi nilai 0 sampai N pada N-puzzle. Variabel X dan Y bergantung pada ukuran puzzle. Soal N-puzzle yang dibangkitkan dibentuk menjadi himpunan predikat at dan menjadi fakta awal untuk permasalahan N-puzzle. Sebagai contoh soal N-puzzle dengan ukuran 3x3 seperti pada Gambar 7.
Gambar 7 Soal N-puzzle yang dibangkitkan. Soal N-puzzle pada Gambar 7 dikodekan ke dalam bentuk predikat seperti berikut : at(0,1,1,1). at(0,2,2,1). at(0,3,3,1). at(0,4,1,2). at(0,6,2,2). at(0,0,3,2). at(0,7,1,3). at(0,5,2,3). at(0,8,3,3).
Pergerakan angka 0 pada N-puzzle akan direpresentasikan dengan predikat move(T,X,Y) pada waktu T angka 0 akan bergerak ke koordinat X,Y. Encoding dengan DLV Pendekatan guess and check pada ASP diterapkan untuk penyelesaian menggunakan
5
DLV. Guess akan menebak semua kandidat solusi. Untuk menebak semua kandidat solusi kita mulai dengan mendefinisikan ruang pencarian yang memenuhi logic dari N-puzzle. Waktu melangkah, posisi nilai 0, kotak yang adjacent dengannya, dan kondisi puzzle akan menentukan ruang pencarian. Langkah pertama dan langkah-langkah berikutnya akan memiliki ruang pencarian yang berbeda. Pada langkah pertama, N-puzzle memiliki node tujuan sebanyak dua, tiga, atau empat tergantung pada jumlah adjacent dari nilai 0, sedangkan pada langkah berikutnya Npuzzle memiliki : node tujuan = adjacent – 1. Selain itu, pada langkah selanjutnya kondisi puzzle menjadi pertimbangan untuk melakukan langkah atau berhenti (selesai), sedangkan pada langkah pertama tidak. Hal ini disebabkan puzzle yang dibangkitkan tidak mungkin sudah solve dari awal. Jika posisi 0 seperti pada soal di Gambar 7, contoh aturannya sebagai berikut: move(1,2,2) v move(1,3,1) move(1,3,3) :- at(0,0,3,2).
v
Aturan di atas menjelaskan jika nilai 0 berada di sisi kanan puzzle dengan koordinat (3,2), nilai 0 memiliki tiga kemungkinan gerak, yaitu ke kiri (2,2), ke atas (3,1), dan ke bawah (3,3). Kode aturan gerakan pada langkah pertama yang lebih lengkap dapat dillihat pada Lampiran 2. Pada posisi yang sama, jika sebelumnya nilai 0 bergerak dari bawah (3,3) ke posisi tersebut (3,2), program akan memeriksa apakah puzzle sudah solve atau belum. Jika puzzle sudah solve, tidak akan melakukan langkah lagi dan program akan berhenti. Namun, jika puzzle belum solve, kemungkinan gerak nilai 0 tinggal ke kiri (2,2) atau ke atas (3,1). Kode aturan gerakan pada langkah berikutnya dapat dillihat pada Lampiran 3. Berikut adalah contoh aturannya : move(2,2,2) at(1,0,3,2), solved(1).
v
move(2,3,1) at(0,0,3,3),
:not
at(2,N,3,2) :at(1,N,2,2), move(2,2,2).
at(1,0,3,2),
Selain itu, kita juga harus membuat aturan frame axiom. Frame axiom berfungsi untuk menentukan kondisi state pada langkah selanjutnya untuk nilai-nilai yang tidak bergerak. Program akan terus menentukan frame axiom selama kondisi puzzle belum solve. Namun, jika puzzle sudah solve program akan berhenti menetukan frame axiom. Kode aturan frame axiom dapat dillihat pada Lampiran 5. Pada kasus di atas, contoh aturannya sebagai berikut : at(2,N,3,1) at(1,N,3,1), solved(1).
:not
at(1,0,3,2), move(2,3,1),not
Bagian terpenting dari logika adalah kita harus menentukan tujuan dari pencarian. Program dinyatakan selesai (solve) jika sudah mencapai tujuan pada waktu T. Berikut adalah aturan pada DLV untuk kondisi selesai (solve): solvedt :- solved(T).
Kondisi solved(T) adalah tujuan dari program, yaitu ketika N-puzzle sudah terurut. solved(T) dibangkitkan Kondisi berdasarkan ukuran puzzle dari soal yang dibangkitkan. Berikut adalah kondisi yang dibangkitkan untuk soal pada Gambar 7 di atas: solved(T) :- at(T,1,1,1), at(T,2,2,1), at(T,3,3,1), at(T,4,1,2), at(T,6,2,2), at(T,0,3,2), at(T,7,1,3), at(T,5,2,3), at(T,8,3,3).
Setelah guess menebak semua kandidat solusi, check akan memeriksa semua kandidat solusi yang dihasilkan dengan menggunakan constraint. Constraint akan menghapus answer set yang tidak memenuhi syarat. Pada N-puzzle, semua path langkah yang tidak menemukan kondisi selesai (solve) akan digugurkan, constraint akan ditulis sebagai berikut: :- solvedt.
Menjalankan Model Penyelesaian N-puzzle Selanjutnya, menentukan aturan pertukaran posisi 0 akibat terjadi suatu pergerakan. Jika pada aturan di atas menghasilkan move(2,2,2), nilai 0 akan bertukar posisi dengan nilai N yang pada T=1 berada di posisi 2,2. Kode aturan pertukaran posisi nilai 0 dapat dillihat pada Lampiran 4. Berikut adalah contoh bentuk aturannya: at(2,0,2,2) :at(1,N,2,2), move(2,2,2).
at(1,0,3,2),
Soal yang dibangkitkan akan dibuat dalam bentuk fakta dan kondisi solve dari N-puzzle. Setiap soal baru dibangkitkan, fakta dan kondisi solve dari soal tersebut akan ditulis ulang dalam file soal.dat, sedangkan model penyelesaian dengan program DLV akan Npuzzle.txt. disimpan dalam file Misalnya, telah dibangkitkan sebuah soal Npuzzle dengan ukuran 3 x 3 seperti pada Gambar 7. Berikut adalah representasi fakta
6
dan kondisi yang akan di tulis pada file soal.dat: #maxint=8. pos(1..3). angka(0..8). n(3). at(0,1,1,1). at(0,2,2,1). at(0,3,3,1). at(0,4,1,2). at(0,6,2,2). at(0,0,3,2). at(0,7,1,3). at(0,5,2,3). at(0,8,3,3). solved(T) :- at(T,1,1,1), at(T,3,3,1), at(T,6,2,2), at(T,7,1,3), at(T,8,3,3).
0 7 5 8
Penyelesaian N-puzzle dengan C++
at(T,2,2,1), at(T,4,1,2), at(T,0,3,2), at(T,5,2,3),
Fakta di atas diproses bersama dengan model penyelesaian pada file Npuzzle.txt oleh DLV. Output yang diminta hanya path langkah menuju solusi dan jumlah langkahnya. Berikut adalah eksekusi program DLV untuk soal pada Gambar7 : C:\solver>dlv.mingw.tgh soal.dat Npuzzle.txt –nofacts –filter = move, solved –silent {move(1,2,2), move(2,2,3), move(3,3,3), solved(3)}
Answer set di atas diterjemahkan kembali menjadi sebuah bentuk representasi N-puzzle seperti pada Gambar 8.
Gambar 8 Solusi N-puzzle. Struktur Data pada C++ Ukuran N-puzzle yang dipilih disimpan dalam file ukuran.dat dan soal N-puzzle yang dibangkitkan disimpan dalam file imperatif.dat. Soal N-puzzle yang dibangkitkan akan ditulis dengan format berikut: Nilai1 Nilai2 Nilai3 ...... NilaiN
Sama seperti DLV, program penyelesaian N-puzzle menggunakan C++ juga harus menerapkan logic dari N-puzzle. Pada C++, program dibuat dengan tiga buah fungsi, yaitu fungsi utama yang akan mengambil soal dan ukuran dari file, fungsi untuk memeriksa kondisi solve puzzle, dan fungsi untuk menggerakan puzzle. Program akan dimulai dengan membuka file ukuran.dat dan imperatif.dat untuk mendapatkan ukuran dan soal puzzle. Pseudo code untuk mendapatkan ukuran dan soal dapat dilihat pada Lampiran 6. Ukuran dan soal puzzle yang didapat menjadi input untuk program ini. Ukuran puzzle dikonversi dari sebuah string menjadi integer dan disimpan dalam sebuah variabel. Dengan cara yang sama, semua nilai pada soal N-puzzle akan disimpan ke dalam array satu dimensi. Penyimpanan nilai puzzle dan posisinya pada array dapat dilihat pada Gambar 9. Pada Gambar 9, posisi nilai pada N-puzzle diwakili indeks pada array, dengan indeks array dimulai dari 1. Langkah berikutnya program akan memeriksa puzzle sudah solve atau belum. Untuk memeriksa kondisi solve puzzle program akan menghitung jumlah jarak setiap posisi nilai saat konfigurasi puzzle solve terhadap posisi nilai pada konfigurasi saat ini. Berikut ini adalah rumus untuk memeriksa kondisi solve puzzle: ∑ |[nilai saat solve] – [posisi nilai saat ini]|
Posisi nilai saat ini dapat menggunakan nilai dari array. Pengecualian terjadi jika nilai array adalah 0, nilai 0 diganti menjadi banyaknya indeks pada array. Banyaknya indeks pada array adalah ukuran*ukuran. Misal untuk puzzle dengan ukuran 3 x 3, nilai 0 akan diganti menjadi 9, sedangkan nilai saat solve adalah indeks dari array untuk posisi nilai tersebut.
Sebagai contoh, penulisan soal N-puzzle pada Gambar 7 memiliki ukuran puzzle adalah 3 dan soal akan ditulis ke file imperatif.dat seperti berikut : 1 2 3 4 6
Gambar 9
Menyimpan soal N-puzzle ke array.
7
Jika total perhitungan tersebut bernilai 0, puzzle sudah solve dan program selesai, namun jika hasilnya lebih besar dari 0, puzzle belum terurut (not solve). Pseudo code untuk memeriksa kondisi solve array dapat dilihat pada Lampiran 7. Sebagai contoh untuk penjelasan perhitungan di atas, digunakan kondisi puzzle pada Gambar 9 : Hitsolve = |1-1| + |2-2| + |3-3| + |4-4| + |5-6| + |6-9| + |7-7| + |8-5| + |9-8| =0+0+0+0+1+3+0+3+1 =8 Hasil perhitungan di atas akan disimpan ke sebuah variabel. Anggap saja nama variabel tersebut adalah Hitsolve. Perhitungan di atas menghasilkan nilai yang lebih besar dari 0, sehingga puzzle dinyatakan belum terurut (not solve). Ketika puzzle belum terurut, program akan mencari path menuju goal state dari Npuzzle dengan teknik iterative deepening search (IDS). Fungsi utama akan memanggil fungsi yang bertugas menggerakan puzzle dengan parameter array dari puzzle, node tempat nilai 0 berada, node sebelumnya, ukuran puzzle, kedalaman ruang pencarian, status langkah (jika belum melangkah status langkahnya 0), dan kondisi puzzle. Selanjutnya, dengan fungsi yang menggerakan puzzle tersebut program akan melakukan pencarian path yang menuju solusi menggunakan teknik depth-first search (DFS) dengan kedalaman yang dibatasi. Sesuai logic, pergerakan posisi 0 bergantung dari posisinya pada puzzle, banyaknya adjacent, langkah sebelumnya, dan kondisi puzzle. Pada langkah pertama, karena belum melangkah pergerakan 0 tidak dipengaruhi oleh langkah sebelumnya. Fungsi yang menggerakan puzzle ini menerapkan prioritas penentuan arah langkah gerakan 0. Prioritas ini menentukan arah yang lebih dulu dituju oleh nilai 0. Arah yang tersedia bergantung pada adjacent dari posisi 0 dan langkah pertama atau bukan.
Gambar 10 Pergerakan N-puzzle.
Berdasarkan arah yang tersedia, pertama 0 diprioritaskan bergerak ke kanan, jika tidak menemukan tujuan setelah bactrack prioritas kedua 0 bergerak ke bawah, jika masih belum menemukan tujuan prioritas setelah bactrack prioritas berikutnya 0 bergerak ke kiri, dan terakhir ke atas. Prioritas berikutnya dilakukan jika pada pencarian pada prioritas sebelumnya tidak menemukan tujuan walaupun sudah mencapai batas kedalaman yang ditentukan dan kembali ke node sebelumnya (setelah bactrack dari prioritas sebelumnya). Seperti pada Gambar 10 di atas, prioritas bergerak 0 adalah ke bawah dulu, lalu ke kiri, dan terakhir ke atas. Pergerakan ke kanan tidak tersedia karena posisi 0 pada puzzle adalah sisi paling kanan. Sesuai gerakan 0 pada puzzle, posisi 0 pada array juga berubah berdasarkan pertukaran dengan adjacent dari posisi 0 pada puzzle. Jika posisi 0 ada pada indeks i,dan n adalah ukuran N-puzzle, pergerakan ke kanan posisi 0 akan bertukar dengan nilai yang berada pada indeks i+1 pada array, pergerakan ke bawah akan bertukar dengan nilai yang berada pada indeks i+n pada array, pergerakan ke kiri akan bertukar dengan nilai yang berada pada indeks i-1 pada array, dan pergerakan ke atas akan bertukar dengan nilai yang berada pada indeks i-n pada array. Jika 0 bergerak ke bawah seperti pada Gambar 10, posisi nilai pada array akan berubah seperti pada Gambar 11. Pada Gambar 11, posisi 0 yang sebelumnya pada indeks 6 di array, setelah pada puzzle posisi 0 bergerak ke bawah, nilai 0 akan berpindah posisi ke indeks 9 pada array. Posisi nilai 8 yang sebelumnya berada pada indeks ke 9 berpindah ke indeks 6 yang sebelumnya ditempati nilai 0. Fungsi yang menggerakan puzzle ini bersifat rekursif karena setelah melangkah (menggerakan posisi 0) fungsi ini akan memanggil dirinya sendiri dengan kondisi puzzle setelah melangkah untuk melakukan langkah berikutnya. Kondisi puzzle setelah melangkah meliputi posisi 0 saat ini, posisi 0 sebelumnya, nilai yang adjacent, dan kondisi puzzle.
Gambar 11 Pergerakan puzzle pada array.
8
Berikut adalah pseudo code untuk prioritas langkah dan pemanggilan dirinya sendiri: IF adjacent right available and previous THEN Go to adjacent right Increment step Call this function ELSE IF adjacent down available not previous THEN Go to adjacent down Increment step Call this function ELSE IF adjacent left available not previous THEN Go to adjacent left Increment step Call this function ELSE IF adjacent up available and previous THEN Go to adjacent up Increment step Call this function END IF
not
and
and
Namun, jika puzzle belum solve dan sudah melakukan pencarian sampai batas kedalaman, program akan melakukan backtrack ke langkah sebelumnya (super function) untuk melakukan langkah pada prioritas berikutnya. Jika pada langkah sebelumnya prioritas pertama 0 bergerak ke semua node di kanan dan buntu, setelah bactrack langkah yang dilakukan berdasarkan prioritas berikutnya (bukan ke kanan). Sebagai contoh, jika pada Gambar 9 nilai 0 bergerak ke bawah lalu buntu, setelah melakukan backtrack, puzzle akan melakukan langkah ke kiri seperti pada Gambar 13.
not
Jika posisi 0 berada di indeks paling akhir pada array, program akan memeriksa kondisi puzzle sudah solve atau belum. Berikut adalah pseudo code jika posisi 0 berada di indeks paling akhir pada array: IF position of 0 is number of puzzle THEN Cek solve IF puzzle solve THEN puzzle solved print END THIS function ELSE backtrack END IF END IF
Jika puzzle sudah solve, program akan mencetak array (konfigurasi puzzle) saat di node tersebut dan kembali ke super function (fungsi yang memanggil fungsi ini) untuk mencetak konfigurasi array-array sebelumnya sampai konfigurasi array soal, sehingga akan terbentuk path yang memiliki solusi dan program selesai seperti pada Gambar 12.
Gambar 12 Path dari soal sampai solved.
Gambar 13 Backtrack dan prioritas langkah berikutnya. Teknik iteration (iterasi) dari IDS diterapkan pada fungsi utama yang memanggil fungsi untuk menggerakan puzzle berkali-kali dengan batas kedalaman yang bertambah secara berturut-turut. Setiap fungsi utama memanggil fungsi ini kondisi puzzle dimulai dari kondisi awal (soal puzzle). Pseudo code untuk memanggil fungsi yang menggerakan puzzle dapat dilihat pada Lampiran 8. Namun, jika sudah melakukan teknik iterasi sampai batas maksimal kedalaman yang ditentukan tapi masih belum menemukan path yang mencapai solusi, program model penyelesaian N-puzzle dengan pemrograman IDS dinyatakan not solved. Hasil Pengujian Pengujian dilakukan dengan cara membangkitan masing-masing 10 soal Npuzzle untuk ukuran 3 x 3 (8-puzzle), 4 x 4 (15-puzzle), dan 5 x 5 (24-puzzle). Sebagai tambahan, untuk perbandingan dilakukan pengujian untuk puzzle ukuran 6 x 6 (35puzzle). Banyaknya langkah pengacakan didapatkan secara random. Tool DLV sendiri masih dalam tahap pengembangan. Hal ini menyebabkan program DLV yang dibangun belum dapat mengakomodasi penyelesaian untuk puzzle dengan ukuran lebih besar dari 6 x 6 (35-puzzle) walaupun teknik answer set programming yang digunakan untuk
9
penelitian ini dapat menyelesaikan semua ukuran N-puzzle.
rata-rata dihitung hanya dari waktu pencarian yang menemukan solusi.
Model penyelesaian yang digunakan adalah model penyelesaian permainan Npuzzle dengan DLV yang menggunakan answer set programming dibandingkan dengan model penyelesaian yang menggunakan teknik iterative deepening search dengan kedalaman maksimal 5, 10, dan 15. Semua soal yang dibangkitkan tersebut digunakan untuk menguji semua model penyelesaian yang dibangun. Pengujian dilakukan sampai solusi ditemukan atau sudah mengunjungi seluruh ruang pencarian sampai batas kedalaman yang ditentukan. Selain menguji pencarian mencapai solusi atau tidak, akan dihitung waktu eksekusi (satuan detik) beserta waktu rata-rata penyelesaian dari setiap solver untuk setiap ukuran. Waktu ratarata penyelesaian hanya dihitung dari waktu eksekusi solver yang mencapai solusi. Hasil pengujian waktu model penyelesaian dituliskan pada Tabel 1, Tabel 2, Tabel 3, dan Tabel 4.
Tabel 2 Waktu eksekusi dan kondisi selesai dari teknik ASP dan IDS untuk 15puzzle
Tabel 1 Waktu eksekusi dan kondisi selesai dari teknik ASP dan IDS untuk 8puzzle
Dari 10 soal 15-puzzle yang dibangkitkan, seluruhnya dapat diselesaikan dengan DLV dan IDS15. Sementara model IDS5 hanya berhasil menyelesaikan 1 soal dengan acak 5. Model IDS10 hanya berhasil menyelesaiakan 6 soal, yaitu 4 soal dengan acak 10 dan masing-masing 1 soal dengan acak 5 dan 6. Kemudian waktu rata-rata didapat dengan menghitung rata-rata dari waktu eksekusi yang berhasil menemukan solusi. Hal tersebut menyebabkan waktu rata-rata IDS5 hanya dihitung dari 1 waktu penyelesaian yang berhasil menemukan solusi pada langkah ke 5. Tabel 3 Waktu eksekusi dan kondisi selesai dari teknik ASP dan IDS untuk 24puzzle
Untuk 10 soal 8-puzzle yang dibangkitkan dengan jumlah langkah pengacakan yang berbeda, model penyelesaian (solver) dengan ASP (menggunakan DLV) dapat menyelesaikan seluruhnya. Model penyelesaian IDS dengan kedalaman pencarian 5 (IDS5) hanya mampu menyelesaikan 2 soal, yaitu soal dengan langkah pengacakan 4 dan 5 (acak 4 dan 5). Sedangkan model penyelesaian IDS dengan kedalaman pencarian 10 (IDS10) hanya mampu menyelesaikan 5 soal, yaitu 2 soal dengan langkah pengacakan 6 , dan masingmasing 1 soal dengan langkah pengacakan 4,5, dan 8. Model penyelesaian IDS dengan kedalaman pencarian 15 (IDS15) dapat menyelesaikan seluruh langkah pengacakan soal berada pada selang 1 sampai 15. Waktu
Dari 10 soal 24-puzzle yang dibangkitkan, seluruhnya dapat diselesaikan dengan DLV dan IDS15. Beberapa solusi pertama yang dimunculkan model DLV dapat menyelesaikan soal-soal tersebut dengan jumlah langkah menuju solved yang lebih besar dari 15 langkah. Hal ini disebabkan pada model DLV tidak perlu menentukan batas maksimal kedalaman pencarian yang bisa dicapai. Model IDS15 menyelesaikan soal tersebut dengan jumlah langkah yang lebih kecil atau sama dengan batas maksimal kedalaman pencarian yang ditentukan, yaitu
10
15. Sementara model IDS5 hanya mampu menyelesaikan 3 soal yang langkah pengacakan untuk pembangkitannya sebanyak 5 langkah atau lebih rendah. Model IDS10 hanya dapat menyelesaikan 6 soal dengan langkah pengacakan masing-masing 5, 10, 5, 10, 8, dan 3. Waktu rata-rata dihitung hanya dari waktu pencarian yang menemukan solusi. Tabel 4 Waktu eksekusi dan kondisi selesai dari teknik ASP dan IDS untuk 35puzzle
ukuran keunggulannya. Kelebihan ASP adalah kita tidak perlu menentukan kedalaman ruang pencarian. Model penyelesaian dengan DLV dapat menyelesaiakan soal N-puzzle untuk semua jenis pengacakan. Hal ini cukup berpengaruh karena saat soal dibangkitkan kita tidak mengetahui pada langkah ke berapa soal puzzle bisa mencapai solve. Model penyelesaian dengan IDS yang menggunakan C++ tidak dapat menyelesaiakan soal yang jumlah pengacakannya lebih besar dari kedalaman ruang pencarian. Pola untuk pencarian path yang mencapai solusi pada ASP tidak hanya satu karena mengandalkan guess and check, sedangkan pada C++ pola pencariannya hanya satu dengan memanfaatkan prioritas dan teknik IDS. Namun akibatnya ASP memiliki waktu penyelesaian yang lebih besar dari waktu penyelesaian dengan IDS.
KESIMPULAN DAN SARAN Dari 10 soal 35-puzzle yang dibangkitkan, seluruhnya dapat diselesaikan dengan DLV dan IDS15. Sama seperti pada 24-puzzle, beberapa solusi pertama yang dimunculkan model DLV dapat menyelesaikan soal-soal tersebut dengan jumlah langkah menuju solved yang lebih besar dari 15 langkah, sedangkan model IDS15 menyelesaikan soal tersebut dengan jumlah langkah yang lebih kecil atau sama dengan 15 langkah. Model IDS5 hanya mampu menyelesaikan 3 soal dengan acak 3, 2, dan 5. Model IDS10 hanya mampu menyelesaikan 6 soal, yaitu 3 soal yang bisa diselesaikan ids5 ditambah 3 soal dengan acak 10. Waktu rata-rata dihitung hanya dari waktu pencarian yang menemukan solusi. Untuk melihat hasil pengujian lebih lengkap yang disertai perbandingan penggunaan memori antara DLV dan IDS dapat dilihat pada Lampiran 9, Lampiran 10, Lampiran 11, dan Lampiran 12. Selain itu, pada hasil pengujian yang di tampilkan pada Lampiran 9, Lampiran 10, Lampiran 11, dan Lampiran 12 disertakan perhitungan banyaknya node yang dikunjungi dengan teknik IDS sampai dengan solve. Sesuai dengan tujuan dari penelitian yaitu membuat dan membandingkan model penyelesaian untuk N-puzzle dengan answer set programming (ASP) dan iterative deepening search (IDS), hasil penelitian menunjukan keduanya memiliki keunggulan dan kekurangan. Hal ini bergantung pada
Kesimpulan Answer Set Programming (ASP) akan menyelesaikan N-puzzle seperti cara berpikir manusia dengan mengodekan program ke dalam bahasa logika. ASP akan menebak semua kemungkinan path menuju solusi, lalu memeriksa semua path yang ditebak mencapai solusi atau tidak, sedangkan pada Iterative Deepening Search (IDS), programmer harus menuliskan perintah-perintah yang akan mengendalikan operasi yang akan dikerjakan oleh komputer. Model penyelesaian yang dibuat dengan ASP terbukti lebih singkat dari pada model penyelesaian dengan imperative programming. Untuk menyelesaiakan Npuzzle, ASP hanya terdiri atas 33 baris aturan dengan disjungsi untuk arah gerak nilai 0, 4 baris aturan yang mengatur pertukaran antara nilai 0 dan adjacent yang dituju, 1 baris yang mengatur nilai yang tidak bergerak (frame axiom), 2 baris aturan solve dan 1 baris constraint. Untuk menyelesaikan masalah yang sama, IDS perlu sekitar 1900 baris kode program C++. Perhitungan baris kode program pada C++ tersebut sudah termasuk komentar dan spasi. ASP tidak perlu menentukan batas kedalaman pencarian. Hal ini cukup menguntungkan karena kita tidak tahu berapa langkah N-puzzle yang dibangkitkan akan selesai, sedangkan IDS tidak dapat menyelesaikan N-puzzle yang jumlah langkah
11
pengacakannya lebih kedalaman pencarian.
besar
dari
tingkat
Computer Sciences – University of Texas at Austin.
Pada ASP, kontrol terhadap alur program dilakukan oleh mesin solver dari DLV. Hal ini membuat ASP dapat membangkitkan beberapa path berbeda menuju solusi, namun menyebabkan waktu eksekusinya menjadi lebih lambat jika dibandingkan dengan IDS, sedangkan IDS menerapkan prioritas dalam menentukan alur program dan langkahnya. Hal tersebut membuat IDS hanya memiliki satu pola penyelesaian, namun dengan waktu eksekusi yang lebih cepat dari pada ASP.
Mushthofa M. 2010. Evaluation of Answer Set Programs with bounded Predicate Arities. [thesis]. Vienna : Faculty of Informatics Department of Knowledge Based Systems – Vienna University of Technology.
Model penyelesaian N-puzzle telah sukses diaplikasikan ke program berbasis web dengan menggunakan antarmuka sehingga pengguna bisa memainkan N-puzzle. Selain itu, pengguna dapat meminta penyelesaian untuk masalah yang dibangkitkan baik dengan ASP atau IDS. Jika pengguna ingin pencarian solusi puzzle dengan waktu eksekusi yang lebih cepat, pengguna dapat memilih penyelesaian dengan IDS, walau ada kemungkinan tidak menemukan solusi. Namun, jika pengguna ingin kepastian mendapatkan solusi dari suatu puzzle walaupun dengan waktu penyelesaian pencarian lebih lambat, ASP solver layak dikedepankan. Saran Penelitian selanjutnya diharapkan bisa menerapkan answer set programming untuk membangkitkan soal N-puzzle, karena saat ini pembangkitannya menggunakan imperative programming. Penyelesaian diharapkan dapat mendeteksi konfigurasi state dari N-puzzle yang sudah pernah terjadi pada langkah sebelumnya.
DAFTAR PUSTAKA Cormen TH, Leiserson CE, Rivest RL, Stein C. 2001. Introduction to Algorithm. London : McGraw-Hill. Gelfond M, Lifschitz V. 1991. Classsical Negation in Logic Programs and Disjunctive Databases. Austin : University of Texas. Kendall G, Parkes A, Spoerer K. 2008. A Survey of NP-CompletePuzzles. Nottingham : School of Computer Science – University of Nottingham. Lifschitz V. 2008. What is Answer Set Programming. Austin : Department of
Ratner D, Warmuth M. 1990. The (n2-1)puzzle and Relocated Problems. Santa Cruz : Computer and Information Sciences – University of California. Reinefed A, Marsland T.A. 1993. Enhanced Iterative- Deepening Search*. Paderborn : Computing Science DepartementUniversity of Alberta. .
12
LAMPIRAN
13
Lampiran 1 Pseudo code program C++ untuk pembangkitan soal N-puzzle. 1 2 3 4 5 6 7 8 9
Set i to 1 FOR each i on index array puzzle IF i is end of index array puzzle Set nilai[i] to 0 ELSE Set nilai[i] to i END IF Increment i END FOR
10 Set i to 1 11 FOR each i on index array puzzle 12 IF nilai[i] is 0 13 i is position of 0 14 END IF 15 Increment i 16 END FOR 17 Set i to 1 18 FOR each i on number of randomization step 19 Search position of 0 20 IF nodes available not previous position of 0 21 Random target node from nodes available 22 Switch 0 with target node 23 END IF 24 Increment i 25 END FOR
Baris 1 sampai baris 9 pada lampiran ini digunakan untuk menentukan nilai dari 1 sampai N pada puzzle, baris 10 sampai baris 16 digunakan untuk mencari posisi kotak bernilai 0 (blank), dan baris 17 sampai baris 25 digunakan untuk melakukan langkah pengacakan.
14
Lampiran 2 Program DLV, Pembangkitan kemungkinan gerak pada langkah pertama (T=0). 1 2 3 4
move(1,2,1) v move(1,1,2) :- at(0,0,1,1). move(1,X,2) v move(1,X0,1) :- at(0,0,X,1),n(X),X=X0+1,pos(X0). move(1,2,Y) v move(1,1,Y0) :- at(0,0,1,Y),n(Y),Y=Y0+1,pos(Y0). move(1,X,Y0) v move(1,X0,Y) :- at(0,0,X,Y), n(X), n(Y), X=X0+1, Y=Y0+1, pos(X0), pos(Y0).
5
move(1,X1,1) v move(1,X,2) v move(1,X0,1) :at(0,0,X,1),X>1,n(S),S>2,X<S,X1=X+1,X=X0+1,pos(X0).
6
move(1,X1,Y) v move(1,X,Y0) v move(1,X0,Y) :at(0,0,X,Y),X>1,n(S),S>2,X<S,n(Y),X1=X+1,Y=Y0+1,X=X0+1,pos(Y0),pos(X0).
7
move(1,2,Y) v move(1,1,Y1) v move(1,1,Y0) :at(0,0,1,Y),X=1,Y>1,n(S),S>2,Y<S,Y1=Y+1,Y=Y0+1,pos(Y0).
8
move(1,X,Y1) v move(1,X0,Y) v move(1,X,Y0) :at(0,0,X,Y),n(X),Y>1,n(S),S>2,Y<S,Y1=Y+1,X=X0+1,Y=Y0+1,pos(X0),pos(Y0).
9
move(1,X1,Y) v move(1,X,Y1) v move(1,X0,Y) v move(1,X,Y0) :at(0,0,X,Y),X>1,n(S),S>2,X<S,Y>1,n(S),Y<S,X1=X+1,Y1=Y+1,X=X0+1,Y=Y0+1,pos(X0),p os(Y0).
Sebagai keterangan X=X0+1 menunjukkan bahwa posisi X ada di sebelah kanan X0, X1=X+1 menunjukkan bahwa posisi X ada di sebelah kiri X1, Y=Y0+1 menunjukkan bahwa posisi Y ada di atas Y0, dan Y1=Y+1 menunjukkan bahwa posisi Y ada di bawah Y1 . Baris 1 adalah aturan pembangkitan kemungkinan gerak jika posisi 0 di pojok kiri atas. Baris 2 adalah aturan pembangkitan kemungkinan gerak jika posisi 0 di pojok kanan atas. Baris 3 adalah aturan pembangkitan kemungkinan gerak jika posisi 0 di pojok kiri bawah. Baris 4 adalah aturan pembangkitan kemungkinan gerak jika posisi 0 di pojok kanan bawah. Baris 5 adalah aturan pembangkitan kemungkinan gerak jika posisi 0 di sisi atas. Baris 6 adalah aturan pembangkitan kemungkinan gerak jika posisi 0 di sisi bawah. Baris 7 adalah aturan pembangkitan kemungkinan gerak jika posisi 0 di samping kiri. Baris 8 adalah aturan pembangkitan kemungkinan gerak jika posisi 0 di samping kanan. Baris 9 adalah aturan pembangkitan kemungkinan gerak jika posisi 0 berada di tengah.
15
Lampiran 3 Program DLV, Pembangkitan kemungkinan gerak pada langkah berikutnya (T>0). 1 2
move(T1,2,1) :- at(T,0,1,1),at(T0,0,1,2),T>0,T=T0+1,T1=T+1,not solved(T). move(T1,1,2) :- at(T,0,1,1),at(T0,0,2,1),T>0,T=T0+1,T1=T+1,not solved(T).
3
move(T1,X0,1) :at(T,0,X,1),at(T0,0,X,2),T>0,T=T0+1,T1=T+1,n(X),X=X0+1,pos(X0),not solved(T). move(T1,X,2) :at(T,0,X,1),at(T0,0,X0,1),T>0,T=T0+1,T1=T+1,n(X),X=X0+1,pos(X0),not solved(T).
4
5 6
7
8
move(T1,1,Y0) :at(T,0,1,Y),at(T0,0,2,Y),T>0,T=T0+1,T1=T+1,n(Y),Y=Y0+1,pos(Y0),not solved(T). move(T1,2,Y) :at(T,0,1,Y),at(T0,0,1,Y0),T>0,T=T0+1,T1=T+1,n(Y),Y=Y0+1,pos(Y0),not solved(T). move(T1,X0,Y) :at(T,0,X,Y),at(T0,0,X,Y0),T>0,T=T0+1,T1=T+1,n(X),n(Y),X=X0+1,Y=Y0+1,pos(X0),pos (Y0),not solved(T). move(T1,X,Y0) :at(T,0,X,Y),at(T0,0,X0,Y),T>0,T=T0+1,T1=T+1,n(X),n(Y),X=X0+1,Y=Y0+1,pos(X0),pos (Y0),not solved(T).
9
move(T1,X,2) v move(T1,X0,1) :at(T,0,X,1),at(T0,0,X1,1),T>0,T1=T+1,T=T0+1,X>1,n(S),S>2,X<S,X1=X+1,X=X0+1,pos( X0),not solved(T). 10 move(T1,X1,1) v move(T1,X0,1) :at(T,0,X,1),at(T0,0,X,2),T>0,T1=T+1,T=T0+1,X>1,n(S),S>2,X<S,X1=X+1,X=X0+1,pos(X 0),not solved(T). 11 move(T1,X1,1) v move(T1,X,2) :at(T,0,X,1),at(T0,0,X0,1),T>0,T1=T+1,T=T0+1,X>1,n(S),S>2,X<S,X1=X+1,X=X0+1,pos( X0),not solved(T). 12 move(T1,X,Y0) v move(T1,X0,Y) :at(T,0,X,Y),at(T0,0,X1,Y),T>0,T1=T+1,T=T0+1,X>1,n(S),S>2,X<S,n(Y),X1=X+1,Y=Y0+1 ,X=X0+1,pos(X0),pos(Y0),not solved(T). 13 move(T1,X1,Y) v move(T1,X0,Y) :at(T,0,X,Y),at(T0,0,X,Y0),T>0,T1=T+1,T=T0+1,X>1,n(S),S>2,X<S,n(Y),X1=X+1,Y=Y0+1 ,X=X0+1,pos(X0),pos(Y0),not solved(T). 14 move(T1,X1,Y) v move(T1,X,Y0) :at(T,0,X,Y),at(T0,0,X0,Y),T>0,T1=T+1,T=T0+1,X>1,n(S),S>2,X<S,n(Y),X1=X+1,Y=Y0+1 ,X=X0+1,pos(X0),pos(Y0),not solved(T). 15 move(T1,1,Y1) v move(T1,1,Y0) :at(T,0,1,Y),at(T0,0,2,Y),T>0,T1=T+1,T=T0+1,Y>1,n(S),S>2,Y<S,Y1=Y+1,Y=Y0+1,pos(Y 0),not solved(T). 16 move(T1,2,Y) v move(T1,1,Y0) :at(T,0,1,Y),at(T0,0,1,Y1),T>0,T1=T+1,T=T0+1,Y>1,n(S),S>2,Y<S,Y1=Y+1,Y=Y0+1,pos( Y0),not solved(T). 17 move(T1,2,Y) v move(T1,1,Y1) :at(T,0,1,Y),at(T0,0,1,Y0),T>0,T1=T+1,T=T0+1,Y>1,n(S),S>2,Y<S,Y1=Y+1,Y=Y0+1,pos( Y0),not solved(T). 18 move(T1,X0,Y) v move(T1,X,Y0) :at(T,0,X,Y),at(T0,0,X,Y1),T>0,T1=T+1,T=T0+1,n(X),Y>1,n(S),S>2,Y<S,Y1=Y+1,X=X0+1 ,Y=Y0+1,pos(X0),pos(Y0),not solved(T). 19 move(T1,X,Y1) v move(T1,X,Y0) :at(T,0,X,Y),at(T0,0,X0,Y),T>0,T1=T+1,T=T0+1,n(X),Y>1,n(S),S>2,Y<S,Y1=Y+1,X=X0+1 ,Y=Y0+1,pos(X0),pos(Y0),not solved(T). 20 move(T1,X,Y1) v move(T1,X0,Y) :at(T,0,X,Y),at(T0,0,X,Y0),T>0,T1=T+1,T=T0+1,n(X),Y>1,n(S),S>2,Y<S,Y1=Y+1,X=X0+1 ,Y=Y0+1,pos(X0),pos(Y0),not solved(T). 21 move(T1,X,Y1) v move(T1,X0,Y) v move(T1,X,Y0) :at(T,0,X,Y),at(T0,0,X1,Y),T>0,T1=T+1,T=T0+1,X>1,n(S),S>2,X<S,Y>1,n(S),Y<S,X1=X+ 1,Y1=Y+1,X=X0+1,Y=Y0+1,pos(X0),pos(Y0),not solved(T). 22 move(T1,X1,Y) v move(T1,X0,Y) v move(T1,X,Y0) :at(T,0,X,Y),at(T0,0,X,Y1),T>0,T1=T+1,T=T0+1,X>1,n(S),S>2,X<S,Y>1,n(S),Y<S,X1=X+ 1,Y1=Y+1,X=X0+1,Y=Y0+1,pos(X0),pos(Y0),not solved(T). 23 move(T1,X1,Y) v move(T1,X,Y1) v move(T1,X,Y0) :at(T,0,X,Y),at(T0,0,X0,Y),T>0,T1=T+1,T=T0+1,X>1,n(S),S>2,X<S,Y>1,n(S),Y<S,X1=X+ 1,Y1=Y+1,X=X0+1,Y=Y0+1,pos(X0),pos(Y0),not solved(T).
16
24 move(T1,X1,Y) v move(T1,X,Y1) v move(T1,X0,Y) :at(T,0,X,Y),at(T0,0,X,Y0),T>0,T1=T+1,T=T0+1,X>1,n(S),S>2,X<S,Y>1,n(S),Y<S,X1=X+ 1,Y1=Y+1,X=X0+1,Y=Y0+1,pos(X0),pos(Y0),not solved(T).
Pada semua aturan diatas tidak mengizinkan kembali ke posisi tepat satu langkah sebelumnya. Baris 1 sampai baris 2 adalah aturan pembangkitan kemungkinan gerak langkah ke jika posisi 0 di pojok kiri atas. Pada baris 1 nilai 0 akan bergerak ke kanan. Pada baris 2 nilai 0 akan bergerak ke bawah. Baris 3 sampai baris 4 adalah aturan pembangkitan kemungkinan gerak langkah ke jika posisi 0 di pojok kanan atas. Pada baris 3 nilai 0 akan bergerak ke kiri. Pada baris 4 nilai 0 akan bergerak ke bawah. Baris 5 sampai baris 6 adalah aturan pembangkitan kemungkinan gerak langkah ke jika posisi 0 di pojok kiri bawah. Pada baris 5 nilai 0 akan bergerak ke atas. Pada baris 6 nilai 0 akan bergerak ke kanan. Baris 7 sampai baris 8 adalah aturan pembangkitan kemungkinan gerak langkah ke jika posisi 0 di pojok kanan bawah. Pada baris 7 nilai 0 akan bergerak ke kiri. Pada baris 8 nilai 0 akan bergerak ke atas. Baris 9 sampai baris 11 adalah aturan pembangkitan kemungkinan gerak langkah ke jika posisi 0 di atas. Pada baris 9 nilai 0 akan bergerak ke kiri atau ke bawah. Pada baris 10 nilai 0 akan bergerak ke kiri atau ke kanan. Pada baris 11 nilai 0 akan bergerak ke kanan atau ke bawah. Baris 12 sampai baris 14 adalah aturan pembangkitan kemungkinan gerak langkah ke jika posisi 0 di bawah. Pada baris 12 nilai 0 akan bergerak ke kiri atau ke atas. Pada baris 13 nilai 0 akan bergerak ke kiri atau ke kanan. Pada baris 14 nilai 0 akan bergerak ke kanan atau ke atas. Baris 15 sampai baris 17 adalah aturan pembangkitan kemungkinan gerak langkah ke jika posisi 0 di kiri. Pada baris 15 nilai 0 akan bergerak ke atas atau ke bawah. Pada baris 16 nilai 0 akan bergerak ke atas atau ke kanan. Pada baris 17 nilai 0 akan bergerak ke kanan atau ke bawah. Baris 18 sampai baris 20 adalah aturan pembangkitan kemungkinan gerak langkah ke jika posisi 0 di kanan. Pada baris 18 nilai 0 akan bergerak ke atas atau ke kiri. Pada baris 19 nilai 0 akan bergerak ke atas atau ke bawah. Pada baris 20 nilai 0 akan bergerak ke kiri atau ke bawah. Baris 21 sampai baris 24 adalah aturan pembangkitan kemungkinan gerak langkah ke jika posisi 0 di tengah. Pada baris 21 nilai 0 akan bergerak ke bawah, ke atas, atau ke kiri. Pada baris 22 nilai 0 akan bergerak ke atas, ke kiri, atau ke kanan. Pada baris 23 nilai 0 akan bergerak ke kanan, ke atas, atau ke bawah. Pada baris 24 nilai 0 akan bergerak ke kanan, ke kiri, atau ke bawah.
17
Lampiran 4 Program DLV, akibat jika terjadi gerakan (move). 1 2 3 4
at(T1,0,X1,Y) :- at(T,0,X,Y),move(T1,X1,Y),T1=T+1,pos(Y). at(T1,0,X,Y1) :- at(T,0,X,Y),move(T1,X,Y1),T1=T+1,pos(X). at(T1,N,X,Y) :- at(T,N,X1,Y),move(T1,X1,Y),at(T,0,X,Y),T1=T+1,angka(N),pos(Y). at(T1,N,X,Y) :- at(T,N,X,Y1),move(T1,X,Y1),at(T,0,X,Y),T1=T+1,angka(N),pos(X).
Pada baris 1 menunjukkan jika pada waktu T nilai 0 ada di X,Y dan bergerak ke X1,Y, maka pada waktu T1 ,dimana T1=T+1 nilai 0 ada di X1,Y . Pada baris 2 menunjukkan jika pada waktu T nilai 0 ada di X,Y dan bergerak ke X,Y1, maka pada waktu T1 ,dimana T1=T+1 nilai 0 ada di X,Y1 . Pada baris 3 menunjukkan jika pada waktu T nilai N ada di X1,Y dan nilai 0 ada di X,Y, lalu nilai 0 bergerak ke X1,Y, maka pada waktu T1 ,dimana T1=T+1 nilai N ada di X,Y . Pada baris 4 menunjukkan jika pada waktu T nilai N ada di X,Y1 dan nilai 0 ada di X,Y, lalu nilai 0 bergerak ke X,Y1, maka pada waktu T1 ,dimana T1=T+1 nilai N ada di X,Y .
18
Lampiran 5 Program DLV, kondisi state pada nilai yang tidak bergerak (frame axiom). 1
at(T1,N,X,Y) :- at(T,N,X,Y),not move(T1,X,Y),N>0,T1=T+1,pos(X),pos(Y),angka(N),not solved(T).
Aturan diatas menunjukan jika pada waktu T nilai N ada di X,Y dan nilai 0 tidak bergerak ke maka pada T1 ,dimana T1=T+1 nilai N tetap berada di X,Y .
X,Y,
19
Lampiran 6 Pseudo code program C++, membaca soal N-puzzle yang dibangkitkan. 1 2
Set ukuran to string on ukuran.dat Set size to integer (ukuran}
3 Set i to 1 4 FOR each string on imperatif.dat 5 Set puzzle to string 6 Set puzzle[i] to integer (puzzle) 7 IF i is number of puzzle 8 break 9 END IF 10 Increment i 11 END FOR
Baris 1 dan 2 pada lampiran ini untuk membaca ukuran puzzle dari ukuran.dat. Baris 3 sampai 11 untuk membaca soal N-puzzle dari imperatif.dat. Dengan catatan number of puzzle didapatkan dari size * size.
20
Lampiran 7 Pseudo code program C++, memeriksa apakah N-puzzle sudah selesai (solve). 1 Set i to 1 2 FOR each index of array puzzle 3 IF puzzle[i] is 0 4 Set value to number of puzzle - i 5 ELSE 6 Set value to puzzle[i] – i 7 Set value to absolute (value) 8 END IF 9 Sum all of value 10 Increment i 11 END FOR
N-puzzle selesai dan menemukan solusi (solve) jika nilai sudah tersusun dan teruurut berdasarkan posisinya. Berdasarkan hal tersebut kondisi solusi bisa didapatkan dengan cara nilai pada kotak dikurangi posisi(indeks)-nya pada array. Pengecualian terjadi pada nilai 0, nilai 0 diganti dengan banyaknya nilai pada puzzle dikurangi posisi(indeks)-nya padaarray. Contoh pada 8-puzzle untuk mengetahui apakah nilai 0 sudah pada posisinya maka 9- [indeks_array].
21
Lampiran 8 Pseudo code program C++, iterasi yang memanggil fungsi menggerakan puzzle. 1 2 3 4 5 6 7 8 9 10 11
Choose max deep (5,10,or 15) Set deep to 2 FOR each deep till max deep IF puzzle not solved THEN Move puzzle ELSE break END IF Increment deep END FOR
Pada C++ max deep sudah ditentukan yaitu 5,10,atau 15.Jadi tinggal memilih dengan maksimal kedalaman yang tersedia untuk menyelesaikan puzzle. Move puzzle pada baris 5 berarti memanggil fungsi idfs().
22
Lampiran 9 Hasil Pengujian untuk N-puzzle 3x3 (8-puzzle).
23
Lampiran 10 Hasil Pengujian untuk N-puzzle 4x4 (15-puzzle).
24
Lampiran 11 Hasil Pengujian untuk N-puzzle 5x5 (24-puzzle).
25
Lampiran 12 Hasil Pengujian untuk N-puzzle 6x6 (35-puzzle).
