Analysis of Heuristic Search Models
Document Type
Article
Publication Date
1987
Abstract
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.
Repository Citation
Sudkamp, T.,
& Shanahan, R.
(1987). Analysis of Heuristic Search Models. Proceeding CSC '87 Proceedings of the 15th annual conference on Computer Science, 7-15.
https://corescholar.libraries.wright.edu/cse/459
DOI
10.1145/322917.322919
