A LINEAR HEURISTIC ALGORITHM FOR GRAPH SEARCH
Zhijun He · Information and Computation · 1988
This paper describes a new heuristic search algorithm with modifiable estimate.This algorithm uses the information gathered by node expansions to improve theheuristic estimate and so it keeps the so called‘consistency assumption’holding on thesearch tree constantly.The new algorithm is admissible and it reduces the worst casecomplexity of search from O(N~2)of algorithm B′(L.Mero,1984)to its O(N).(N isthe size of the searched graph.)In the other part of the paper,a comparison between algorithm B' and the newalgorithm is made.