Next: Bandwidth Minimization Up: Combinatorial Search and Heuristic Previous: Constructing All Paths in

# Search Pruning

Backtracking ensures correctness by enumerating all possibilities. For example, a correct algorithm to find the optimal traveling salesman tour could enumerate all n! permutations of n vertices of the graph and selecting the best one. For each permutation, we could check whether each of the n edges implied in the tour really exists in the graph G, and if so, sum the weights of these edges together.

For most graphs, however, it would be pointless to construct all the permutations first and then analyze them later. Suppose we started our search from vertex , and it happened that edge was not in G. Enumerating all the (n-2)! permutations beginning with would be a complete waste of effort. Much better would be to prune the search after and continue next with . By carefully restricting the set of next elements to reflect only the moves that are legal from the current partial configuration, we reduce the search complexity significantly.

Pruning is the technique of cutting off search the instant we have established that this partial solution cannot be extended into the solution that we want. For example, in our traveling salesman search program, we seek the cheapest tour that visits all vertices before returning to its starting position. Suppose that in the course of our search we find a tour t whose cost is . As the search continues, perhaps we will find a partial solution , where k < n and the sum of the edges on this partial tour is . Can there be any reason to continue exploring this node any further? No, assuming all edges have positive cost, because any tour with the prefix will have cost greater than tour t, and hence is doomed to be non-optimal. Cutting away such failed partial tours as soon as possible can have an enormous impact on running time.

Exploiting symmetry is a third avenue for reducing combinatorial search. It is clearly wasteful to evaluate the same candidate solution more than once, because we will get the exact same answer each time we consider it. Pruning away partial solutions identical to those previously considered requires recognizing underlying symmetries in the search space. For example, consider the state of our search for an optimal TSP tour after we have tried all partial positions beginning with . Can it pay to continue the search with partial solutions beginning with ? No. Any tour starting and ending at can be viewed as starting and ending at or any other vertex, for these tours are cycles. There are thus only (n-1)! distinct tours on n vertices, not n!. By restricting the first element of the tour to always be , we save a factor of n in time without missing any interesting solutions. Detecting such symmetries can be subtle, but once identified they can usually be easily exploited by a search program.

Next: Bandwidth Minimization Up: Combinatorial Search and Heuristic Previous: Constructing All Paths in

Algorithms
Mon Jun 2 23:33:50 EDT 1997