Analysis of Heuristic Search Models

Thomas Sudkamp; Robert Shanahan

doi:10.1145/322917.322919

Analysis of Heuristic Search Models

Thomas Sudkamp, Robert Shanahan

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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	English
Title of host publication	Proceedings of the 15th Annual Conference on Computer Science, CSC 1987
Publisher	Association for Computing Machinery, Inc
Pages	7-15
Number of pages	9
ISBN (Electronic)	0897912187, 9780897912181
DOIs	https://doi.org/10.1145/322917.322919
State	Published - Feb 1 1987
Event	15th Annual Conference on Computer Science - St. Louis, United States Duration: Feb 16 1987 → Feb 19 1987 Conference number: 15

Conference

Conference	15th Annual Conference on Computer Science
Abbreviated title	CSC 1987
Country/Territory	United States
City	St. Louis
Period	2/16/87 → 2/19/87

ASJC Scopus Subject Areas

General Computer Science

Keywords

Automated reasoning
Heuristic search

Disciplines

Computer Sciences
Engineering
Mathematics

Access to Document

10.1145/322917.322919License: Unspecified

Cite this

@inproceedings{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.",

keywords = "Automated reasoning, Heuristic search",

author = "Thomas Sudkamp and Robert Shanahan",

note = "Publisher Copyright: {\textcopyright} 1987 ACM.; 15th Annual Conference on Computer Science ; Conference date: 16-02-1987 Through 19-02-1987",

year = "1987",

month = feb,

day = "1",

doi = "10.1145/322917.322919",

language = "English",

pages = "7--15",

booktitle = "Proceedings of the 15th Annual Conference on Computer Science, CSC 1987",

publisher = "Association for Computing Machinery, Inc",

}

TY - GEN

T1 - Analysis of Heuristic Search Models

AU - Sudkamp, Thomas

AU - Shanahan, Robert

N1 - Conference code: 15

PY - 1987/2/1

Y1 - 1987/2/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.

KW - Automated reasoning

KW - Heuristic search

UR - http://www.scopus.com/inward/record.url?scp=85044234498&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85044234498&partnerID=8YFLogxK

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

U2 - 10.1145/322917.322919

DO - 10.1145/322917.322919

M3 - Conference contribution

SP - 7

EP - 15

BT - Proceedings of the 15th Annual Conference on Computer Science, CSC 1987

PB - Association for Computing Machinery, Inc

T2 - 15th Annual Conference on Computer Science

Y2 - 16 February 1987 through 19 February 1987

ER -

Analysis of Heuristic Search Models

Abstract

Conference

ASJC Scopus Subject Areas

Keywords

Disciplines

Access to Document

Other files and links

Cite this