Worst-Case Solution Quality Analysis When Not Re-Expanding Nodes in Best-First Search


  • Richard Valenzano University of Alberta
  • Nathan Sturtevant University of Denver
  • Jonathan Schaeffer University of Alberta




Heuristic search, inconsistent heuristic, node re-expansions, best-first search, inadmissible heuristic, not re-expanding


The use of inconsistent heuristics with A* can result in increased runtime due to the need to re-expand nodes. Poor performance can also be seen with Weighted A* if nodes are re-expanded. While the negative impact of re-expansions can often be minimized by setting these algorithms to never expand nodes more than once, the result can be a lower solution quality. In this paper, we formally show that the loss in solution quality can be bounded based on the amount of inconsistency along optimal solution paths. This bound holds regardless of whether the heuristic is admissible or inadmissible, though if the heuristic is admissible the bound can be used to show that not re-expanding nodes can have at most a quadratic impact on the quality of solutions found when using A*. We then show that the bound is tight by describing a process for the construction of graphs for which a best-first search that does not re-expand nodes will find solutions whose quality is arbitrarily close to that given by the bound. Finally, we will use the bound to extend a known result regarding the solution quality of WA* when weighting a consistent heuristic, so that it also applies to other types of heuristic weighting.




How to Cite

Valenzano, R., Sturtevant, N., & Schaeffer, J. (2014). Worst-Case Solution Quality Analysis When Not Re-Expanding Nodes in Best-First Search. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8850



AAAI Technical Track: Heuristic Search and Optimization