• Document: Implementasi Algoritma A Star pada Pemecahan Puzzle 8
  • Size: 460.23 KB
  • Uploaded: 2018-10-18 04:23:19
  • Status: Successfully converted


Some snippets from your converted document:

Jurnal Teknik Informatika Vol. 1 September 2012 1 Implementasi Algoritma A Star pada Pemecahan Puzzle 8 Yuliana, Ananda dan Ibnu Surya Progr;am Studi Teknik Informatika Politeknik Caltek Riau, Jln. Umbansari no.1 Rumbai Pekanbaru 28261 1 can_1ee14@yahoo.com, 2ananda@pcr.ac.id, 3ibnu@pcr.ac.id Abstrak Puzzle 8 adalah sebuah permainan dimana terdapat sembilan kotak angka, huruf maupun gambar yang diacak, yang harus disusun kembali ke posisi yang benar dan terurut. Banyak metode yang dapat digunakan untuk menyelesaikan puzzle 8, salah satunya menggunakan metode best first search. Di dalam best first search terdapat sebuah fungsi yang dinamakan fungsi heuristik. Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian. Salah satu algoritma yang memakai fungsi heuristic adalah Algoritma A Star. Fungsi heuristik yang digunakan adalah dengan melihat banyaknya kotak pada posisi yang salah dan total keseluruhan jarak dari kotak yang berada di tempat yang salah untuk mencapai posisi yang benar. Fungsi ini sering juga disebut dengan manhattan distance. Tujuan dari pembuatan proyek akhir ini untuk mengimplementasikan Algoritma A Star pada permainan puzzle 8. Dari aplikasi ini dapat dilihat bahwa Algoritma A Star mampu memberikan jalur dalam penyelesaian puzzle 8. Setelah pengujian berulang yang dilakukan, dapat dilihat perbandingan hasil antara Algoritma A Star dengan Algoritma Greedy dimana Algoritma A Star menghasilkan jalur yang lebih pendek dalam menyelesaikan puzzle 8. Kata kunci : Best first search, Algoritma A Star, Puzzle8 Abstract 8 Puzzle is a game where there is nine square number, alphabet or picture which are mixed, that should arrange to the right position and in order. There are some methods that can be use to solve 8 puzzle, one of them is by best first search method. In best first search, there is a function that called heuristic function. Heuristic is a t that expands the efficiency in searching process. One of the algorithm that use heuristic function is A star algorithm techniques. Heuristic function worked in counting how many boxes that is in wrong position and the total distance from the wrong boxes to reach the right position. This function also called by Manhattan distance. The aim of this research is to implement A Star algorithm in 8 puzzles. This application proves that A Star algorithm able to give a solution in solving 8 puzzle. Some repeated experiment showed the result comparison between A Star algorithm with Greedy’s algorithm where A Star give a shorter output path to solve the 8 puzzle. Keywords : Best first search , A Star algorithm, 8 puzzle 1. Pendahuluan 1.1 Latar Belakang Aplikasi permainan merupakan salah satu implementasi dari ilmu di bidang komputer. Inti dari sebuah aplikasi permainan adalah mengembangkan kemampuan otak untuk mengatur strategi, kecepatan, dan ketepatan dalam mencapai tujuan akhir. Salah satu contoh permainan adalah puzzle [5]. Puzzle terdiri dari beberapa jenis, ada yang menggunakan angka, huruf, dan gambar. Dalam permainan puzzle, pemain diharapkan dapat mencapai tujuan akhir untuk membentuk sebuah puzzle menjadi sebuah gambar atau pola yang benar dengan waktu yang cepat. Algoritma A Star adalah algoritma pencarian graf yang menemukan jalur dari status awal ke status akhir. Algoritma ini menggunakan fungsi heuristic (biasanya didenotasikan dengan ) untuk menentukan urutan dimana pencarian dilakukan dengan mengunjungi node dalam pohon. merepresentasikan biaya jalan yang paling efisien sampai ke tujuan [4]. Fungsi heuristic yang digunakan Algoritma A Star untuk memecahkan kasus bervariasi tergantung dari kasus yang akan dihadapi, misal untuk memecahkan kasus pencarian jalur terpendek dari satu ke kota lain menggunakan fungsi heuristic distance plus cost sedang untuk memecahkan Jurnal Teknik Informatika Vol. 1 September 2012 2 kasus Puzzle 8, maka digunakan fungsi heuristic city block distance atau sering juga disebut dengan istilah manhattan distance. 1.2 Tujuan Tujuan dari proyek akhir ini adalah mengimplementasikan algoritma A Star pada pemecahan puzzle8 agar dapat membuktikan bahwa Algoritma A Star dapat digunakan dalam penyelesaian puzzle 8 dan dapat melihat perbandingan antara Algoritma A Star dengan Algoritma Greedy. 1.3 Perumusan Masalah Bagaimana menempatkan bilangan 1-8 dengan kondisi teratur dalam suatu kotak ukuran 3x3 dengan salah satu Best first search yaitu algoritma A Star. 1.4 Ruang Lingkup Adapun ruang lingkup pada proyek akhir ini adalah ukuran dar

Recently converted files (publicly available):