Some Remarks on Heuristic Search Algorithms
Proceedings of the Seventh International Joint Conference on Artificial Intelligence. Search. Pages 572-573.
© 1981 International Joint Conferences on Artificial Intelligence
Abstract
In this communication the terminology an~ the notations of the paper of Martelli (lj are used throughout. A similar treatment is given in the book of Nilsson [2]. Familiarity with at least one of these works is assumed to read this paper.
- A.Martelli: On the complexity of ad- missible search algorithms. Artifi- cial Intelligence 8 /1977/, 1-13
- N.J.Nilsson: Principles of Artifi- cial Intelligence. TIOGA Publishing Company, Palo Alto, California, 1980
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. An improved version of Martelli's algo rithm B
Martelli in his algoRithm ~ improved the classical algorithm A for finding a minimal cost path in a graph using heuris tic estimates by introducing a global vari able F which gives the greatest f values achieved up to that step by a closed node. F is used to control whether the remaining costs promised by the heuristic estimates are in accordance with the propagation of the algorithm so far. Algorithm ~ uses the heuristic estimates only if they promise to improve the global F value, otherwise it uses only the g-estimates. This way al gorithm B avoids the possible exponential running time of the original algorithm ~ even if the consistency assumption does not hold. Nevertheless, some particularly wrong heuristic estimates can mislead the search of algorithm B, as well. Fig. 1. displays an example of Martelli for which algorithm AM requires 0/2~/ node expansion and algorithm ~ requires only 0/N~/ expan sions.
The improved algorithm, let us call it algorithm B', is based on the observa tion that expanding a node may result in a possibility to improve the heuristic es timate of that node, and perhaps also of i ts son nodes. E.g. in the graph of Fig.l. after expanding node ~l the heuristic es-
timate of ~l could have been set 19 in stead of zero still maintaining the upper bound property of the heuristic extimate, but this change would have avoided sever al reopenings of node n 1 performed both by algorithm AM and B. On the other hand, if e.g. the heuristic estimate of ~ 5 /also in the graph of Fig.l./ had been 23 instead of zero, after expanding ~S the heuristic estimate of ~l could have been set 12. This operation would have saved several reopenings, as well.

Algorithm B' is a variant of B and it can be obtained-from ~ by inserting two steps after step /3/ of algorithm B. Thus algorithm ~· looks the following ~ay:
- /1/ Put the start node s on a list called OPEN. Set
- /2/ If OPEN is empty exit with failure; otherwise continue.
- /3/ If there are some nodes in OPEN with r < F I select among them the node n whose g value is smallest; othe~ise, select the node n in OPEN whose t val ue is smallest and set F + 1(n). /Re solve ties arbitrarily, but always in favour of any goal riode./ Remove n from OPEN and put it on a list called CLOSED.
- /3a/ For each son~ of the recently se lected node n if
.... /3b/ Let m be a son of ~ for which h(~) +
+ c(~~~)~ hm(!!_)is minimal. If hm(!!_ph(!!_) A - "" { then seth(!!_) ~ hm ~)
- / 4/ If n is a goal node, exit with the so lution path obtained by tracing back through the pointers; otherwise contin ue.
- /5/ Expand node n, generating all of its successors. /If there are no successors go to /2/. For each successor n . , compute ..., "" -]_ gi · g(!!_) + c(~, !!_J
- /6/ If a successor n. is not already on either OPEN or 1 CLOSED, set g ( n . ) ~ g . and f ( n . ) ~ g 1 . + h ( n . J -]_ ]_ -]_ -]_ Put n . on OPEN and direct a pointer from- 1 it back to n.
- / 7/ If a successor n . Is already on OPEN -]_ I 8 I or CLOSED and if g(n . ) > g. , then up-1. ]_ date it by setting ..... ;"\ " "" "' g(!!_i) · gi and f(!!_i) · gi + h(~i) Put ni on OPEN if it was on CLOSED and redirect ton the pointer from ~i· Go to I 2 I.
For this modified algorithm the following statement holds:
Theorem 1. Algorithm~· is admissible .· This theorem can be proved in a simi lar way as the admissibility of algorithms ~x and ~ is proved in [1) and [2].
2. The complexity of algorithm B'
The complexity of a heuristic search a lgorithm is measured by the number of node e xpansions and not by the number of elemen tary ope rations required to perform the al gorithm. This approach /also taken in [1] and (2] / is motivated by the fact in most of the applications that the most time con suming operation is generating the succes sors of a node /i.e. the node expansion/ and ca l culating their heuristic estimates, al l othe r administrative activities of the search algorithms are of negligible com p lexity.
Theorem 2. For every graph algorithm B' e xpands each node at most as many times as a l gor ithm B, if both algorithms r e solve tie s in the same way .·
This theorem looks very plausible be ca us e in all cases of inconsistencies al gorithm~ improves its heuristic estimates, and in no other cases. However, better heu rist i c e stimates alone do not warrant bet ter performance. If e.g. the heuristic es t imates of the graph in Fig.l. were all ze ro, algorithm B would expand each node on ly once . On the other hand, algorithm B' may change the order of expanded nodes - drast ically compared with algorithm B. In spi t e of the plausibility of Theorem-2., the author could find only a fairly long and sophisticated proof of it.
Theorem 4.1. in [1] can be sharpened the following way, using the same proof technique: Theorem 3. Algorithm B requires at most N 2 /2 + 0/N/ node exp~sions. Fig.l. shows that this statements is sharp .·
The author conjectures that algorithm ~· requires only N~/4 + 0/N/ steps in the worst case, but he was able to prove only the following statement: Theorem 4. Algori~hm B' requires at most N 2 /8 + 0/N/node expan~ions .·
The proof of this theorem is quite straightforward, however fairly lengthy. The main guideline is to show that if a node is expanded k times, then there must be at least k distinct nodes "before" and also "after"-this node.
Fig. 2. displays a graph for which algorithm B' requires N~/8 + 0/N/ node expansions: /It is easy to see, how to ge neralize this graph to haveN nodes./

