PostHeaderIcon Depth First Branch And Bound

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