Smoothed Analysis of Inconsistent A*
The first smoothed analysis of the A* algorithm using inconsistent heuristics is presented, proving that the expected smoothed time complexity of inconsistent A* is bounded by a polynomial, specifically a total iteration number of $O(n^2 m \kappa)$.
Zhiyang Chen, Hai-Long Yao
· 0 citations