Comparative Analysis of Four Heuristic Functions that Optimizes the A* Search Algorithm
Advances in Mathematics and Computer Science Vol. 2,
Page 23-35
Abstract
In this chapter are compared four heuristic functions with high efficiency for an optimum solving of 8-puzzle. The analysis is realized among Chebyshev distance, Hamming distance and Manhattan distance using A* search algorithm implemented in Java. The two heuristic functions defined using Chebyshev distance are more informed than Hamming and Manhattan heuristics. This chapter also presents necessary stages in object oriented development of an interactive software dedicated to simulate the A* search algorithm for 8-puzzle. The modelling of software is achieved through specific UML diagrams representing phases of analysis, design and implementation, the system thus being described in a clear and practical manner. In order to confirm that second Chebyshev heuristic is more efficient was used space complexity performance criteria. The space complexity was measured by number of generated nodes from search tree, by number of expanded nodes and by effective branching factor. From experimental results obtained by using second Chebyshev heuristic, improvements were observed regarding space complexity of A* algorithm versus Hamming, Manhattan and first Chebyshev heuristics. Analysing the results presented in graphics, it can be asserted that number of steps made for obtaining the solution is the same for similar configurations, determining the optimal solutions for all four examined heuristics. But, investigating generated nodes number in the search tree associated with the A* algorithm using second Chebyshev heuristic, it can be observed that this number is strictly less than number obtain by using other three heuristics. Calculating approximately effective branching factor for all four heuristics, there were obtained values illustrated in figures. The values of b* appropriate to function hC2 are more appropriate to value 1 than values of b* appropriate to functions hM, hH, and hC1, so the A* algorithm using hC2 heuristic drives to an optimal solution in a way that appears to be linear. According to these experimental values, results the superiority of second Chebyshev heuristic from Manhattan, Hamming and first Chebyshev heuristics. In this case we can say that hC2 heuristic dominates hM, hH, and hC1 heuristics, from space complexity point of view.
Keywords:
- Heuristics function
- Hamming distance
- Manhattan distance
- Chebyshev distance
- optimal solution
How to Cite
- Abstract View: 0 times