A: an efficient near admissible heuristic search algorithm
Malik Ghallab, Dennis G. Allard · International Joint Conference on Artificial Intelligence · 1983
The algorithm A* (Nilsson, 1979) presents two significant drawbacks. First, in seeking strict optimal solution paths it necessarily has high order of complexity. Second, the algorithm does not explicitly descriminate between the cost of a solution path and the cost of finding the solution path. To confront these problems we propose the algorithm AE, a generalization of A*. Instead of seeking an optimal solution, it seeks one which is within a factor (1+e) of optimum (e > 0). The basic idea is to avoid doing any search at all on most near optimal partial solutions by sticking to a small number of most fruitful paths. Various strategies for searching for near optimal partial solutions are discussed. Experimental results are presented indicating that A e has average complexity of lower order than A* and compares favorably to the related algorithm Af* (Pearl and Kim, 1982).