Analytical Study of the A* Heuristic Search Algorithm Used to Solve Efficiently a Puzzle Game
Polyhedra (prisms, pyramids, or pyramidal frustums) can be moved using the available open spaces in the puzzle game given in this paper. The challenge necessitates determining the smallest number of movements required for the game to go from its original configuration to a goal configuration. The main difficulty in addressing the problem is due to the size of the search space, which necessitates the use of a heuristic search. The search method can be improved by determining a strong estimate using a heuristic function, which will direct the search process to the most promising side of the search tree. Using the A* search algorithm implemented in Java, a comparison study is carried out between the Hamming, Manhattan, and Chebyshev heuristics. This paper also covers the stages of object-oriented software development that are required to solve this puzzle game efficiently. The programme is modelled using specialised UML diagrams that represent the steps of analysis, design, and implementation, resulting in a clear and realistic description of the system. The space complexity criterion was used to confirm theoretical conclusions demonstrating that the Manhattan heuristic is more efficient. The number of created nodes from the search tree, the number of enlarged nodes, and the effective branching factor were used to determine the space complexity. The Chebyshev heuristic improved the space complexity of the A* algorithm when compared to the Hamming and Manhattan heuristics, according to the experimental data.
Computer Science Department, Faculty of Automation and Computer Science, Technical University of Cluj-Napoca, Romania.
View Book :- https://stm.bookpi.org/AAER-V9/article/view/1011