Comparison of A* Algorithm and Greedy Best Search in Searching Fifteen Puzzle Solution
DOI:
https://doi.org/10.24203/ijcit.v11i3.242Keywords:
A*, Artificial Intelligence, Fifteen Puzzle, Greedy Best First SearchAbstract
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*.
References
. 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
. Kuang Ping, Luo Shuai. “A Brief Introduction of an Improved A* Search Algorithm”.2013
. 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
. Yuanliang Zhang. “A Method of Ship’s Path Planning at Sea”. Applied Mechanics and Materials Vols 321-324 (2013) pp 2038-2041. 2013.
. 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
. 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
. 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
. 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
. 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
. 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
. 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
. 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
. 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
. Han Wang, Yan Piao. “Research on Optimal Path Finding Algorithm”. Applied Mechanics and Materials Vols. 427-429(2013) pp 1883-1887. 2013
. 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
. 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
. 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
. 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.
. 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
Downloads
Published
Issue
Section
License
Copyright (c) 2022 Charisma Tubagus Setyobudhi
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
The articles published in International Journal of Computer and Information Technology (IJCIT) is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
