Posts Tagged ‘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.
Recursive Best First Search
IDA* search is no longer a best-first search since the total cost of a child can beless than that of its parent, and thus nodes are not necessarily expanded in best-first order. Recursive Best-First Search (RBFS) is an alternative algorithm. Recursive best-first search is a best-first search that runs in space that is linear with respect to the maximum search depth, regardless of the cost funtion used. Even with an admissible cost function, Recursive Best-First Search generates fewer nodes than IDA*, and is generally superior to IDA*, except for a small increase in the cost per node generation.
It works by maintaining on the recursion stack the complete path to the current node being expanded as well as all immediate siblings of nodes on that path, along with the cost of the best node in the sub-tree explored below each sibling. Whenever the cost of the current node exceeds that of some other node in the previously expanded portion of the tree, the algorithm backs up to their deepest common ancestor, and continues the search down the new path. In effect, the algorithm maintains a separate threshold for each sub-tree diverging from the current search path.
Heuristic Path Search Algorithm
Since the complexity of finding optimal solutions to these problems is generally exponential in practice, in order to solve significantly larger problems, the optimality requirement must be released. An early approach to this problem was the heuristic path algorithm (HPA).
Heuristic path algorithm is a best-first search algorithm, where the figure of merit of node n is f(n) = (1-w)*g(n)+w*h(n). Varying w produces a range of algorithms from uniform-cost search (w=0) through A* (w=1/2) to pure heuristic search (w=1). Increasing w beyond ½ generally decreases the amount of computation while increasing the cost of the solution generated. The trade off is often quite favorable, with small increases in solution cost yielding huge savings in computation. Moreover, it shows that the solutions found by this algorithm are guaranteed to be no more than a factor of w/(1-w) greater than optimal, but often are significantly better.
Depth-First Branch-And-Bound Search
For many problems, the maximum search depth is known in advance or the search is finite. For example, consider the traveling salesman problem (TSP) of visiting each of the given set of cities and returning to the starting city in a tour of shortest total distance. The most natural problem space for this problem consists of a tree where the root node represents the starting city, the nodes at level one represent all the cities that could be visited first, the nodes at level two represent all the cities that could be visited second, etc. In this tree, the maximum depth is the number of cities, and all candidate solution occurs at this depth. In such a space, a simple depth-first search gurantees finding an optional solution using space that is only linear with repsect to the number of cities.
The idea of depth-first branch-and-bound (DFBnB) Search is to make this search more efficient by keeping track of the lowest-cost solution found so far. Since the cost of a partial tour is the sum of the costs of the edges traveled so far, whenever a partial tour is found whose cost equals or exceeds the cost of the best complete tour found so far, the branch representing the partial tour can be pruned, since all its descendents must have equal or greater cost. Whenever a low-cost complete tour is found, the cost of the best tour is updated to this low cost. In addition, an admissible heuristic function such as the cost of the minimum spanning tree of the remaining unvisited cities, can be added to the cost so far of a partial tour to increase the amount of prunin. Finally, by carefully ordering the children of a given node from smallest to largest estimated total cost, a lower-cost solution can be
found more quickly, further improving the pruning efficiency.
Interestingly, IDA* and DFBnB exhibit complementary behavior. Both are guaranteed to return an optimal solution cost, and increase in each iteration until it reaches the optimal cost. In DFBnB, the cost of the best solution found so far is always an upper bound on the optimal solution cost and decreases until it reaches the optimal cost.
While IDA* never expands any nodes whose cost exceeds the optimal cost, its overhead cosists of expanding some nodes more than once. While DFBnB never expands any node more than once its overhead consists of expanding some nodes whose cost exceed the optimal cost. For problems whose search trees are of bounded depth, or for which it is easy to construct a good solution such as the TSP, DFBnB is usually the algorithm of choice for finding an optimal solution. For problems with infinite search trees or for which it is difficult to construct a low-cost solution, such as the sliding-tile puzzles or Rubik’s Cube, IDA* is usually the best choice.
NEXT: Heuristic Path
Iterative Deepening A* (IDA*) Search
Just as iterative deepening solved the space problem of breadth-first search, iterative deepening A* (IDA*) eliminates the memory constraints of A* search algorithm without sacrificing solution optimality. Each iteration of the algorithm is a depth-first search that keeps track of the cost, f(n) = g(n) + h(n), of each node generated. As soon as a node is generated whose cost exceeds a threshold for that iteration, its path is cut off, and the search backtracks before continuing. The cost threshold is initialized to the heuristic estimate of the initial state, and in each successive iteration is increased to the total cost of the lowest-cost node that was pruned during the previous iteration. The algorithm terminates when a goal state is reached whose total cost does not exceed the current threshold.
Since Iterative Deepening A* performs a series of depth-first searches, its memory requirement is linear with respect to the maximum search depth. In addition, if the heuristic function is admissible, IDA* finds an optimal solution. Finally, by an argument similar to that presented for DFID, IDA* expands the same number of nodes, asymptotically, as A* on a tree, provided that the number of nodes, asymptotically, as A* on a tree, provided that the number of nodes grows exponentially with solution cost. These costs, together with the optimality of A*, imply that IDA* is asymptotically optimal in time and space over all heuristic search algorithms that find optimal solutions on a tree. Additional benefits of IDA* are that it is much easier to implement, and often runs faster than A*, since it does not incur the overhead of managing the open and closed lists.