PostHeaderIcon Complexity In Heuristic Search

Heuristic Search: Complexity Of Finding Optimal Solutions

The time complexity of a heuristic search algorithm depends on the accuracy of the heuristic function. For example, if the heuristic evaluation function is an exact estimator, then A* runs in linear time, expanding only those nodes on an optimal solution path. Conversely, with a heuristic that returns zero everywhere, A* becomes uniform-cost search which has exponential complexity.

In general, the time complexity of A* and IDA* is an exponential function of the error in the heuristic function. For example, if the heuristic has constant absolute error, meaning that it never underestimates by more than a constant amount regardless of the magnitude of the estimate, then the running time of A* linear with respect to the solution cost. A more realistic assumption is constant relative error, which means that the error is a fixed percentage of the quantity being estimated. In that case, the running times of A* and IDA* are exponential. The base of the exponent, however, is smaller than the brute-force branching factor, reducing the asymptomatic complexity and allowing larger problems to be solved. For example, using appropriate admissible heuristic functions, IDA* can optimally solve random instance of the twenty-four puzzle and Rubik’s cube.