Search Algorithms Under Different Kinds of Heuristics—A Comparative Study
Amitava Bagchi, Ambuj Mahanti · Journal of the ACM · 1983
Three heuristic search algorithms, called Algorithms A, B, and C, are presented.Their performance, with the admlssib/hty condition relaxed, is compared using the following two criteria: (i) number of node expansions and (u) cost of solutmn found.First, a general comparison is made.In this process some variations and extensions of C are also considered.Subsequently, two types of heuristic estimates, called proper and path dependent, are defined, and the algorithms are reexamined.It is shown that on the whole A (Nilsson's algorithm) and B (Martelli's algorithm) are inferior to C, which is a slightly modified version of B.