Skip to main content Skip to main navigation menu Skip to site footer
Articles
Published: 2019-12-31

Perbandingan Algoritma A* (A star) dan Algoritma IDA* (Iterative Deepening A* Pada Permainan Sliding Puzzle

Abstract

One of the games discussed in this study is a puzzle game. In a puzzle game players are expected to be able to achieve the final goal to form a correct picture or pattern. The algorithms used in this study are the A* algorithm (A Star) and IDA* algorithm (iterative deepening A*). This study aims to determine the completion process of the game Sliding Puzzle using A* Algorithm and IDA* Algorithm and determine which algorithms are more efficient. Based on the time complexity it was found that the A* algorithm is more efficient than the IDA* algorithm because it only chooses the smallest value of f, apart from the IDA* algorithm which tries all possible steps with the same value of f. The disadvantages of these two algorithms are that in some cases this algorithm cannot solve the problem or stop at the local optimum or the same step  repeated.

References

  1. Adipranata, Rudi, Andreas Handojo & Happy Stiawan. 2007. Aplikasi Pencari Rute Optium pada Peta GunaMeningkatkan Efisiensi Waktu Tempuh Pengguna Jalandengan Metode A* dan Best First Search.Surabaya: Jurnal INFORMATIKA Vol. 8, No. 2, 100 – 108.
  2. Brualdi, Richart A, 2010, Introductory Combinatorics, China Machine Press, Beijing.
  3. Hallimsah, Beny H, Eggy Margiso, 2014, Problem Solving Permainan Puzzle 8 Menggunakan Algoritma A*,pontianak , Vol. 4, No. 1.
  4. Harris, J.M., Jeffry L.H., & Michael J.M., 2000, Combinatorics and Graph Theory, Springer, USA.
  5. Hidayatullah, Halilintar Nur, 2007, Implementasi Algoritma IDA* (Iteratif Deepening A*) dalam Menentukan Solusi Terbaik Pada Permainan Otello 6x6 dengan Simulasi Matlab, skripsi, Program Studi Matematika Fakultas MIPA Universitas Mataram.
  6. Hermianto, 2017, Implementasi Algoritma Runtun Balik (Backtraking) Dalam Penyelesaian Permainan Puzzle Sudoku Berbasis Android, Medan, Skripsi, Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Iinformatika Universitas Sumatra Utara Medan.
  7. Munir, Rinaldi., 2014, Matematika Diskrit, Informatika, Bandung.
  8. Mutiana, Veronica. Fitria Amastini. & Noviana Mutiara. 2013. Optimasi Pencarian Jalur Dengan Metode A* ( A star ). Tenggareng: Jurnal ULTIMATICS, Vol. 5, No. 2.
  9. Russell, Stuart J dan Peter Norvig. 2010. Artificial Intelligence A Modern Approach Third Edition. New Jersey.
  10. Suyanto. 2007. Artificial Intelligence. Informatika. Bandung.