Analysis of heurisitc search models
Thomas A. Sudkamp, Robert Shanahan · 1987
A model containing multiple optimal solutions and nonoptimal solutions is constructed to study the performance of A* heuristic search algorithm. To obtain estimates of the average performance of the algorithm, a domain independent A* search space is constructed treating the heuristic function, branching factor and number of successful children of a node as random variables. These results are compared to the worst case performance of the models developed by Pohl and Gaschnig. The parameters of the model are defined to simulate the 15 puzzle search space. The results of the 15 puzzle searches are compared with the simulation to determine the effects of the assumptions on the structure of the graph and the heuristic functions.