International Journal of Computer and Information Technology

Open Access Open Access  Restricted Access Subscription Access

Comparison of A* Algorithm and Greedy Best Search in Searching Fifteen Puzzle Solution


Affiliations
1 Department of Computer Science, Faculty of Technology and Engineering, Diponegoro University, Jl. Prof. Soedharto SH, Tembalang, Semarang, Indonesia
 

Artificial Intelligence is an exciting field to research. Artificial Intelligence itself is a broad subject. The application of artificial intelligence in daily routine is various. One of the usages of artificial intelligence is finding the shortest route on a map. In general, the algorithm which can be used for finding the shortest route is A*. A* is often used in finding the shortest route in a graph or map. Generally speaking, A* is used to make a game, especially for finding the shortest route of an intelligent agent inside it. In this paper, the finding solution of puzzle game using A* and Greedy Best First Search is to be discussed. The puzzle game which is discussed is the Fifteen Puzzle. This research compares the two algorithms used, A* and Greedy Best First Search. This research shows that Greedy Best First Search gives a slightly faster solution than A*.

Keywords

A*, Artificial Intelligence, Fifteen Puzzle, Greedy Best First Search.
User
Notifications
Font Size

  • [1]. Li xiao min, Wang Jian Ping, Ning Xin. “A* Algorithm based Robot Planning”. Applied Mechanics and Materials Vols 63-64(2011) pp 686-689.2011

  • [2]. Kuang Ping, Luo Shuai. “A Brief Introduction of an Improved A* Search Algorithm”.2013

  • [3]. Yang Zhong Xiu, Ren Xiao Bao, Song Jia-tao, Wang Wan-liang. “Schedule Study and Simulation Experiment. of Lift sliding Stereo Garage Based on A*”. Applied Mechanics and Materials Vol 109(2012) pp 523-527. 2011 www.ijcit.com 83

  • [4]. Yuanliang Zhang. “A Method of Ship’s Path Planning at Sea”. Applied Mechanics and Materials Vols 321-324 (2013) pp 2038-2041. 2013.

  • [5]. Frantisek Duchon, Dominik Hunady, Martin Dekan, Andrej Babinec. “Optimal Navigation for Mobile Robot in Known Environment”. Applied Mechanics and Materials Vol 282(2013) pp 33-38. 2013

  • [6]. Huan Wang, Yulian Jiang. “Robotic Fish Path Planning based on Improved A* Algorithm”. Applied Mechanics and Materials Vols 336-338(2013) pp 968-972.2013

  • [7]. Liping Cheng, Bo Yan, Yonghai Tan. “Application of CAN bus and the Layered A* Algorithm in the Parking Guidance System”. Applied Mechanics and Materials Vols 602-605 (2014) pp 887-890.2014

  • [8]. Xia Chen, Xiangmin Chen, Jing Zhang. “The Dynamic Path Planning of UAV based on A* Algorithm”. Applied Mechanics and Materials Vols 494-495 (2014) pp 1094-1097.2014

  • [9]. Shrawan Kr Sharma, B.L. Pal. “Shortest Path Searching for Road Network Using A* Algorithm”. International Journal of Computer Science and Mobile Computing Vol 4 Issue 7, July 2015, pg 513-522.2015

  • [10]. Shang Erke, Dai Bin, Nie Yiming, Zhu Qi, Xiao Liang, Zhao Dawe. “An improved A Star based Path Planning algorithm for Autonomous Land Vehicles”. International Journal of Advanced Robotic Systems September-October 2020: 1-13.2020

  • [11]. Zhao Zhiqiang, Liu Zhihua, Hao Jiaxin. “Path Planning for Ground Simulation Object Based on A* Algorithm”. Applied Mechanics and Materials Vols 229-231(2012) pp 2019-2024. 2012

  • [12]. Xiangguang He, Yaya Wang. “Researching on AI Path Finding Algorithm in Game Development”. 2012 International Symposium on Instrumentation and Measurement, Sensor Network and Automation. 2012

  • [13]. Zhanying Zhang, Ziping Zhao. “A Multiple Mobile Robots Path Planning Algorithm Based on A* and Dijkstra”.International Journal of Smart Home Vol.8 No.3 (2014) pp 75-86. 2014

  • [14]. Han Wang, Yan Piao. “Research on Optimal Path Finding Algorithm”. Applied Mechanics and Materials Vols. 427-429(2013) pp 1883-1887. 2013

  • [15]. Dr.K. Sudhagar, M.Bala Subramanian, G.Rajarajeswari. “Path planning of Mobile Robot Agent using Heuristic Based Integrated Hybrid Algorithm”. Advanced Materials Research Vols 984-985 (2014) pp 1229-1234. 2014

  • [16]. Akshay Kumar Guruji, Himansh Agarwal, D.K. Prasediya. “Time Efficient A* Algorithm for Robot Path Planning”. 3rd International Conference on Innovations in Automation and Mechatronics Engineering ICIAME 2016. 2016

  • [17]. Anggina Primanita, Rusdi Effendi, Wahyu Hidayat. “Comparison of A* and IDA* for Non Player Character in Role Playing Game”. International Conference on Electrical Engineering and Computer Science (ICECOS) 2017. 2017

  • [18]. Yan-yan Zhang, Yan chun Shen, Li Ni Ma. “Pathfinding Algorithm of 3D Scene Based on Navigational Mesh”. Advanced Materials Research Vols 1030-1032 (2014) pp 1745-1750. 2014.

  • [19]. Milena Karova, Ivaylo Penev, Neli Kalcheva.”Comparative analysis of Algorithms to search the Shortest Path in a Maze”. 2016 IEEE International Black Sea Conference on Communications and Networking (BlackSeaCom). 2016


Abstract Views: 168

PDF Views: 97




  • Comparison of A* Algorithm and Greedy Best Search in Searching Fifteen Puzzle Solution

Abstract Views: 168  |  PDF Views: 97

Authors

Charisma Tubagus Setyobudhi
Department of Computer Science, Faculty of Technology and Engineering, Diponegoro University, Jl. Prof. Soedharto SH, Tembalang, Semarang, Indonesia

Abstract


Artificial Intelligence is an exciting field to research. Artificial Intelligence itself is a broad subject. The application of artificial intelligence in daily routine is various. One of the usages of artificial intelligence is finding the shortest route on a map. In general, the algorithm which can be used for finding the shortest route is A*. A* is often used in finding the shortest route in a graph or map. Generally speaking, A* is used to make a game, especially for finding the shortest route of an intelligent agent inside it. In this paper, the finding solution of puzzle game using A* and Greedy Best First Search is to be discussed. The puzzle game which is discussed is the Fifteen Puzzle. This research compares the two algorithms used, A* and Greedy Best First Search. This research shows that Greedy Best First Search gives a slightly faster solution than A*.

Keywords


A*, Artificial Intelligence, Fifteen Puzzle, Greedy Best First Search.

References