Peter E. Hart
Abstract
Our paper on the use of heuristic information in graph searching defined a path-finding algorithm, A*, and proved that it had two important properties. In the notation of the paper, we proved that if the heuristic function ñ (n) is a lower bound on the true minimal cost from node n to a goal node, then A* is <u>admissible;</u> i.e., it would find a minimal cost path if any path to a goal node existed. Further, we proved that if the heuristic function also satisfied something called the <u>consistency assumption,</u> then A* was <u>optimal;</u> i.e., it expanded no more nodes than any other admissible algorithm A no more informed than A*. These results were summarized in a book by one of us.
- [fr1] Nils J. Nilsson, Problem-Solving Methods in Artificial Intelligence, McGraw-Hill Book Co., New York, New York, 1971. Google Scholar
Digital Library
Recommendations
Heuristic Search for the Generalized Minimum Spanning Tree Problem
The generalized minimum spanning tree (GMST) problem occurs in telecommunications network planning, where a network of node clusters needs to be connected via a tree architecture using exactly one node per cluster. The problem is known to be NP-hard, ...
Heuristic solutions for general concave minimum cost network flow problems
We address the single-source uncapacitated minimum cost network flow problem with general concave cost functions. Exact methods to solve this class of problems in their full generality are only able to address small to medium size instances, since this ...
On minimum reload cost paths, tours, and flows
The concept of reload cost, that is of a cost incurred when two consecutive arcs along a path are of different types, naturally arises in a variety of applications related to transportation, telecommunication, and energy networks. Previous work on ...
Comments