Measuring Heuristic Accuracy on the Performance of Search Algorithms in Solving 8-Puzzle Problems

Abstract

The goal of this paper is to examine the effect of heuristic accuracy on the performance of search algorithms in solving 8-puzzle problems. The 8-puzzle is a popular benchmark search problem in Artificial Intelligence, and numerous search strategies have been developed to solve it. This research evaluates the performance of search algorithms using different heuristics to determine the optimal level of heuristic accuracy for solving 8-puzzle problems. Several search algorithms, including uniform cost search and A* search, were implemented and tested using different heuristics. Manhattan and Euclidean distances were chosen as heuristics for A* algorithm. Heuristics play a crucial role in guiding these algorithms towards the solution, and their accuracy can greatly impact the performance of the search. Results revealed that reduction attained in both time and space complexity by A* search with Manhattan heuristic is over 99.1% for the average case, while the reduction in the effective branching factor is over 21.1%. These results from the experiments provide insights into the trade-off between heuristic accuracy and search efficiency, and contribute to a better understanding of the behavior of search algorithms in complex problems