next up previous index CD Book Algorithms
Next: Lecture 12 - introduction Up: No Title Previous: Lecture 10 - tree

Lecture 11 - backtracking

Parallel Bubblesort

In order for me to give back your midterms, please form a line and sort yourselves in alphabetical order, from A to Z.  

There is traditionally a strong correlation between the midterm grades and the number of daily problems attempted:

daily: 0, sum: 134, count: 3, avg: 44.67

daily: 1, sum: 0, count: 2, avg: 0.00

daily: 2, sum: 63, count: 1, avg: 63.00

daily: 3, sum: 194, count: 3, avg: 64.67

daily: 4, sum: 335, count: 5, avg: 67.00

daily: 5, sum: 489, count: 8, avg: 61.12

daily: 6, sum: 381, count: 6, avg: 63.50

daily: 7, sum: 432, count: 6, avg: 72.00

daily: 8, sum: 217, count: 3, avg: 72.33

daily: 9, sum: 293, count: 4, avg: 73.25

Listen To Part 11-2

Combinatorial Search

We have seen how clever algorithms can reduce sorting from tex2html_wrap_inline14741 to tex2html_wrap_inline14743 . However, the stakes are even higher for combinatorially explosive problems:  

The Traveling Salesman Problem

Given a weighted graph, find the shortest cycle which visits each vertex once.  

Applications include minimizing plotter movement, printed-circuit board wiring, transportation problems, etc.

There is no known polynomial time algorithm (ie. tex2html_wrap_inline14745 for some fixed k) for this problem, so search-based algorithms are the only way to go if you need an optional solution.

Listen To Part 11-3

But I want to use a Supercomputer

Moving to a faster computer can only buy you a relatively small improvement:  

Listen To Part 11-4

Can Eight Pieces Cover a Chess Board?

Consider the 8 main pieces in chess (king, queen, two rooks, two bishops, two knights). Can they be positioned on a chessboard so every square is threatened?  

Only 63 square are threatened in this configuration. Since 1849, no one had been able to find an arrangement with bishops on different colors to cover all squares.

Of course, this is not an important problem, but we will use it as an example of how to attack a combinatorial search problem.

Listen To Part 11-5

How many positions to test?

Picking a square for each piece gives us the bound:


Anything much larger than tex2html_wrap_inline14759 is unreasonable to search on a modest computer in a modest amount of time.  

However, we can exploit symmetry to save work. With reflections along horizontal, vertical, and diagonal axis, the queen can go in only 10 non-equivallent positions.

Even better, we can restrict the white bishop to 16 spots and the queen to 16, while being certain that we get all distinct configurations.



Listen To Part 11-6


Backtracking is a systematic way to go through all the possible configurations of a search space.  

In the general case, we assume our solution is a vector tex2html_wrap_inline14761 where each element tex2html_wrap_inline14763 is selected from a finite ordered set tex2html_wrap_inline14765 ,

We build from a partial solution of length k tex2html_wrap_inline14767 and try to extend it by adding another element. After extending it, we will test whether what we have so far is still possible as a partial solution.

If it is still a candidate solution, great. If not, we delete tex2html_wrap_inline14769 and try the next element from tex2html_wrap_inline14771 :

Compute tex2html_wrap_inline14773 , the set of candidate first elements of v.

k = 1

While k > 0 do

While tex2html_wrap_inline14779 do (*advance*)

tex2html_wrap_inline14781 = an element in tex2html_wrap_inline14783


if ( tex2html_wrap_inline14787 ) is solution, print!

k = k + 1

compute tex2html_wrap_inline14791 , the candidate kth elements given v.

k = k - 1 (*backtrack*)

Listen To Part 11-7

Recursive Backtracking

Recursion can be used for elegant and easy implementation of backtracking.  

Backtrack(a, k)

if a is a solution, print(a)

