A Comparative Study of A* and Greedy Best-First Search Algorithms in Solving 8-Puzzle Game
Cuvinte cheie:
AI, Machine learning, A*, ML AlgorithmRezumat
The 8-puzzle is a classic problem in the real world. It involves swapping a tile's position with an empty slot until the goal state is reached from a given initial state in the puzzle. A search algorithm helps to solve the problem of finding the shortest path between two points or two states, as in the case of this study.
In this study, we compare the performance of two well-known search algorithms, A* and greedy best-first search, in solving the 8-puzzle game. We implemented both algorithms in Python and ran experiments on test puzzle cases to evaluate their performance. The resulting outcome shows that the A* algorithm consistently outperformed the greedy best-first search algorithm in terms of both the number of moves required to reach the goal state and the running time. For most test cases, Greedy best-search could not solve the given puzzle problem within the stipulated time limit of 2 minutes.
Referințe
(1)Russell, S. and Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Prentice-Hall.
(2)Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27(1), 97-109.
(3)Pillay, N. (2015) “Intelligent system design using hyper-heuristics,” South African Computer Journal, 56. Available at: https://doi.org/10.18489/sacj.v56i1.268.
(4)Biship, C. M. (2006). Pattern Recognition and Machine Learning (1st ed.). Springer.
(5)Bostrom, N. (2014). Superintelligence: Paths, Dangers, and Strategies. Oxford University Press.
(6)Feigenbaum, E. A., & Feldman, J. (1963). Computers and Thought. MIT Press.
(7) Gulshan, V., Peng, L., Coram, M., Stumpe, M. C., Wu, D., Narayanaswamy, A., ... & Webster, D. R. (2016). Development and Validation of a Deep Learning Algorithm for Detection of Diabetic Retinopathy in Retinal Fundus Photographs. JAMA, 316(22), 2402-2410.
(8) Mitchell, T. M. (1997). Machine Learning. McGraw-Hill.
(9) Nguyen, A., Jo, H., & Han, S. (2015). Deep learning for healthcare: review, opportunities and challenges. Briefings in Bioinformatics, 17(2), 358-377.
(10) Shalev-Shwartz, S., Shammah, S., & Shashua, A. (2017). On the Design and Implementation of Autonomous Driving Systems. Foundations and Trends in Robotics, 6(1), 1-54.
(11) Brown, T., Mann, G. S., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., ... & Neelakantan, A. (2020). Language Models are Few-Shot Learners. arXiv preprint arXiv:2005.14165.
(12) Krizhevsky, A., Sutskever, I., & Hinton, G. E. (2012). ImageNet Classification with Deep Convolutional Neural Networks. In Advances in Neural Information Processing Systems (pp. 1097-1105).
Legg, S., & Hutter, M. (2007). Universal Intelligence: A Definition of Machine Intelligence. Minds and Machines, 17(4), 391-444.
Descărcări
Publicat
Cum cităm
Număr
Secțiune
Licență
Open access and copyright policy
The journal offers access to the contents in the open access system on the principles of non-exclusive license Creative Commons (CC BY 4.0). Thus, the authors are required to agree with that policy. In this regard, authors will be asked to complete a submission card with a copyright transfer agreement that specifies detailed descriptions of the copyright transfer. The submission card is provided via email before the publication.
Publication fee
IJSSASS is a self-funded journal. For this reason, the journal handles a publication fee. The current publication fee is provided on the journal’s Web site in the section Instruction for authors. Thus, the publication fee that is required for manuscript processing is clearly stated on our website
