A Comparative Study of Three Heuristic Functions Used to Solve the 8-Puzzle

Abstract

This paper introduces a new heuristic function with high efficiency for an optimum solving of the 8-puzzle, this one being the double of the Chebyshev distance. The comparative study is realized among this new heuristic (Chebyshev heuristic), the Hamming heuristic and the Manhattan heuristic using A* algorithm implemented in Java. The Chebyshev heuristic function is more informed than Hamming and Manhattan heuristics. This paper also presents the necessary stages in object oriented development of an interactive software dedicated to simulate the A* search algorithm for 8-puzzle. The modeling of the software is achieved through specific UML diagrams representing the phases of analysis, design and implementation, the system thus being described in a clear and practical manner. In order to confirm the obtained theoretical results which show that Chebyshev heuristic is more efficient, two performance criteria were used: space complexity and time complexity. The space complexity was measured by the number of generated nodes from the search tree, by the number of the expanded nodes and by the effective branching factor. The time complexity was measured by the running time. From the experimental results obtained by using the Chebyshev heuristic, improvements were observed regarding space and time complexity of A* algorithm versus Hamming and Manhattan heuristics.