else {

k = k +1

compute tex2html_wrap_inline14797

while tex2html_wrap_inline14799 do

tex2html_wrap_inline14801 = an element in tex2html_wrap_inline14803

tex2html_wrap_inline14805 = tex2html_wrap_inline14807

Backtrack(a, k)


Backtracking can easily be used to iterate through all subsets or permutations of a set.

Backtracking ensures correctness by enumerating all possibilities.

For backtracking to be efficient, we must prune the search space.

Listen To Part 11-8

Constructing all Subsets

How many subsets are there of an n-element set?  

To construct all tex2html_wrap_inline14809 subsets, set up an array/vector of n cells, where the value of tex2html_wrap_inline14811 is either true or false, signifying whether the ith item is or is not in the subset.

To use the notation of the general backtrack algorithm, tex2html_wrap_inline14813 , and v is a solution whenever tex2html_wrap_inline14815 .

What order will this generate the subsets of tex2html_wrap_inline14817 ?







Listen To Part 11-9

Constructing all Permutations

How many permutations are there of an n-element set?  

To construct all n! permutations, set up an array/vector of n cells, where the value of tex2html_wrap_inline14821 is an integer from 1 to n which has not appeared thus far in the vector, corresponding to the ith element of the permutation.

To use the notation of the general backtrack algorithm, tex2html_wrap_inline14823 , and v is a solution whenever tex2html_wrap_inline14825 .


The n-Queens Problem

The first use of pruning to deal with the combinatorial explosion was by the king who rewarded the fellow who discovered chess!  

In the eight Queens, we prune whenever one queen threatens another. Listen To Part 11-11

Covering the Chess Board

In covering the chess board, we prune whenever we find there is a square which we cannot cover given the initial configuration!

Specifically, each piece can threaten a certain maximum number of squares (queen 27, king 8, rook 14, etc.) Whenever the number of unthreated squares exceeds the sum of the maximum number of coverage remaining in unplaced squares, we can prune.

As implemented by a graduate student project, this backtrack search eliminates tex2html_wrap_inline14827 of the search space, when the pieces are ordered by decreasing mobility.

With precomputing the list of possible moves, this program could search 1,000 positions per second. But this is too slow!


Although we might further speed the program by an order of magnitude, we need to prune more nodes!

By using a more clever algorithm, we eventually were able to prove no solution existed, in less than one day's worth of computing.

You too can fight the combinatorial explosion!

Listen To Part 11-12

The Backtracking Contest: Bandwidth

The bandwidth problem takes as input a graph G, with n vertices and m edges (ie. pairs of vertices). The goal is to find a permutation of the vertices on the line which minimizes the maximum length of any edge.    

tex2html_wrap14839 tex2html_wrap14841
The bandwidth problem has a variety of applications, including circuit layout, linear algebra, and optimizing memory usage in hypertext documents.

The problem is NP-complete, meaning that it is exceedingly unlikely that you will be able to find an algorithm with polynomial worst-case running time. It remains NP-complete even for restricted classes of trees.

Since the goal of the problem is to find a permutation, a backtracking program which iterates through all the n! possible permutations and computes the length of the longest edge for each gives an easy tex2html_wrap_inline14831 algorithm. But the goal of this assignment is to find as practically good an algorithm as possible.

Listen To Part 12-4

Rules of the Game

  1. Everyone must do this assignment separately. Just this once, you are not allowed to work with your partner. The idea is to think about the problem from scratch.
  2. If you do not completely understand what the bandwidth of a graph is, you don't have the slightest chance of producing a working program. Don't be afraid to ask for a clarification or explanation!!!!!
  3. There will be a variety of different data files of different sizes. Test on the smaller files first. Do not be afraid to create your own test files to help debug your program.
  4. The data files are available via the course WWW page.
  5. You will be graded on how fast and clever your program is, not on style. No credit will be given for incorrect programs.
  6. The programs are to run on the whatever computer you have access to, although it must be vanilla enough that I can run the program on something I have access to.
  7. You are to turn in a listing of your program, along with a brief description of your algorithm and any interesting optimizations, sample runs, and the time it takes on sample data files. Report the largest test file your program could handle in one minute or less of wall clock time.
  8. The top five self-reported times / largest sizes will be collected and tested by me to determine the winner.

Listen To Part 12-5

Producing Efficient Programs

  1. Don't optimize prematurely: Worrying about recursion vs. iteration is counter-productive until you have worked out the best way to prune the tree. That is where the money is.  
  2. Choose your data structures for a reason: What operations will you be doing? Is case of insertion/deletion more crucial than fast retrieval?

    When in doubt, keep it simple, stupid (KISS).

  3. Let the profiler determine where to do final tuning: Your program is probably spending time where you don't expect.

next up previous index CD Book Algorithms
Next: Lecture 12 - introduction Up: No Title Previous: Lecture 10 - tree

Mon Jun 2 09:21:39 EDT 1997