Analysis of Heuristic Search Models

Thomas Sudkamp; Robert Shanahan

doi:10.1145/322917.322919

Analysis of Heuristic Search Models

Thomas Sudkamp, Robert Shanahan

Wright State University

Research output: Contribution to journal › Article › peer-review

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.

Original language	American English
Journal	Proceeding CSC '87 Proceedings of the 15th annual conference on Computer Science
DOIs	https://doi.org/10.1145/322917.322919
State	Published - Jan 1 1987

Disciplines

Computer Sciences
Engineering
Mathematics
Physical Sciences and Mathematics

Access to Document

10.1145/322917.322919License: Unspecified

http://dx.doi.org/10.1145/322917.322919

Cite this

@article{3a636f38a13b4e42a50d918edf40edad,

title = "Analysis of Heuristic Search Models",

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.",

author = "Thomas Sudkamp and Robert Shanahan",

year = "1987",

month = jan,

day = "1",

doi = "10.1145/322917.322919",

language = "American English",

journal = "Proceeding CSC '87 Proceedings of the 15th annual conference on Computer Science",

}

TY - JOUR

T1 - Analysis of Heuristic Search Models

AU - Sudkamp, Thomas

AU - Shanahan, Robert

PY - 1987/1/1

Y1 - 1987/1/1

N2 - 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.

AB - 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.

UR - https://corescholar.libraries.wright.edu/cse/459

UR - http://dx.doi.org/10.1145/322917.322919

U2 - 10.1145/322917.322919

DO - 10.1145/322917.322919

M3 - Article

JO - Proceeding CSC '87 Proceedings of the 15th annual conference on Computer Science

JF - Proceeding CSC '87 Proceedings of the 15th annual conference on Computer Science

ER -

Analysis of Heuristic Search Models

Abstract

Disciplines

Access to Document

Other files and links

Cite this