8-Puzzle Dengan Menggunakan Algoritma Iterative Deepening Search (IDS) Naskah Publikasi
Disusun Oleh: Muhammad Nasrul Anwar NIM : 04.11.0578 JURUSAN TEKNIK INFORMATIKA PROGRAM STUDI STRATA-1
JURUSAN TEKNIK INFORMATIKA SEKOLAH TINGGI MANAGEMEN INFORMATIKA DAN KOMPUTER AMIKOM JOGJAKARTA 2010
8-PUZZLE WITH ITERATIVE DEEPENING SEARCH (IDS) ALGORITHM 8-PUZZLE DENGAN MENGGUNAKAN ALGORITMA ITERATIVE DEEPENING SEARCH (IDS)
Muhammad Nasrul Anwar Jurusan Teknik Informatika STMIK AMIKOM YOGYAKARTA
ABSTRACT Computer games are software applications that used by users. Many kinds of variety and interesting appearance, including computer game software of interest by peoples. 8-puzzle is a game that uses search techniques (searching). Search techniques can be done using an algorithm to find a solution or a problem. Lots of search techniques can be done and these techniques should be selected based on criteria of the problems faced and the level of needs that must be met. As one of the widely used search techniques are iterative deepening search (IDS). IDS is a technique that combines the benefits searches by using the technique of Breadth First Search (BFS) in the case of complete and optimal search techniques and the advantages of Depth First Search (DFS) in terms of space complexity. On implementation, the search techniques will IDS settlement cases taken on 8-Puzzle problem. In this paper, the author tries to analyze the points of discussion and the results are intended to provide advice to the reader to prefer the use of IDS algorithm because it is more effective and efficient to do the search for solutions to a problem. Key Words : Algorithm, Heuristic Algorithm, IDS
BAB I PENDAHULUAN
1.1.
LATAR BELAKANG MASALAH Permainan komputer merupakan aplikasi perangkat lunak yang sering digunakan oleh para pengguna komputer. Dengan jenis yang bermacam-macam dan tampilan yang menarik, permainan komputer termasuk perangkat lunak yang diminati oleh berbagai kalangan. Selain karena tampilan dan aplikasinya relatif menarik, permainan komputer dapat menjadi salah satu perangkat lunak yang cukup menyenangkan terutama bagi orang yang telah terbiasa menggunakan komputer. Salah satu permainan yang sering dimainkan para pengguna komputer adalah permainan 8-puzzle. Permainan 8-puzzle ini mempunyai peraturan yang cukup sederhana. Pada permainan ini, pemain harus mengurutkan angka-angka dari angka yang diacak dan batasan ruang yang ada. Permainan akan berakhir ketika pemain telah mengurutkan angka tersebut. 8-puzzle merupakan sebuah permainan yang menggunakan teknik pencarian
(searching).
Teknik
pencarian
bisa
dilakukan
dengan
menggunakan suatu algoritma untuk mendapatkan suatu solusi atau permasalahan. Banyak sekali teknik pencarian yang bisa dilakukan dan teknik-teknik tersebut harus dipilih berdasarkan kriteria permasalahan yang dihadapi dan tingkat kebutuhan yang harus dipenuhi. Adapun salah satu teknik pencarian yang banyak digunakan adalah Iterative Deepening Search (IDS). IDS merupakan suatu teknik yang menggabungkan keuntungan pencarian dengan menggunakan teknik Breadth First Search (BFS) dalam hal
complete dan optimal serta keuntungan dari teknik pencarian Depth First Search (DFS) dalam hal space complexity. Pada implementasi, teknik pencarian IDS akan diambil kasus penyelesaian permasalahan pada 8-Puzzle.
Gambar 1.1 8-Puzzle Secara Umum
Gambar 1.1 di atas merupakan gambaran umum dari 8 puzzle dan khusus pada kasus kali ini, urutan angka yang terdapat pada gambar merupakan solusi yang harus dicapai. Adapun status dari 8-puzzle ini adalah ubin (tile) yang bisa dipindah posisinya. 8-puzzle memiliki maksimal 4 aksi yaitu ubin digeser ke atas, digeser ke kiri, digeser ke kanan, dan digeser ke bawah dilihat dari letak ubin yang kosong (tidak ada angka). Jadi pada kasus ini ubin yang kosong harus digeser untuk menghasilkan solusi yang diinginkan. Dengan menggunakan teknik pencarian IDS maka harus dihasilkan suatu langkah-langkah untuk menghasilkan solusi. Sebenarnya solusi bisa bermacam-macam namun untuk kasus ini dibatasi sampai solusi terurut seperti gambar di atas. Penulis perlu mengambil judul “8-Puzzle Dengan Menggunakan Algoritma Iterative Deepening Search (IDS)” karena permainan 8-puzzle ini berfungsi sebagai pembelajaran atau referensi kepada mahasiswa tentang
logika algoritma khususnya algoritma Iterative Deepening Search (IDS) yang selama ini masih jarang dibahas dalam penyusunan tugas akhir atau skripsi.
1.2.
PERUMUSAN MASALAH Bagaimana cara untuk mendapatkan hasil akhir permainan puzzle dan untuk menghasilkan solusi paling efektif menggunakan algoritma IDS.
1.3.
BATASAN MASALAH Pada penulisan tugas akhir atau skripsi ini, akan diberikan batasan masalah sebagai berikut : 1. Teknik pencarian yang digunakan hanya menggunakan IDS. 2. Solution Report dari pencarian yang meliputi: jumlah step yang digunakan dalam pencarian, nilai heuristic, generate node, waktu yang diperlukan untuk melakukan pencarian dan langkah-langkah dalam mencapai goal state(solusi). 3. Pencarian solusi didapat dengan dua cara yaitu dengan menentukan batasan limit atau tidak menggunakan batasan limit. 4. Ada kemungkinan tidak ditemukannya solusi karena adanya batasan limit.
1.4.
MAKSUD DAN TUJUAN Adapun maksud dan tujuan penulisan tugas akhir atau skripsi tersebut adalah: a) Untuk mengetahui nilai heuristic dari pencarian. b) Untuk mengetahui waktu yang dibutuhkan dalam menyelesaikan permainan.
c) Untuk mengetahui jumlah node yang digunakan pada pencarian solusi 8-puzzle
1.5.
METODOLOGI PENELITIAN Metodologi penelitian yang digunakan dalam penulisan skripsi ini adalah :
1. Study Literature Study literature digunakan untuk mempelajari tentang algoritma pencarian, seperti Iterative Deepening Search, Best
First
Search
dan
Dept
First
Search.
Untuk
keperluan
implementasi, penulis melakukan study literature terhadap peemrograman Delphi sebagai bahasa pemrograman yang akan digunakan dalam tahap implementasi. 2. Implementasi Implementasi
yang
dilakukan
meliputi
implementasi
algoritma Iterative Deepening Search. Selain itu perancangan pengujian terhadap hasil implementasi juga dilakukan untuk mengetahui efektifitas dari suatu algoritma. 3. Analisis Melakukan analisa dari hasil implementasi. Yaitu tentang jumlah heuristic, jumlah node, waktu dan efektifitas pencarian.
1.6.
SISTEMATIKA PENULISAN LAPORAN Agar dapat tercapai penulisan yang sistematis mengenai pokok permasalahan sebagai hasil penelitian, maka akan lebih baik dan lebih jelas serta terarah apabila terlebih dahulu diberi gambaran sistematika secara
ringkas mengenai susunan skripsi ini maupun tentang apa yang dikandung dalam skripsi ini, sehingga akan mempermudah dalam pemahaman dan pembahasannya. Sistematika skripsi ini adalah sebagai berikut: BAB I PENDAHULUAN Pada bab ini akan menjelaskan tentang latar belakang, perumusan masalah, batasan masalah, maksud dan tujuan penelitian,
serta
metode
pengumpulan
data
untuk
pengembangan sistem serta sistematika penulisan skripsi. BAB II DASAR TEORI Bab ini akan menjelaskan dasar teori dari sistem dan software yang digunakan dalam pembuatan aplikasi. BAB III
ANALISIS DAN PERANCANGAN SISTEM Pada bab ini menjelaskan tentang analisis yang digunakan dalam pembuatan skripsi serta perancangan dari aplikasi yang akan dibuat.
BAB IV IMPLEMENTASI SISTEM DAN PEMBAHASAN Dalam bab ini menjelaskan cara kerja aplikasi yang telah dibuat. BAB V PENUTUP Dalam BAB V ini berisi tentang kesimpulan secara teori maupun praktek, dan saran dari hasil analisis dan perancangan aplikasi yang dianggap perlu diperhatikan sehubungan dengan pembuatan aplikasi tersebut. DAFTAR PUSTAKA
BAB II DASAR TEORI
2.1. ALGORITMA 2.1.1. Definisi Algoritma Algoritma adalah urutan langkah-langkah logis penyelesaian masalah yang disusun secara sistematis dan logis1. Kata logis merupakan kata kunci dalam algoritma. Langkah-langkah dalam algoritma harus logis dan harus dapat ditentukan bernilai salah atau benar. Dalam beberapa konteks, algoritma adalah spesifikasi urutan langkah untuk melakukan pekerjaan tertentu2. Pertimbangan dalam pemilihan algoritma adalah, pertama algoritma haruslah benar. Artinya algoritma akan memberikan keluaran yang dikehendaki dari sejumlah masukan yang diberikan. Tidak peduli sebagus apapun algoritma, kalau memberikan keluaran yang salah, pastilah algoritma tersebut bukan algoritma yang baik. Pertimbangan kedua yang harus diperhatikan adalah kita harus mengetahui seberapa baik hasil yang dicapai oleh algoritma tersebut. Hal ini penting terutama pada algoritma untuk menyelesaikan masalah yang memerlukan aproksimasi hasil (hasil yang hanya berupa pendekatan). Algoritma yang baik harus mampu memberikan hasil yang sedekat mungkin dengan nilai yang sebenarnya. Ketiga adalah efisiensi algoritma. Efisiensi algoritma dapat ditinjau
1
Robert R. Korfhage. 1966. Logic and Algorithms. John Wiley & Sons.Inc. New York 2 Robert Sedgewick. 1983. Algorithms. Addison-Wesley Publishing Company.Inc. USA.
dari 2 hal yaitu efisiensi waktu dan memori. Meskipun algoritma memberikan keluaran yang benar (paling mendekati), tetapi jika kita harus menunggu berjam-jam untuk mendapatkan keluarannya, algoritma tersebut biasanya tidak akan dipakai, setiap orang menginginkan keluaran yang cepat. Begitu juga dengan memori, semakin besar memori yang terpakai maka semakin buruklah algoritma tersebut. Dalam kenyataannya, setiap orang bisa membuat algoritma yang berbeda untuk menyelesaikan suatu permasalahan, walaupun terjadi perbedaan dalam menyusun algoritma, tentunya kita mengharapkan keluaran yang sama. Jika terjadi demikian, carilah algoritma yang paling efisien dan cepat. 2.1.2. Algoritma Dan Program Program adalah kumpulan pernyataan komputer, sedangkan metode dan tahapan sistematis dalam program adalah algoritma. Program ditulis dengan menggunakan bahasa pemrograman. Jadi bisa disebut bahwa program adalah suatu implementasi dari bahasa pemrograman3. Beberapa pakar memberi formula bahwa:
Program = Algoritma + Bahasa (Struktur Data)
Bagaimanapun juga struktur data dan algoritma berhubungan sangat erat pada sebuah program. Algoritma yang baik tanpa pemilihan struktur data yang tepat akan membuat program menjadi kurang baik, demikian juga sebaliknya. Pembuatan algoritma mempunyai banyak keuntungan di antaranya: 3
Robert Sedgewick. 1983. Algorithms. Addison-Wesley Publishing Company.Inc. USA.
1.
Pembuatan atau penulisan algoritma tidak tergantung pada bahasa pemrograman manapun, artinya penulisan algoritma independen dari bahasa pemrograman dan komputer yang melaksanakannya.
2.
Notasi algoritma dapat diterjemahkan ke dalam berbagai bahasa pemrograman.
3.
Apapun bahasa pemrogramannya, output yang akan dikeluarkan sama karena algoritmanya sama.
Beberapa hal yang perlu diperhatikan dalam membuat algoritma: 1.
Teks algoritma berisi deskripsi langkah-langkah penyelesaian masalah. Deskripsi tersebut dapat ditulis dalam notasi apapun asalkan mudah dimengerti dan dipahami.
2.
Tidak ada notasi yang baku dalam penulisan teks algoritma seperti notasi bahasa pemrograman. Notasi yang digunakan dalam menulis algoritma disebut notasi algoritmik.
3.
Setiap orang dapat membuat aturan penulisan dan notasi algoritmik sendiri. Hal ini dikarenakan teks algoritma tidak sama dengan teks program. Namun, supaya notasi algoritmik mudah ditranslasikan ke dalam notasi bahasa pemrograman tertentu, maka sebaiknya notasi algoritmik tersebut berkorespondensi dengan notasi bahasa pemrograman secara umum.
4.
Notasi algoritmik bukan notasi bahasa pemrograman, karena itu
pseudocode dalam notasi algoritmik tidak dapat dijalankan oleh komputer. Agar dapat dijalankan oleh komputer, pseudocode dalam notasi algoritmik harus ditranslasikan atau diterjemahkan ke dalam notasi bahasa pemrograman yang dipilih. Perlu diingat
bahwa orang yang menulis program sangat terikat dalam aturan tata bahasanya dan spesifikasi mesin yang menjalannya. 5.
Algoritma sebenarnya digunakan untuk membantu kita dalam mengkonversikan
suatu
permasalahan
ke
dalam
bahasa
pemrograman. 6.
Algoritma merupakan hasil pemikiran konseptual, supaya dapat dilaksanakan oleh komputer, algoritma harus ditranslasikan ke dalam notasi bahasa pemrograman. Ada beberapa hal yang harus diperhatikan pada translasi tersebut, yaitu: a.
Pendeklarasian Variabel Untuk variabel
mengetahui
dibutuhkannya
pendeklarasian
dalam penggunaan bahasa pemrograman
apabila
tidak
semua
bahasa
pemrograman
membutuhkannya. b.
Pemilihan Tipe Data Apabila bahasa pemrograman yang akan digunakan membutuhkan pendeklarasian variabel maka perlu hal ini dipertimbangkan pada saat pemilihan tipe data.
c.
Pemakaian Instruksi-Instruksi Beberapa instruksi mempunyai kegunaan yang sama tetapi
masingmasing
memiliki
kelebihan
dan
kekurangan yang berbeda. d.
Aturan Sintaksis Pada saat menuliskan program kita terikat dengan aturan sintaksis dalam bahasa pemrograman yang akan digunakan.
e.
Tampilan Hasil Pada saat membuat algoritma kita tidak memikirkan tampilan hasil yang akan disajikan. Hal-hal teknis ini diperhatikan
ketika
mengkonversikannya
menjadi
program. f.
Cara Pengoperasian Compiler Atau Interpreter Bahasa pemrograman yang digunakan termasuk dalam kelompok compiler atau interpreter.
2.1.3. Jenis-Jenis Algoritma Terdapat beragam klasifikasi algoritma dan setiap klasifikasi mempunyai alasan tersendiri. Salah satu cara untuk melakukan klasifikasi jenis-jenis algoritma adalah dengan memperhatikan paradigma dan metode yang digunakan untuk mendesain algoritma tersebut. Beberapa paradigma yang digunakan dalam menyusun suatu algoritma akan dipaparkan dibagian ini. Masing-masing paradigma dapat digunakan dalam banyak algoritma yang berbeda4.
Divide
and
Conquer,
paradigma
untuk
membagi
suatu
permasalahan besar menjadi permasalahan-permasalahan yang lebih kecil. Pembagian masalah ini dilakukan terus menerus sampai ditemukan bagian masalah kecil yang mudah untuk dipecahkan. Singkatnya menyelesaikan keseluruhan masalah dengan membagi masalah besar dan kemudian memecahkan permasalahan-permasalahan kecil yang terbentuk.
4www.
Dynamic programming, paradigma pemrograman dinamik akan
id.wikipedia.org
sesuai jika digunakan pada suatu masalah yang mengandung sub struktur yang optimal dan mengandung beberapa bagian permasalahan yang tumpang tindih. Paradigma ini sekilas terlihat mirip dengan paradigma Divide and Conquer, sama-sama mencoba
untuk
membagi
permasalahan
menjadi
sub
permasalahan yang lebih kecil, tapi secara intrinsik ada perbedaan dari karakter permasalahan yang dihadapi.
Metode serakah. Sebuah algoritma serakah mirip dengan sebuah pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap dan menggunakan pilihan "serakah" apa yang dilihat terbaik pada saat itu.
Macam-macam algoritma5 : 1. Algoritma Kombinatorial a) Algoritma kombinatorial Umum b) Algoritma Graph c) Algoritma Pencarian
Pencarian Linear: mencari sebuah item pada sebuah
list tak berurut.
Algoritma Seleksi: mencari item ke-k pada sebuah list.
Pencarian Biner: menemukan sebuah item pada sebuah
list terurut.
Pohon Pencarian Biner
Pencarian
Breadth-first:
menelusuri
sebuah
graf
tingkatan demi tingkatan.
5
http://www-groups.dcs.st-and.ac.uk/~history/Miscellaneous/Pearce/Lectures/Ch8_3.html
Pencarian Depth-first: menelusuri sebuah graf cabang demi cabang.
Pencarian Best-first: menelusuri sebuah graf dengan urutan
sesuai
kepentingan
dengan
menggunakan
antrian prioritas.
Pencarian pohon A*: kasus khusus dari pencarian best-
first.
Pencarian Prediktif: pencarian mirip biner dengan faktor pada magnitudo dari syarat pencarian terhadap nilai atas dan bawah dalam pencarian. Kadang-kadang disebut pencarian kamus atau pencarian interpolasi.
Tabel Hash: mencari sebuah item dalam sebuah kumpulan tak berurut dalam waktu O(1).
d) Algoritma String
e) Approximate Matching f)
Algoritma Penyusunan
2.
Compression Algorithms
3.
Computational Geometry
4.
Grafik Komputer
5.
Algoritma Kriptografi
6.
Algoritma Distributed Systems
7.
Algoritma Numerical
8.
Number Theoretic Algorithms
9.
Numerical Algebra
10. Parsing 11. Teknik Perangkat Lunak
12. Algoritma Kuantum 13. Algoritma Medis 14. Lainnya 2.1.4. Algoritma Pencarian 2.1.4.1.
Karakteristik Algoritma Pencarian Karakteristik algoritma pencarian dapat dinilai dari beberapa faktor6, yaitu : 1. Kelengkapan Apakah dapat diberikan garansi bahwa solusi terdapat dalam ruang pencarian. 2. Optimasi Apakah solusi yang didapat hanya memerlukan biaya minimal. 3. Penghitungan Biaya Pencarian
Kompleksitas waktu : waktu yang diperlukan (jumlah simpul yang dibuka) buruk atau sesuai dengan kasus yang terjadi.
Kompleksitas ruang : ruang yang dipakai oleh algoritma diukur dari ukuran fringe yang terbentuk.
2.1.4.2.
Pendekatan Strategi Pencarian Perbedaan
strategi
pencarian,
menyebabkan
beberapa pendekatan7, diantaranya :
6 7
Pencarian buta (tanpa informasi)
Pencarian heuristic (dengan informasi)
Constrain satisfaction (pencarian dengan batasan)
Hapnes Toba, Pencarian Tanpa Informasi, PIB lesson 4 Hapnes Toba, Pencarian Tanpa Informasi, PIB lesson 4
munculnya
Adversary (pencarian saling berlawanan)
2.1.5.
Problem Solving Dengan Algoritma Pencarian Problem yang dimaksud di sini adalah deviasi antara current
state dengan goal. Domain problem dimodelkan ke dalam state space searching (ruang pencarian) berisi kumpulan state berbeda. State adalah sebuah kondisi yang mungkin dalam obyek permasalahan tersebut8.
Problem solving sendiri adalah bagaimana bergerak dari current state ke arah goal. Langkah awal dalam problem solving adalah mencari state yang cocok dengan state awal dan kemudian mecari rangkaian next state dari state awal yang cocok dan yang bisa mengantarkan pada state goal9. Konsep
problem
solving
dengan
tree
searching
merepresentasikan ruang pencarian dalam suatu problem menjadi struktur pohon yang dinamakan pohon pencarian. Problem solving dilakukan dengan mengunjungi simpul-simpul secara traversal dalam pohon tersebut. Pohon pencarian adalah sebuah data struktur yang terdiri atas sebuah simpul induk utama, disebut root, tempat dimulainya pencarian. Setiap simpul dapat memiliki satu atau lebih simpul anak. Data struktur suatu simpul : 1. Deskripsi keadaan 2. Pointer ke parent 3. Kedalaman simpul 8 9
Munir, Rinaldi. (2006). “ Matematika Diskrit” , InformatikaBandung, 2005, hal.IX-1 –X-32
http://www.informatika.org/~rinaldi/Stmik/2006-2007/ Penerapan%20BFS%20dan%20 DFS% 20pada%20Pencarian%20Solusi.pdf
4. Operator yang membuka simpul ini 5. Biaya total dari simpul awal sampai simpul ini Setiap algoritma pencarian akan menyimpan semua simpul dalam pohon dalam suatu daftar List yang disebut sebagai fringe. Fringe ini dipakai sebagai alat untuk menunjukkan simpul yang telah dibuka dan siap untuk dieksplorasi. Strategi pencarian didefinisikan berdasarkan penentuan urutan pemrosesan node. Strategi ini dievaluasi berdasarkan beberapa faktor, yaitu :
1.
Kelengkapan : apakah dapat diberikan garansi bahwa solusi terdapat dalam ruang pencarian.
2.
Optimasi : apakah solusi yang akan didapatkan memerlukan biaya minimal.
3.
Kompleksitas waktu : jumlah nodes yang diproses.
4.
Kompleksitas memori : jumlah maksimum nodes di memori.
Gambar 2.1 Pohon Pencarian Terminologi untuk kompleksitas waktu dan memori adalah : 1. b: Pencabangan maksimal dari pohon pencarian
2. d : Kedalaman dari solusi terendah 3. m : Kedalaman maksimum dari ruang pencarian Strategi pencarian yang akan dibahas pada skripsi ini hanya menggunakan informasi yang tersedia pada definisi masalah atau yang disebut dengan pencarian buta (uninformed).
Berbagai strategi
pencarian uninformed adalah: 1.
Breadth-First Search (BFS)
2.
Uniform-Cost Search
3.
Depth-First Search (DFS)
4.
Depth-Limited Search
5.
Depth First Iriterative Deepening (DFID) Pada skripsi ini, kita hanya membahas algoritma IDS yang
memiliki optimasi sehingga dapat kita gunakan untuk menyelesaikan permainan 8-puzzle. Dimana algoritma IDS merupakan gabungan dari 2 strategi pencarian uninformed yaitu breadth-first search (BFS) dan
Depth-first search (DFS).
2.1.5.1. Breadth-First Search (BFS) Pencarian dilakukan pada semua node dalam setiap level secara berurutan dari kiri ke kanan. Jika pada satu level belum ditemukan solusi, maka pencarian dilanjutkan pada
level
berikutnya.
Demikian
seterusnya
sampai
ditemukan solusi. Dengan strategi ini, maka dapat dijamin bahwa solusi yang ditemukan adalah yang paling baik (Optimal). Tetapi BFS harus menyimpan semua node yang pernah
dibangkitkan.
Hal
ini
harus
dilakukan
untuk
penelusuran balik jika solusi sudah ditemukan10.
Gambar 2.2 Ilustrasi Urutan Kunjungan Simpul Pada Algoritma BFS
0
0
1
0
2
1
3
(i)
0
2
4
(ii)
1
3
2
4
(iii)
5
(iv)
Gambar 2.3 Tahapan Pembentukan Pohon BFS
Cara Kerja Algoritma BFS Dalam algoritma BFS, simpul anak yang telah
dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan
untuk
mengacu
simpul-simpul
yang
bertetangga dengannya yang akan dikunjungi kemudian 10
Russel, Stuart and Petter Norfig.Artificial Intelegent A Modern Approach, 1995,Prentice – Hall,inc
6
sesuai urutan pengantrian11.Untuk memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya, berikut langkah-langkah algoritma BFS: 1) Masukkan simpul ujung (akar) ke dalam antrian. 2)Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi. 3)Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan. 4)Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian. 5)Jika antrian kosong dan setiap simpul sudah dicek,
pencarian
pengembalikan
hasil
selesai
dan
solusi
tidak
ditemukan. 6)Ulangi pencarian dari langkah kedua.
Properti Algoritma BFS Karena seluruh simpul yang telah dikunjungi
harus disimpan, maka kompleksitas ruang algoritma BFS adalah O (jumlah simpul + jumlah sisi). Hal ini menunjukkan bahwa algoritma BFS memerlukan ruang besar dan tidak cocok untuk pemecahan masalah besar. Angka yang sama menunjukkan kompleksitas waktu terburuk, dimana setiap simpul harus diperiksa. 11
Russel, Stuart and Petter Norfig.Artificial Intelegent A Modern Approach, 1995,Prentice – Hall,inc
Kompleksitas waktu terbaik O(1), didapat jika solusi ditemukan pada pencarian pertama. Walaupun memiliki kompleksitas ruang dan waktu yang kurang baik, algoritma BFS dapat mencari solusi secara tuntas, berarti algoritma ini akan menemukan solusi terbaik dan terdekat bagaimanapun bentuk graf tersebut.
Algoritma BFS: 1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi (goal node),
maka
stop. 2. Jika Q kosong, tidak ada solusi. Stop. 3. Ambil simpul v dari kepala (head) antrian, bangkitkan semua anak-anaknya. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di belakang antrian. 4. Jika suatu simpul anak dari v adalah simpul solusi, maka solusi telah ditemukan, kalau tidak kembali lagi ke langkah 2.
Analisis Breadth First Search :
1. Completeness Iya jika cabang maksimum terhingga
2. Time Complexity 1+b1+b2+b3+…..+bd+b(bd-1) = O(bd) dieksponensial
3. Space Complexity O(bd) menyimpan semua node di memori
4. Optimalty Iya jika cost per langkah = 1
Kelebihan, Kelemahan, analisa ruang dan waktu Kelebihan BFS :
Tidak akan menemui jalan buntu
Jika ada satu solusi, maka BFS akan menemukannya, dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.
Kelemahan BFS :
Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.
Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level yang ke(n+1).
Analisis Ruang dan Waktu Diasumsikan :
Ada satu solusi (1 tujuan ditemukan) pada pohon.
Pohon pelacakan memiliki cabang yang selalu sama, yaitu sebanyak b.
Tujuan dicapai pada level ke- d.
Tujuan
dicapai
pada
pertengahan
pohon (kondisi rata-rata). 1. Analisis Ruang
Antrian pertama memiliki 1 keadaan
Setelah mencapai langkah pertama, antrian akan berisi b keadaan.
Pemrosesan setiap b keadaan pada level ke-0 akan menambahkan b keadaan lagi pada antrian.
Sehingga
setelah
dilakukan
pemrosesan semua keadaaan pada level
ke-d,
maka
antrian
akan
menyimpan keadaan sebanyak bd-1.
Karena diasumsikan bahwa tujuan terletak ditenah, maka antrian akan menyimpan bd-1/2 keadaan.
2. Analisis Waktu Ukuran waktu disini diambil dari banyaknya keadaan yang dikunjungi. Jika diasumsikan
bahwa
setiap
node
membutuhkan waktu yang sama dalam pemrosesan maka : Waktu = waktu untuk memproses node-node di level ke-1 + waktu untuk memproses node-node di level ke-2+…+
waktu untuk memproses node-node di level ke-(d-1) + waktu untuk memproses node-node di level ke-(d)/2 = 1 + b + b2 + b3 + … + bd-1 + bd/2 = O(bd)
2.1.5.2. Depth First Search (DFS) Pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang kiri dapat dihapus dari memori12. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi. Jika solusi ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).
(i)
12
(ii)
(iii)
(iv)
(v)
Russel, Stuart and Petter Norfig.Artificial Intelegent A Modern Approach, 1995,Prentice – Hall,inc
(vi)
(vii)
Gambar 2.4 Tahapan Pembentukan Pohon DFS
Cara Kerja Algoritma DFS Dalam
algoritma
DFS,
simpul
yang
telah
dikunjungi disimpan dalam suatu tumpukan (stack). Antrian ini digunakan untuk mengacu simpul-simpul yang akan dikunjungi sesuai urutan tumpukan (masuk terakhir, keluar pertama) dan mempermudah proses runut-balik jika simpul sudah tidak mempunyai anak (simpul pada kedalaman maksimal)13. Untuk memperjelas cara kerja algoritma DFS beserta tumpukan yang digunakannya, berikut langkahlangkah algoritma DFS: 1. Masukkan
simpul
ujung
(akar)
ke
dalam
tumpukan. 2. Ambil simpul dari tumpukan teratas, lalu cek apakah simpul merupakan solusi. 3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan. 4. Jika simpul bukan solusi, masukkan seluruh simpul
yang
bertetangga
dengan
simpul
tersebut (simpul anak) ke dalam tumpukan.
13
Kusumadewi, Sri. Artificial Intelegent. 2003. Yogyakarta : Graha Ilmu
5. Jika tumpukan kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan. 6. Ulangi pencarian dari langkah kedua..
Properti Algoritma DFS Berbeda dengan algoritma BFS yang hanya
melakukan
pencarian
solusi
pada
graf
sampai
menemukannya, sehingga membutuhkan waktu yang lama, algoritma DFS menggunakan metode heuristik, sehingga solusi dapat ditemukan lebih cepat. Kompleksitas ruang algoritma DFS juga jauh lebih rendah dari algoritma BFS, karena hanya menyimpan simpul-simpul pada suatu subpohon. Akan tetapi, kompleksitas waktu algoritma DFS sama dengan kompleksitas waktu algoritma BFS. Algoritma DFS juga dapat mencari solusi secara tuntas seperti algoritma BFS, berarti algoritma ini akan menemukan solusi terbaik dan terdekat bagaimanapun bentuk graf tersebut.
Walaupun
demikian,
masih
terdapat
kelemahan algoritma DFS, yaitu jika pada graf yang sangat besar kedalaman graf terus bertambah dan tidak diketahui akhirnya, sehingga memori tidak cukup. Hal ini dapat diatasi dengan pengembangan algoritma DFS yaitu
pencarian
mendalam
berulang
(Iterative
Deepening Search - IDS)14.
Algoritma DFS:
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, maka Stop. 2. Jika Q kosong, tidak ada solusi. Stop. 3. Ambil
simpul
v
dari
kepala
(head)
antrian.Jika kedalaman simpul v sama dengan
batas
kedalaman
maksimum,
kembali ke langkah 2. 4. Bangkitkan semua anak dari simpul v. Jika
v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q.Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali
lagi
ke langkah 2.
Kelemahan, Kelebihan, Analisa Ruang Dan Waktu Kelebihan DFS adalah: Pemakain berbeda
14
jauh
memori
dengan
hanya
BFS
yang
sedikit, harus
Russel, Stuart and Petter Norfig.Artificial Intelegent A Modern Approach, 1995,Prentice – Hall,inc
menyimpan
semua
node
yang
pernah
dibangkitkan. Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat. Kelemahan DFS adalah: Jika
pohon
yang
dibangkitkan
mempunyai level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (tidak complete). Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (tidak optimal). Analisis Ruang :
Setelah berjalan 1 langkah, stack akan berisi b node.
Setelah berjalan 2 langkah, stack akan berisi (b-1) + b node.
Setelah berjalan 3 langkah, stack akan berisi (b-1) + (b-1) + b node.
Setelah berjalan d langkah, stack akan berisi (b-1) *d + 1 node, mencapai maksimum.
Analisis Waktu :
Pada kasus terbaik, DFS akan mencapai tujuan
pada
kedalaman
d
pertama,
sehingga dibutuhkan pencarian sebanyak d+1 node
Pada kasus terburuk, DFS akan mencapai tujuan pada kedalaman d pada node terakhir, sehingga dibutuhkan pencarian sebanyak : 1 + b +b2 + b3 + ... + bd = (bd+1 - 1)/(b-1).
2.2. PERANCANGAN APLIKASI 2.2.1. Context Diagram
Context Diagram atau yang dikenal dengan Data Flow Diagram (DFD) level 0 berfungsi antara lain untuk menunjukkan batasan sistem yang dibangun dengan lingkaran luarnya. Ciri diagram konteks :
1.
Menggunakan hanya satu simbol proses.
2.
Label simbol proses menggambarkan seluruh sistem.
3.
Menyertakan semua terminator dalam sistem.
4.
Menunjukkan semua arus data antara terminator dan sistem.
2.2.2. Data Flow Diagram
Data Flow Diagram (DFD) menggambarkan sebuah sistem yang sudah ada ataupun dalam sebuah rancangan sistem. Tujuan dari DFD untuk memudahkan seorang analisis untuk menganalisa dan merancang sistem. Analisa tersebut dapat berupa aliran data atau informasi, proses file atau database, sumber dan tujuan data. Diagram arus data tersebut digambarkan dengan bahan simbol-simbol atau notasi. Setiap proses dilengkapi dengan penjelasan yang lengkap mengenai identifikasi proses, nama proses dan pelaku proses. Pada diagram arus terdapat beberapa tingkatan yang terbagi
dalam level-level. Diagram arus data level 0 disebut juga context diagram yang berisi gambaran global dari sebuah sistem. Beberapa notasi yang digunakan DFD adalah untuk mewakili :
Kesatuan Luar (External Entity) Setiap sistem pasti mempunya batas sistem (boundary) yang memisahkan suatu sistem dengan lingkungan luarnya. Sistem akan menerima input dan menghasilkan output kepada lingkungan luarnya. Kesatuan luar (External Entity) merupakan kesatuan (Entity) di lingkungan luar sistem yang dapat berupa orang, organisasi atau sistem lainnya yang akan memberikan input atau menerima output dari sistem.
Arus Data (Data Flow) Arus data (Data Flow) dalam DFD digambarkan dengan notasi suatu panah. Arus data ini mengalir di antara proses (Process), simpanan data (Data Store) dan
kesatuan luar (External Entity). Arus
data ini menunjukkan arus dari data yang dapat berupa masukan untuk sistem atau hasil dari proses sistem.
Proses (Process) Suatu proses adalah kegiatan atau kerja yang dilakukan oleh orang, mesin atau komputer dari suatu arus data yang masuk ke dalam proses untuk menghasilkan arus data yang akan ke luar dari proses. Suatu proses dapat ditunjukkan dengan notasi lingkaran atau dengan notasi empat persegi panjang tegak yang sudut-sudutnya dibulatkan.
Simpanan Data (Data Store) Simpanan data pada DFD dapat disimbolkan dengan sepasang garis horizontal paralel yang tertutup pada salah satu ujungnya. Nama
dari data store menunjukkan nama file-nya, misalnya file anggota,
file barang, dan file lainnya.
No.
Simbol
Keterangan
1.
Entity
Data Flow 2.
Data 3.
Store
Process 4.
5.
Terminator
Tabel 2.1 Simbol Yang Digunakan Pada Data Flow Diagram. 2.2.3. Flow Chart Bagan alir (flow chart) adalah bagan (chart) yang menunjukkan
aliran (flow) di dalam program atau prosedur sistem secara logika15. Bagan alir digunakan terutama untuk alat bantu komunikasi dan untuk dokumentasi. Ada tiga macam bagan alir yang akan dibahas dalam modul ini, yaitu :
Bagan Alir Sistem Bagan Alir Sistem (Sistem Flow Chart) merupakan bagan yang menunjukkan arus pekerjaan secara keseluruhan dari sistem. Bagan ini menjelaskan urutan-urutan dari prosedur – prosedur yang ada di dalam sistem. Bagan alir sistem menunjukkan apa yang dikerjakan sistem.
Bagan Alir Dokumen Bagan alir dokumen (Document flow chart) atau disebut juga bagan alir formulir
(Form flow chart) atau paperwork flowchart
merupakan bagan alir yang menunjukkan arus dari laporan dan formulir termasuk tembusan-tembusannya. Bagan alir dokumen ini menggunakan simbol-simbol yang sama dengan simbol yang digunakan dalam bagan alir sistem.
Bagan Alir Program Bagan alir program (program flow chart) merupakan bagan yang menjelaskan secara rinci langkah-langkah dari proses program. Bagan alir program dibuat dari derivikasi bagan alir sistem. Bagan alir digambarkan dengan menggunakan simbol-simbol sebagai berikut :
No.
15
Nama
Jogianto:1999:295
Simbol
Keterangan
1.
Dokumen
Menunjukkan dokumen input dan output baik untuk proses manual, mekanik atau komputer.
2.
Proses
Menunjukkan
kegiatan
proses
dari
operasi program komputer. 3.
4.
Simpanan
File non komputer yang diarsip menurut
Offline
urutan tertentu.
Penghubung
Menunjukkan penghubung ke halaman yang masih sama atau ke halaman lain.
5.
Input/Output
Digunakan untuk mewakili data input atau output.
6.
Garis Alir
Digunakan untuk menunjukkan arus dari
( flow lines
proses.
symbol ) 7.
Keputusan
Digunakan untuk suatu penyelesaian
(Decision
kondisi di dalam program.
symbol)
8.
Titik Terminal
Digunakan untuk menunjukkan awal dan
(terminal
akhir dari suatu proses.
point symbol) 9.
Data Store
Digunakan untuk menggambarkan simpanan data.
Tabel 2.2 Simbol-Simbol Pada Diagram Alir (Flow Chart)
2.3. 2.3.1.
DELPHI Pengenalan Delphi Delphi merupakan salah satu bahasa pemrograman visual yang dikembangkan oleh Borland. Bahasa pemrograman Delphi dapat digunakan untuk berbagai keperluan baik untuk perhitungan matematis, aplikasi perkantoran, aplikasi multimedia, pembuatan aplikasi pengolah, aplikasi kontrol industri sampai kepada aplikasi16. Bahasa pemrograman Delphi terdiri dari beberapa bagian. Untuk lebih jelasnya lihat gambar di bawah ini :
Gambar 2.5 Bagian-Bagian Dari Pemrograman Delphi Keterangan : 1. Menu Bar Semua perintah yang diperlukan selama merancang 16
Agung, Pengenalan Dlphi 7,www.ilmukomputer.com
dan membangun program aplikasi. Terletak di bagian atas jenfela utama Delphi.
2. Object Tree View Berupa hierarki dari komponen-komponen pallets yang telah digunakan dalam program Delphi beserta nama dari komponen tersebut.
3. Speed bar Berisi sekumpulan tombol yang digunakan untuk mengakses beberapa perintah dalam menu. Biasanya yang tersedia pada SpeedBar adalah perintah-perintah yang umum digunakan dalam proses perancangan program aplikasi.
4. Form Design Merupakan tampilan visual dari aplikasi Delphi. Form berbentuk jendela dan dapat dianggap sebagai kertas atau meja
yang
digunakan
untuk
meletakkan
komponen-
komponen pallets. Saat memulai Delphi, akan otomatis tersedia sebuah form. Pada form tersebut terdapat garis titik-titik yang disebut Grid, berguna untuk membantu pengaturan tata letak obyek yang dimasukkan dalam form. Setiap form mengandung unit. Unit dalam form inilah yang dipakai untuk mengatur dan mengendalikan form. 5. Komponen Pallets Berisi kumpulan tab, dimana setiap tab atau halaman memuat berbagai tombol komponen yang digunakan sebagai
interface program aplikasi. 6. Object Inspector
Object Inspector terdiri dari dua tab. Dua tab tersebut:
Property Digunakan untuk menentukan setting suatu obyek. Satu obyek memiliki beberapa properti yang dapat diatur langsung dari lembar properti pada jendela
object inspector maupun melalui kode program. Setting ini mempengaruhi cara kerja obyek yang bersangkutan saat aplikasi dijalankan.
Event Merupakan peristiwa atau kejadian yang diterima oleh suatu obyek, misalnya klik, drag, tunjuk dan lain-lain. Event yang diterima obyek akan memicu Delphi menjalankan kode program yang ada di dalamnya.
7. Kode Window Merupakan tempat dimana kita mengetikkan kode program yang akan dieksekusi saat aplikai berjalan. 2.3.2. Tool
Delphi
Tool merupakan alat yang akan digunakan untuk membantu kita dalam
bekerja
untuk
membuat
sebuah
aplikasi.
Tool-tool
pada
pemrograman Delphi adalah :
1. Form Form merupakan tempat kita membuat desain sebuah aplikasi atau software. Secara umum, form dapat dilihat seperti gambar berikut :
Nama Form Minimize Maximize dan Close Tempat kerja
Gambar 2.6 Gambar Form Delphi 2. komponen-komponen Delphi komponen-komponen dari Delphi dapat dilihat melalui gambar berikut ini :
Menu utama : File, edit, search, dll
Speed bar
components pallete
Macam komponen Button, check box, label, dll Gambar 2.7 Komponen-Komponen Delphi
Componnent Pallets sendiri berisi beberapa tool, diantaranya terdapat pada gambar berikut ini :
Gambar 2.8 Componnent Dari Salah Satu Pallet
3. Event Event merupakan sebuah tempat untuk menuliskan script program. Disini juga terdapat object inspectore yang berfungsi untuk mengatur sebuah kondisi.
Object inspectore Script program
Gambar 2.9 Event Dari Delphi
2.3.3. Borland Delphi 7 Borland dephi 7 merupakan pilihan dari sebagian kalangan programmer untuk membuat aplikasi. Hal ini disebabkan kelebihan yang ada pada Borland, berikut ini sebagian kecil dari banyak kelebiahan Borland Delphi 7 :
Berorientasi Object Oriented Programing. Setiap bagian yang ada pada program dipanang sebagai suatu object yang mempunyai sifat-sifat yang dapat diubah dan diatur.
Satu file EXE, setelah anda merancang program dalam IDE Delphi, Delphi akan mengkompilasinya menjadi sebuah file executable tunggal. Program yang anda buat dapat langsung dijalankan dan didistribusikan pada komputer lain tanpa perlu menyertakan file DLL dari luar. Ini merupakan sebuah kelebihan yang sangat berarti.
Borland Delphi 7 hadir bersama Borland Kylix 3 yang berbasiskan
Linux, sehingga memungkinkan anda untuk membuat aplikasi multi-platform.
2.4. PERMAINAN PUZZLE Sesuai namanya, permainan puzzle berintikan mengenai pemecahan teka-teki, baik itu menyusun balok, menyamakan warna bola, memecahkan perhitungan matematika, melewati labirin, sampai mendorong-dorong kota masuk ke tempat yang seharusnya, itu semua termasuk dalam jenis ini. Sering pula permainan jenis ini adalah juga unsur permainan dalam video game petualangan maupun game edukasi. Permainan puzzle ini banyak sekali jenisnya, diantaranya adalah Tetris, Fading Shadow, 8-puzzle, Minesweeper,
Bejeweled, Sokoban dan Bomberman. Pada kali ini penulis akan membahas tentang permainan 8-puzzle. Permainan 8-puzzle. Permainan 8-puzzle ini mempunyai peraturan yang cukup sederhana. Pada permainan ini, pemain harus mengurutkan angka-angka dari angka yang di acak dan batasan ruang yang ada. Permainan akan berakhir ketika pemain telah mengurutkan angka tersebut. Adapun status dari 8-puzzle ini adalah ubin (tile) yang bisa dipindah posisinya. 8-puzzle memiliki maksimal 4 aksi yaitu ubin digeser ke atas, digeser ke kiri, digeser ke kanan, dan digeser ke bawah dilihat dari letak ubin yang kosong (tidak ada angka). Jadi pada kasus ini ubin yang kosong harus digeser untuk menghasilkan solusi yang diinginkan.
BAB III ANALISIS DAN PERANCANGAN SISTEM
3.1.
METODE ANALISIS Analisis perangkat lunak merupakan tahap yang paling penting dalam pengembangan suatu perangkat lunak, karena kesalahan dalam tahap analisis akan mempengaruhi target yang akan dicapai. Maka dengan adanya tahap ini diharapkan dapat menentukan sejauh mana perangkat lunak dapat mencapai target. Metode analisis yang dipakai untuk menganalisis kebutuhan perangkat lunak pada permasalahan permainan 8-puzzle dengan menggunakan algoritma IDS adalah metode analisis dengan pendekatan terstruktur. Metode analisis dengan pendekatan terstruktur dilengkapi dengan alat-alat (tools) berupa komputer yang dibutuhkan dan teknik-teknik yaitu, metode dan fungsi-fungsi yang dibutuhkan dalam pengembangan perangkat lunak, sehingga hasil analisis dari perangkat lunak yang dikembangkan akan menghasilkan perangkat lunak yang strukturnya dapat didefinisikan dengan baik dan jelas.
3.2.
HASIL ANALISIS Berdasarkan analisis yang telah dilakukan maka dapat diketahui apa saja yang menjadi masukan perangkat lunak, keluaran perangkat lunak, kebutuhan perangkat keras, kebutuhan perangkat lunak, Antarmuka Perangkat lunak, kinerja yang diharapkan. 1.
Masukan Perangkat Lunak Masukan perangkat lunak pada permainan 8-puzzle dengan
menggunakan algoritma IDS ini adalah sebuah kondisi awal (initial
state) yang diperoleh dari pengacakan secara random. Selain itu masukan lainnya adalah adanya sebuah batasan pencarian (depth_limit) yang akan digunakan untuk membatasi langkah dalam mencari hasil akhir (goal state). 2.
Keluaran Perangkat Lunak Keluaran dari perangkat lunak ini berupa jumlah step yang digunakan dalam pencarian, nilai heuristic, generate node, waktu yang diperlukan untuk melakukan pencarian dan langkah-langkah dalam mencapai goal state(solusi).
3.
kebutuhan Perangkat Lunak (software) Software yang disarankan untuk dapat menjalankan aplikasi ini adalah Bahasa Pemrograman Delphi. Sedangkan untuk Sistem Operasi yang dapat menjalankan aplikasi ini adalah Windows 2000 atau XP.
4.
Kebutuhan Perangkat Keras (hardware) Perangkat keras minimum yang diperlukan untuk membangun sistem ini adalah sebagai berikut :
Processor PENTIUM 4 2,0GHz/E socket 478 atau AMD yang setara.
5.
Hardisk 40 GB .
Memory 512 MB .
VGA 8MB.
Monitor , Mouse dan Keyboard.
Antarmuka perangkat lunak Antarmuka
yang
dikembangkan
pada
perangkat
lunak
(software)
ini
berbasis
icon
yang
user
friendly
untuk
mempermudah pemakaian perangkat lunak. Dengan demikian, user yang masih pemula maupun yang sudah ahli dapat memakai perangkat lunak ini. 6.
Kinerja yang diharapkan Kinerja yang diharapkan dari hasil analisis diatas adalah perangkat lunak yang dibangun dapat menghasilkan solusi yang tepat untuk menentukan goal state dari permainan 8-puzzle dengan beberapa kriteria yang diberikan.
3.3.
METODE PERANCANGAN Metode perancangan yang digunakan dalam perancangan sistem dalam permainan 8-puzzle menggunakan algoritma IDS ini adalah metode analisi dengan pendekatan terstruktur yang menggunakan alat-alat pengembangan berupa context diagram dan Diagram Alir Data (Data Flow Diagram). 3.3.1. Context Diagram Aplikasi permainan 8-puzzle ini melibatkan 2 entity yaitu start dan goal state. Desain dari aplikasi permainan 8-puzzle digambarkan dalam context diagram berikut ini :
Gambar 3.1 DFD Level 0 (Context Diagram) Permainan 8-Puzzle
3.3.2. Data Flow Diagram Aplikasi permainan 8-puzzle ini meliputi empat (4) proses utama yaitu : Acak, depth_limit, Proses dan Reset. DFD dari aplikasi permainan 8-puzzle ini ditunjukkan pada gambar berikut ini:
Gambar 3.2 DFD Level 1 Permainan 8-Puzzle
3.4.
PERANCANGAN SISTEM (Flowchart sistem)
Flowchart sistem digunakan untuk menggambarkan keseluruhan langkah kerja dan perangkat lunak yang akan dibuat dan juga akan digunakan untuk menentukan langkah-langkah kerja dari sistem tersebut. Berikut ini akan dijelaskan urutan proses yang dilakukan oleh masing-masing entity :
Gambar 3.3 Flowchart Sistem Permainan 8-Puzzle
Proses dari permainan 8-puzzle ini diawali dengan initial state dimana kondisi ubin tersusun
secara berurutan dari ubin satu (1) sampai
ubin delapan (8) dan satu ruang kosong (ubin kosong atau tanpa angka). Lakukan pengacakan ubin. Ubin akan diacak secara random kemudian ditampilkan dalam layar. Pilihlah apakah akan menggunakan depth limit atau tidak. Apabila iya, centang terlebih dahulu checkbox yang telah tersedia kemudian masukkan nilai depth-limit yang akan digunakan untuk batasan dalam proses pencarian hasil (goal state). Ketik angka yang diinginkan atau geser panel sehingga menghasilkan angka yang diinginkan. Lakukan pencarian. Pencarian hasil (goal state) akan dilakukan sesuai dengan batasan limit yang sudah ditentukan sebelumnya. 8-puzzle akan menampilkan goal state-nya, menghitung nilai heuristic-nya, jumlah
node yang digenerate, waktu yang didapat untuk melakukan pencarian dan langkah-langkah dalam mencapai goal state. Apabila tidak menggunakan depth limit, maka langsung lakukan pencarian hasil (goal state). 8-puzzle akan menampilkan hasilnya, menghitung jumlah step yang digunakan dalam pencarian, nilai heuristicnya, jumlah node yang digenerate, waktu yang didapat untuk melakukan pencarian dan langkah-langkah dalam mencapai goal state. Berdasarkan flowchart diatas, untuk kembali ke kondisi awal permainan
didapat
dengan
melakukan
reset.
Apabila
tidak
ingin
melanjutkan permainan, klik tombol close.
3.5.
PERANCANGAN APLIKASI
3.5.1. Daftar Fungsionalitas Fungsionalitas yang ada pada program yang akan kami buat berupa pencarian solusi dari 8-puzzle dari initial state menjadi final
state, antara lain : Initial state
didapat dari mengacak 8-puzzle secara otomatis
atau secara manual dari posisi goal state. Program kami akan menunjukkan bagaimana cara untuk mendapatkan
solusi
menggunakan IDS,
dari
masalah
tersebut
dengan memilih batasan
dengan
yang akan
digunakan untuk melakukan pencarian.
Selain itu akan didapat berapa nilai heuristiknya, waktu untuk menyelesaikan masalah
tersebut, jumlah step yang
digunakan dalam pencarian, jumlah node yang di-generate, dan langkah–langkah dalam mencapai goal state.
Pada program yang kami buat ini ada kemungkinan tidak diketemukan solusinya karena adanya batasan dari limit. 3.5.2. Rancangan Struktur Data dan Algoritma Struktur data yang digunakan metode IDS :
type arah = (atas=0,kanan=1,bawah=2,kiri=3); puzz = record ID : longint; ParentID : longint; posX : byte; posY : byte; Level : integer; Suksesor : byte; Leaf : byte; Error: byte; ErrSum : longint; cell : array [0..2,0..2] of byte; end; procedure dan fungsi yang akan digunakan antara lain : procedure HitungHeuristik {procedure
ini
digunakan
heuristiknya } function cek_goal:boolean {cek diset dengan true for i
1 to 3 do
begin for j
1 to 3 do
untuk
menghitung
nilai
begin if nodeinitial[i,j] <> nodeGoal[i,j] then begin cek:=false; break; end; end; if cek = false then break; end; cek_goal diset cek}
procedure initialisasiNode { nodeinitial.atas
nil;
nodeinitial.bawah
nil;
nodeinitial.kanan
nil;
nodeinitial.kiri
nil;
nodeinitial.prev
nil;
nodeinitial.next
nil;
} procedure IDS { lakukan
pengecekan
pada
limit.
Jika
pada
limit
tersebut tidak ketemu maka bangkitkan anaknya. Jika tidak diketemukan (sudah sampai batas limit yang telah ditentukan) maka lakukan stop pencarian).
}
Algoritma IDS : function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution or failure input : problem, a problem for depth 0 to ~ do
resultDEPTH-LIMITED-SEARCH(problem,depth) if result<>cutoff then result result
Penjelasan komponen struktur data : -
ID merupakan identitas dari eight puzzle berupa bilangan numeric yang sifatnya unik.
-
ParentID merupakan identitas induk dari eight puzzle.
-
PosX merupakan posisi horizontal angka 0 dalam cell.
-
PosY merupakan posisi vertikal angka 0 dalam cell
-
Level merupakan posisi kedalaman eight puzzle
-
Cell
merupakan
matriks
dua
dimensi
yang
merupakan
manifestasi dari eight puzzle itu sendiri. Variabel global yang digunakan pada aplikasi : -
initPuzz merupakan eight puzzle yang akan menjadi start puzzle.
-
finishPuzz merupakan eight puzzle yang akan menjadi finish puzzle
-
resetPuzz merupakan eight puzzle yang akan menjadi default puzzle
-
outP merupakan array multidimensi dari eight puzzle yang akan digunakan sebagai tempat penyimpanan hasil generator operasi pencarian solusi.
Penjelasan property tambahan : -
Leaf
digunakan
untuk
menandakan
sebuah
eight
puzzle
merupakan daun yang berarti bahwa eight puzzle tersebut merupakan kandidat solusi atau parent. -
Error digunakan untuk menyimpan cost (jumlah digit angka eight puzzle yang tidak bersesuaian dengan digit angka eight puzzle solusi/tujuan).
-
ErrSum digunakan untuk menyimpan total cost eight puzzle yang merupakan penjumlahan ErrSum dari parent-parentnya.
3.5.3. Goal State (Solusi)
Goal state dari permainan 8-puzzle ini dapat dilihat sesuai gambar dibawah ini :
Gambar 3.4 Goal State Dari Permainan 8-Puzzle 3.5.4. Desain Interface Desain inerface (tampilan) dari aplikasi 8-Puzzle ini, dapat dilihat seperti gambar dibawah ini :
7 1
9
2 3 4 5 6
8
Gambar 3.5 Desain Interface Permainan 8-Puzzle Bagian – Bagian dari desain interface:
1. Puzzle yang akan dicari solusinya. 2. Tombol untuk melakukan pengacakan secara otomatis. 3. CheckBox untuk mengubah limit dari pencarian IDS. 4. Menentukan jumlah limit baru jika sudah melakukan
checkBox. 5. Tombol untuk melakukan pencarian solusi. 6. Tombol untuk mengembalikan puzzle seperti semula (keadaan goal state). 7. Solution Report dari pencarian yang meliputi: problem state (initial state), nilai heuristicnya, jumlah node yang digenerate, jumlah step yang dilakukan, waktu
yang didapat untuk melakukan pencarian. 8. Animation solution yaitu mendapatkan goal
bagaimana
cara
untuk
state dengan perubahan dari
puzzlenya. 9. Tempat keterangan dalam pencarian.
BAB IV IMPLEMENTASI DAN PEMBAHASAN
4.1
IMPLEMENTASI Tujuan dari tahap implementasi ini adalah untuk memastikan perangkat lunak yang dibuat dapat bekerja secara efektif dan efisien sesuai dengan yang diharapkan. Implementasi merupakan tahap dimana sistem siap dioperasikan pada keadaan yang sebenarnya, sehingga akan diketahui apakah sistem yang dibuat benar-benar dapat menghasilkan tujuan yang diharapkan. Sebelum program diterapkan dan diimplementasikan, maka program harus bebas kesalahan. Kesalahan program yang mungkin terjadi antara lain kesalahan penulisan dan kesalahan logika. Setelah program bebas dari kesalahan tersebut maka perangkat dapat digunakan sesuai dengan fungsinya.
4.2
ALGORITMA ITERATIVE DEEPENING SEARCH (IDS) Pembuatan algoritma IDS ini merupakan tahap yang sangat penting, dikarenakan proses pengujian hasil bertumpu pada algoritma itu sendiri. Maka dari itu harus dipastikan bahwa algoritma yang dibuat harus sesuai dengan hasil yang diharapkan. Dari hasil perancangan, maka didapat algoritma IDS sebagai berikut :
function TForm1.IDS(StartP1,FinishP1:puzz;var igen : integer; var TimeConsum : double; MaxLevel : longint = 999999999):longint; var iStart : integer; iIDF, iLvl : longint; ParentPuzz : puzz; tmpTime : double; begin istart := gettickcount;//mengambil waktu dari system kemudian disimpan di variable iStart iIDF:= -1;//asumsi iIDF=-1 (tidak ketemu) menampung pengembalian nilai fungsi IDS iLvl := 0;//isi iLvl dengan nilai 0 igen := 1; //lakukan looping selama iIDF = -1 dan iLvl<=MaxLevel while ((iIDF = -1) and (iLvl <= MaxLevel)) do begin iIdf := dfs(StartP1,FinishP1,TmpTime,iLvl);//isi iIdf dengan nilai yang dikembalikan fungsi dfs dengan inputan StartP1,FinishP1,TmpTime,iLvl iLvl := iLvl + 1;//increment iLvl end; IDS := iIDF;//kembalikan nilai fungsi IDS dengan nilai iIDF TimeConsum := (gettickcount istart)/1000; //timeconsum merupakan waktu yang dibutuhkan untuk melakukan pencarian hingga menemukan solusi yang didapat dari waktu system setelah pencarian selesai dikurangi waktu mulai pencarian, dibagi 1000 untuk mendapatkan waktu dengan satuan sekon. end;
Dengan menggunakan algoritma diatas, maka pencarian goal state atau hasil akan dilakukan. Dimulai dari posisi initial state, algoritma akan menyimpan seluruh nilai variabel dan disimpan dalam iStart. Diasumsikan bahwa nilai iIDF adalah -1 (tidak ketemu hasilnya) kemudian menampung pengembalian nilai fungsi IDS. Setelah itu mengisi level dengan nilai 0. Lakukan looping selama kondisi iIDF = -1 dan iLvl <= maxlevel, kemudian isi nilai iIDF dengan nilai yang dikembalikan fungsi DFS dengan input
StartP1,FinishP1,TmpTime,iLvl. Setelah itu kembalikan lagi nilai fungsi IDS
dengan nilai iIDF.
4.3
ANALISA PERBANDINGAN HASIL PENCARIAN DARI 4 ALGORITMA PENCARIAN PENCARIAN.. Untuk mengetahui apakah algoritma IDS merupakan algoritma yang paling efektif untuk malakukan pencarian solusi dari masalah 8-puzzle ini, maka dilakukan analisis terhadap 4 algoritma pencarian. Diantaranya yaitu Breadth First Search (BFS), Depth First Search (DFS), Uniform Cost Search (UCS) dan IDS itu sendiri. Analisa yang dilakukan meliputi waktu dalam ukuran mili detik, level, dan node yang digenerate. Ketiga point tersebut sudah mewakili untuk analisa apakah algoritma IDS adalah algoritma paling efektif
dibandingkan
dengan
algoritma
pencarian
lainnya.
Setelah
melakukan analisis dari beberapa algoritma pencarian tersebut, maka didapatkan hasil sebagai berikut :
Waktu Dan Level Yang Dibutuhkan Untuk Mencapai Solusi
No.
BFS Waktu(Ms)
Level
DFS Node
Waktu(Ms)
IDS
Level
Generated
Node
Waktu(Ms)
Level
Generated
UCS Node
Waktu(Ms)
Level
Generated
Node Generated
1
0
1
4
0
41
75
0
1
3
0
1
4
2
0
2
9
125
1064
1825
0
2
8
0
2
6
3
0
3
27
110
1001
1689
0
3
9
0
3
13
4
0
4
45
0
150
257
0
4
13
0
4
16
5
15
8
553
16
182
301
0
8
382
0
8
150
6
0
2
17
0
28
38
0
2
12
0
2
8
dst Tabel 4.1 4.1. Contoh Kasus Analisa Perbandingan Algoritma Pencarian
Keterangan : -
No. 1,2,3….dst menunjukkan urutan initial state diatas
-
Level : level pada pohon pencarian
-
Node generated : node yang dipakai dalam pencarian
-
Waktu pencarian rata-rata menghasilkan 0 millisecond karena waktu pencarian tergantung spesifikasi computer
Dari hasil analisis perbandingan dari ke-4 algoritma pencarian pada tabel diatas dapat dievaluasi berdasarkan beberapa faktor seperti dibahwah ini :
1. Completeness Berdasarkan tabel diatas, hampir semua algoritma dapat memberikan
garansi bahwa
solusi terdapat
dalam ruang
pencarian, hanya algoritma DFS yang tidak complete (hasil tidak ditemukan jika pohon yang dibangkitkan mempunyai level yang sangat dalam atau tak terhingga).
2. Time Complexity Kompleksitas waktu disini mengacu pada jumlah node yang diproses selama pencarian. Waktu yang dibutuhkan untuk melakukan pencarian pada masing-masing algoritma pencarian berbeda. Pada tabel diatas terlihat bahwa algoritma IDS dan UCS memiliki waktu pencarian yang paling sedikit, yaitu 0 detik pada tiap levelnya. Sementara BFS dan DFS memiliki waktu yang lebih lama dalam melakukan pencarian. Hal ini dikarenakan algoritma DFS melibatkan level kedalaman dalam melakukan pencarian. Sehingga algoritma DFS ini membutuhkan banyak waktu untuk melakukan pencarian.
3. Space Complexity Kompleksitas memori pada bagian ini dipengaruhi oleh jumlah node yang disimpan dalam ruang memory. Pada tabel diatas dapat dilihat bahwa algoritma IDS rata-rata menyimpan lebih sedikit node dalam ruang memorinya. Ini dapat dilihat dari jumlah node yang degenerated.IDS hanya membutuhkan sedikit memori dari ke-3 algoritma lainnya.
4. Optimality Dari
hasil
analisa
yang
dilakukan,
hampir semua
algoritma dapat bekerja secara optimal. Yaitu dapat menemukan
solusi yang paling baik dan memerlukan biaya yang sedikit. Hanya algoritma DFS saja yang tidak dapat memberikan solusi apabila terdapat dua alternative solusi tapi berada pada level yang berbeda. Berdasarkan dari analisa beberapa faktor diatas, dapat disimpulkan bahwa algoritma IDS merupakan algoritma pencarian yang paling efektif dari pada ke-3 algoritma pencarian yang lainnya. Beberapa alasan yang dapat mendukung pernyataan tersebut adalah sebagai berikut : 1) Algoritma IDS selalu menemukan solusi dengan waktu yang relatif singkat dari algoritma yang lainnya. dan apabila ada solusi lebih dari satu, maka IDS akan menemukan solusi yang paling dekat dan membutuhkan waktu yang lebih sedikit. 2) Algoritma IDS membutuhkan ruang memory yang lebih sedikit dari algoritma yang lain. Hal ini dikarenakan algoritma IDS hanya menyimpan simpul yang dibangkitkan saja. 3) Jumlah node yang dipakai dalam pencarian solusi adalah minimal, berbeda dengan ke-3 algoritma pencarian yang lainnya. 4) Apabila solusi terdapat pada level yang dalam, maka algoritma IDS akan menemukannya lebih cepat dari algoritma pencarian lainnya. 5) Algoritma IDS tidak akan pernah mennemui jalan buntu dalam melakukan pencarian. Jadi dapat dipastikan bahwa algoritma IDS dapat memberikan solusi yang diharapkan dan optimal.
4.4
APLIKASI PERMAINAN 8-PUZZLE 8-puzzle merupakan sebuah permainan yang menggunakan teknik pencarian (searching). Adapun status dari permainan 8-puzzle ini adalah ubin
yang berupa angka dari satu (1) sampai delapan (8) serta 1 buah ubin kosong (tidak ada angka) sebagai ruang untuk memindahkan ubin guna pencarian solusi. Permainan 8-puzzle ini memiliki maksimal 4 aksi yaitu ubin digeser ke atas, digeser ke kiri, digeser ke kanan, dan digeser ke bawah dilihat dari letak ubin yang kosong. Proses dari permainan 8-puzzle ini terdiri dari beberapa tahapan, yaitu : 1. Inisialisasi Inisialisasi dilakukan pada saat form dibuat, tombol reset puzzle digunakan sebagai default puzzle. Pada bagian inisiasi ini juga terdapat prosedur dengan nama prosedur set_tampilan. Prosedur set tampilan ini berfungsi untuk melakukan setting ubin-ubin dari 8-puzzle itu sendiri. 2. Prosedur Untuk Membuat 8-Puzzle Berfungsi untuk membuat 8-puzzle yang berupa data menjadi bentuk visual melalui panel-panel yang telah ada. 3. Prosedure Untuk Membuat Goal State (Solusi) Pada prosedur ini dikondisikan bahwa solusi dari permainan 8puzzle ini adalah mengurutkan ubin dari ubin satu (1) sampai ubin delapan (8) serta satu ruang kosong pada ubin ke sembilan. 4. Prosedur IDS Pada prosedur ini terdapat algoritma IDS yang akan digunakan untuk melakukan pencarian goal state dari permainan 8-puzzle tersebut. Pada prosedur ini juga terdapat beberapa perhitungan yang digunakan untuk menghitung jumlah node yang digunakan pada pencarian solusi, menghitung jumlah step yang digunakan, nilai heuristic, generate node, waktu yang diperlukan untuk melakukan pencarian dan langkah-langkah dalam mencapai goal state (solusi).
4.5
IMPLEMENTASI ANTARMUKA (FORM) Kondisi awal permainan 8-puzzle ini dapat dilihat sesuai gambar berikut ini :
Gambar 4.1 Gambar Kondisi Awal Permainan 8-Puzzle Pada aplikasi permainan 8-puzzle ini terdiri dari beberapa komponen, diantaranya : 1. Acak Otomatis Pada proses ini, ubin pada posisi initial state akan diacak otomatis secara random. Hasil dari proses pengacakan secara random tersebut dapat dilihat pada gambar dibawah ini :
Gambar 4.2 Permainan 8-Puzzle Setelah Ubinnya Diacak
Setelah proses ini dilakukan, pemain dihadapkan dengan dua (2) pilihan, yang pertama adalah menggunakan depth limit (batasan limit) dimana pencarian solusi dari permainan 8-puzzle ini akan dibatasi dengan banyaknya langkah yang ditentukan. Yang kedua adalah tanpa menggunakan depth limit. Apabila pemain tidak menggunakan depth
limit ini, maka proses pencarian solusi dapat langsung dilakukan. Pada solusi pencarian tanpa menggunakan depth limit ini akan ditambahkan informasi tentang jumlah langkah yang dilakukan untuk menghasilkan solusi. Prosedur yang digunakan adalah :
procedure TForm1.Bt_AcakClick(Sender: TObject); var i, j:byte; begin P1.visible:=true; P2.visible:=true; P3.visible:=true; P4.visible:=true; P5.visible:=true; P6.visible:=true; P7.visible:=true; P8.visible:=true; P0.visible:=true; randomize_puz; for i:=1 to 3 do for j:=1 to 3 do play.isi[i,j]:=puzzle[i,j]; play.heuristic:=CariNilaiHeuristik(play); set_tampilan(play); label2.caption:=inttostr(play.heuristic); end;
2. Batasan Limit (Depth Limit) Pada proses ini pemain diharuskan melakukan centang pada
checkbox yang disediakan, kemudian mengatur berapa maksimum depth yang akan digunakan. Penggunaan maksimum depth ini dimaksudkan
untuk membatasi pencarian solusi. Sehingga dimungkinkan tidak adanya solusi. Pemilihan maksimum depth dapat dilihat dari gambar dibawah ini :
Gambar 4.3 Permainan 8-Puzzle Dengan Memilih Batasan Limit Prosedur yang digunakan untuk menampilkan pilih batas adalah sebagai berikut :
procedure TForm1.pilih_batasClick(Sender: TObject); begin pakai_batas:=pilih_batas.Checked; txt_level.Enabled:=pilih_batas.Checked; updw.Enabled:=pilih_batas.Checked; end;
3. Search Pada proses inilah akan dihasilkan goal state (solusi). Setelah tombol search ditekan, maka pencarian solusi akan dilakukan. Solusi disini meliputi hasil pencarian, jumlah node, jumlah node yang
digenerate, jumlah waktu yang diperlukan untuk menemukan solusi, jumlah heuristic dan jumlah langkah (step) yang dilakukan untuk menghasilkan solusi. Perlu diingat bahwa ada kemungkinan tidak adanya solusi dikarenakan adanya batasan limit. Setelah pencarian solusi didapat, semua hasil data yang diperoleh diletakkan pada solution report (groupbox proses) serta memo yang telah disediakan. Hasil dari pencarian solusi dapat dilihat pada gambar berikut ini :
Gambar 4.4 Tampilan Setelah Ditekan Tombol Search Prosedur yang digunakan untuk melakukan search adalah :
procedure TForm1.searchClick(Sender: TObject); var c1,c2,i,j:byte; begin batas_level:=updw.Position; c1:=play.lokasi; play.heuristic:=CariNilaiHeuristik(play); search.Visible:=false; stop.Left:=search.Left; stop.Top:=search.Top; stop.Visible:=true; processing:=true; hthread_ids:=beginThread (nil,0,@Fth_ids,nil,0,ThreadID_ids); end;
Pada tampilan solusi diatas, terdapat beberapa hasil diantaranya jumlah depth yaitu 1, jumah node yang digunakan adalah 159, generate
node 198, waktu yang digunakan adalah 2,442 detik, nilai heuristic 7,dan keterangan yang ditampilkan dalam memo. 1.
Nilai Heuristic Pada permainan 8-puzzle ini, nilai heuristic dicari dengan menggunakan sebuah function. Function yang digunakan adalah :
function CariNilaiHeuristik(x : node):byte; // function untuk melakukan pencarian nilai heuristik dengan metode manhattan var h, c1, c2, m, n,c3, c4 : byte; posisi : byte; begin h:=0; posisi := 0; //heuristic manhattan for c1:=1 to 3 do for c2:=1 to 3 do for c3:=1 to 3 do for c4:=1 to 3 do if x.isi[c1,c2]=puzzle2[c3,c4] then if (x.isi[c1,c2]<>0) then h:= h + abs(c1 - c3) + abs(c2 - c4); CariNilaiHeuristik:=h; end;
Setelah nilai heuristic didapat, hasilnya disimpan kemudian ditampilkan dalam tempat yang telah disediakan. 2.
Waktu Yang Dibutuhkan Dalam melakukan pencarian solusi dari permainan 8puzzle ini, yaitu menyusun ubin dari angka satu (1) hingga angka delapan (8), tentunya memerlukan sejumlah waktu. Prosedur yang digunakan adalah sebagai berikut :
procedure TForm1.Timer1Timer(Sender: TObject); begin if trackbar1.position < trackbar1.max then trackbar1.position:=trackbar1.positio n + 1; label14.Caption:=IntToStr(TrackBar1.P osition); if trackbar1.position = trackbar1.max then begin timer1.Enabled:=false; button5.caption:='>'; end; end;
Setelah
dilakukan
perhitungan
waktu
tersebut,
didapatkan sejumlah waktu yang dibutuhkan dalam pencarian solusi dari pengacakan ubin tersebut. Dengan dihasilkannya ratarata jumlah waktu yang relatif singkat, bisa dikatakan bahwa pencarian solusi tersebut adalah cepat atau efektif. 3.
Jumlah Node Yang Digunakan untuk
mengetahui
jumlah
node
yang
digunakan,
procedure yang digunakan adalah :
function F_IDS(head:ids_node):ids_node; var temp:ids_node; begin jum_node:=1; jum_gen:=0; level_skr:=0; goal:=false;
//a_star:=true; //playing:=false; c:=0; //play.heuristic:=hitung_h(play); head.level:=0; root:=head; open:=head; closed:=nil; form1.Bt_Acak.enabled:=false; batas_level_skr:=1; while ((batas_level_skr <= batas_level) or (not pakai_batas)) and (goal = false) do begin head.level:=0; root:=head; open:=head; closed:=nil; while (open <> nil) do begin //form1.animasi; level_skr:=open.level; form1.katerangan; if stop_cari then begin goal:=false; break; end; //if open = nil then F_bfs:=nil //else //begin node_X:=open; if cek_goal(node_X) = false then begin pindah_X_ke_closed(node_X); TambahAnak(node_X); //termasuk pindah anak2 x ke open //dan hilangkan anak2 x yg sudah ada di open atau closed inc(c); end else begin goal:=true; break; end; end;
if stop_cari then begin goal:=false; break; end; inc(batas_level_skr); //pindah_best_ke_close(bestnode); // if bestnode.heuristic=0 then // goal:=true // else // begin // generate_succ(bestnode); // inc(c); // end;//end else //end;//end else end;//endwhile if goal then F_ids:=node_X else F_ids:=nil; end; end.
4.
Reset Pada proses ini, ubin akan dikembalikan pada posisi semula dan pemain dapat mencobanya kembali sesuai dengan langkah-langkah diatas. Kondisi 8-puzzle setelah direset :
Gambar 4.5 Gambar 8-Puzzle Setelah Di Reset Prosedur yang digunakan adalah :
procedure TForm1.resetClick(Sender: TObject); begin langkah:=0; memo_hist.Clear; label2.caption:='H'; label9.caption:='10'; label13.caption:='0'; L_jum_node.Caption:='0'; label_gen.Caption:='0'; label_level.Caption:='0'; label_time.Caption:='0'; L_Step.Caption:='0'; button3.enabled:=false; button4.enabled:=false; button5.caption:='>'; Bt_acak.enabled:=true; search.Enabled:=true; P1.visible:=true; P2.visible:=true; P3.visible:=true; P4.visible:=true; P5.visible:=true; P6.visible:=true; P7.visible:=true; P8.visible:=true; P0.visible:=true; jum_node:=0; //jum_semua_node:=0; jum_gen:=0; if not playing then begin //hancurkan list langkahlangkah solusi destroy_list; head_list:=nil; //hancurkan tree dan inisialisasi tree dan list dari current destroy_tree(root); head:=nil; end; inisialisasi_puz2; inisialisasi; inis_kotak; label2.Caption:=inttostr(CariNilaiHeur istik(play)); end;
5.
Menu File Dalam menu file ini hanya terdapat satu sub menu saja yaitu
exit. Sub menu ini berfungsi untuk keluar dari permainan 8puzzle ini selain menggunakan tool yang ada pada bar. Apabila menu file ini di click, maka akan tampak seperti gambar dibawah ini :
Gambar 4.6 Gambar Setelah Menu File Di Click Pada menu click ini, terdapa prosedur untuk keluar dari permainan. Prosedur yang digunakan adalah :
procedure TForm1.Exit1Click(Sender: TObject); begin application.Terminate; end; end. 6.
Menu Help Apabila menu help ini diclick, maka akan muncul menu about yang berisi tentang informasi pembuat program. Apabila menu help diclick, maka akan tampak seperti yang terlihat pada gambar dibawah ini :
Gambar 4.7 Gambar Menu About
4.6
UJI COBA PERANGKAT LUNAK Pada bagian ini akan dilakukan uji coba terhadap perangkat lunak dengan cara melakukan debug program sehingga program dapat berjalan. Kemudian dilakukan acak secara otomatis sehingga dihasilkan tampilan sebagai berikut :
Gambar 4.8 Gambar Initiated 8-Puzzle Setelah itu, diberikan batasan limit pada limit 10. kemudian dilakukanlah pencarian dengan cara menekan tombol search. Setelah dilakukan pencarian solusi terhadap salah satu hasil pengacakan dan batasan limit
tersebut, maka didapat hasil sebagai berikut ini : 1) Nilai heuristik dari puzzle tersebut adalah 11 2) Waktu yang digunakan untuk melakukan pencarian goal state dari permasalahan diatas adalah 3 detik 155 mili detik 3) Generate node = 198 4) Jumlah node yang digunakan = 159 5) Hasil dari pencarian adalah tidak ditemukannnya solusi. Hal ini dikarenakan bahwa dalam contoh permasalahan diatas dilakukan pembatasan limit yaitu 10. Dan setelah dilakukan pencarian sampai pada batas tersebut, solusi tidak ditemukan. Hasil dari pencarian solusi tersebut dapat dilihat pada gambar berikut ini:
Gambar 4.9 Gambar Hasil Akhir Permainan 8-Puzzle
BAB V PENUTUP
5.1
KESIMPULAN Setelah diuraikan seluruh proses perancangan dan pembuatan permainan 8-puzzle ini, dapat disimpulkan bahwa :
IDS merupakan metode yang menggabungkan keuntungan BFS (complete
dan
optimal)
dengan
keuntungan
DFS
(space
complexity yang rendah), tapi konsekuensinya time complexitynya menjadi tinggi.
Pemakaian memori hanya sedikit, karena hanya node-node pada lintasan yang aktif saja yang disimpan berbeda jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.
Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka IDS akan menemukannya secara cepat.
Tidak akan menemui jalan buntu
Jika ada satu solusi, maka IDS akan menemukannya, dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan
Waktu yang digunakan relatif singkat
Jumlah node yang dipakai dalam penarian solusi adalah minimal
Manfaat aplikasi ini sebagai berikut:
Memberikan wawasan tentang algoritma pencarian terutama algoritma pencarian Iterative Deepening Search (IDS).
Mengetahui
waktu
yang
dibutuhkan
untuk
menyelesaikan
permainan 8-puzzle.
Mengetahui jumlah step yang digunakan dalam pencarian, jumlah node yang digenerate, dan langkah – langkah dalam mencapai goal state.
5.2
SARAN Dalam Pembuatan Tugas Akhir masih menemui beberapa kendala pada aplikasi permainan 8-puzzle ini, mungkin bila pengembangan bisa dilanjutkan maka hal pertama kali dilakukan adalah melakukan perbaikan pada tampilan. Dengan tampilan yang menarik akan menjadi nilai tambah bagi permainan ini
dikarenakan keingintahuan user akan semakin besar untuk mencoba permainan tersebut.
DAFTAR PUSTAKA
Hapnes Toba. Pencarian Tanpa Informasi. New York : PIB Lesson 4; Kusumadewi, Sri. 2003. Artificial Intelegent. Graha Ilmu : Yogyakarta; Munir, Rinaldi. 2006. Matematika Diskrit. Informatika Bandung: Bandung; Robert R. Korfhage. 1966. Logic and Algorithms. John Wiley & Sons.Inc : New York; Russel, Stuart dan Petter Norfig. 1995. Artificial Intelegent A Modern Approach. Prentice – Hall, inc : USA Sedgewick, Robert. 1983. Algorithms. Addison-Wesley Publishing Company.Inc : USA;
