This paper compares the performance of five heuristic search algorithms, related to the now classical A* algorithm introduced by Nilsson [1]. The five algorithms are classified into three “approaches.” The first approach is the classical one; i.e., the node in the search graph which is selected for expansion is the one for which the cost function has a minimum value. The algorithms representing this approach are (1) A* (as modified by Martelli), and (2) an alternative to A*, also proposed by Nilsson, in which a node that has been expanded is not expanded again; instead, as in Nilsson’s GRAPHSEARCH heuristic search algorithm for networks, when a little path to a previously expanded node is found, values are “propagated” to its currently know successors. These two algorithms are termed A and PropA by the authors.

The second approach is likewise illustrated by two algorithms. Algorithm C was introduced by the authors in 1983. It differs from A in that a new variable F is introduced. Nodes are selected for expansion when fˆ ≤, where fˆ(n) is an estimate of the cost of a minimum cost path from the start node to a goal node when the path is constrained to go through node n. The detailed additional step in the algorithm, which involves replacement of F by fˆ(n) under appropriate conditions, is discussed in detailed by the authors in the first reference of the paper [2]. In [2], they show that when search heuristics do not satisfy the admissibility requirement, Algorithm C nearly always outperforms A, as measured by the number of node expansions and the cost of solution found by it. The fourth algorithm, termed PropC, modifies C by adding the propagation property in an analogous way to the difference between Algorithm A and PropA.

Finally, an algorithm introduced by Martelli and Montanari [3] for AND/OR graphs is adapted to networks and termed MarkA. The name derives from the fact that this is an arc-marking algorithm. Following expansion of each node, one outgoing arc is marked. Cost comparisons are then made as one moves up the marked path, altering the marking if necessary.

The paper presents a number of results concerning the performance of each of these algorithms. The algorithms differ in their success rate primarily under conditions when the heuristic cost estimate functions are inadmissible, i.e., when for at least one node in the graph, hˆ(n)>h(n) where h(n) is the cost associated with the least path cost from node n to the goal, and where hˆ(n) is the heuristic estimate of that cost. The performance of the five algorithms is measured by (1) the cost of the solution they find, and (2) the time of execution and storage requirements in the worst case, as measured by the number of node expansions with A and C, the number of nodes selected by PropA and PropC, and the number of arc markings for MarkA. The paper concludes with recommendations on the choice of algorithm under various conditions. When the heuristic is admissible, it is indicated that all five algorithms find the minimal cost solution. However, if the network has loops, MarkA cannot be used, and, in terms of execution times, the recommended method is PropA. When the heuristic is admissible and there are no loops in the graph, MarkA is recommended since it makes at most O(N 0S2) arc markings (where N is the number of nodes in the graph). When the heuristic is inadmissible, the authors recommend their own algorithm (D), since it yields solutions as good or better than A, PropA, or MarkA and runs faster than PropC.

Clearly, the book is not closed in the study of search algorithms since an infinite number of variations are possible. However, papers such as the present one emphasize the importance of Nilsson’s contribution [1].