Let us remark, that if steps /3a/ and /3b/ are inserted to the original algo rithm Ax instead of algorithm B, Theorem 4.-will hold for this algorithm as well, thus this method turns out to be another way to avoid the possible expo nential running time of algorithm Ax.
3. No overall optimal algorithm exists
If the consistency assumption holds, it can be proved that algorithm Ax /and also algorithms~ and~'/ expands the possible least number of nodes, i.e. no algorithm not better informed than AX can expand less number of nodes.
If the complexity of a search algo rithm is measured by the number of dis tinct expanded nodes, this optimality pro perty of Ax will still hold. But in our case the complexity of a search algorithm is measured by the total number of node expansions, and in this case the following theorem can be proved:
Theorem 5. Let M be an algorithm for find ing the minimal-cost path in graphs using the heuristic information attached to the nodes of the graphs. There exists an algo rithms N and a graph G so, that algorithm N also finds the minimal cost path in all graphs and N requires fewer node expan sions than M when applied to G .·
The proof of this theorem consists of a set of consecutive counterexamples re sulting in a graph for which it is proved that at least one of its nodes must be expanded at least twice by an optimal al gorithm. Then an algorithm is constructed which also finds always the minimal cost path but expands each node of this parti cular graph only once.
4. Conclusions
An improved version of Martelli's al gorithm B has been described. This algo rithm can improve its heuristic estimates during its run. The improved algorithm never requires more node expansions than the original algorithm, and its worst case behaviour is also at least twice better. Furthermore, there are cases, when the original algorithm requires 0/N~/ node expansions for an N-node graph, while the improved version requires only 0/N/ ex pansions.
Another result is that if the com plexity of the algorithm is measured by the total number of node expansions, no overall optimal search algorithm exists.
The proofs of the theorems stated in this communication will be given in a forthcoming paper, now in preparation.
@inproceedings{ijcai1981p107,
title = {Some Remarks on Heuristic Search Algorithms},
author = {Méro, László},
booktitle = {Proceedings of the Seventh International Joint Conference on
Artificial Intelligence, {IJCAI-81}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Patrick J. Hayes},
pages = {572--573},
year = {1981},
month = {8},
note = {Search},
url = {https://ijcai.org/proceedings/1981/107},
}
TY - CPAPER TI - Some Remarks on Heuristic Search Algorithms AU - Méro, László T2 - Proceedings of the Seventh International Joint Conference on Artificial Intelligence, IJCAI-81 PB - International Joint Conferences on Artificial Intelligence PY - 1981 SP - 572 EP - 573 UR - https://ijcai.org/proceedings/1981/107 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: