Ch.7 Backtracking

In order to apply the backtrack method, the desired solution must be expressible as an n-tuple or solution vector <x1, x2, . . ., xn> where the x's are chosen from some finite set Si

Often the problem must meet some feasibility constraints that maximizes or minimizes some criterion function or optimizing function.

solution space = set of all feasible solutions.

suppose solution space is finite. Consider Brute force

  1. enumerate entire solution space (large permutation space)
  2. compute optimizing function
  3. pick optimum solution vector
Instead, with backtracking we can yield a solution with far fewer trials. Build up a solution one component at a time and use modified criteria to test whether the vector being formed has any chance for success. (Prunes the space.)

Example: Constraint Satisfaction and Dependency-Directed Backtracking

Let us suppose that a CSUC student needs to plan her after school activities for each day of a week.

The choices are constrained by weekly objectives: there must be (at least)

In addition, let us assume:

  1. Mon, Tue, Wed, and Thurs are study days. She can study 0, 2, or 4 hours, each hour being one unit.
  2. Fri is entertainment day. She can watch TV (2 units), dine out (5 units), go to a party (5 units), or do nothing (0 units)
  3. Saturday is exercise and entertainment day. Entertainment choices are as on Friday. For exercise, she can go for a walk (1 unit), jog (2 units), go to the gym (3 units) or do nothing (0 units)
  4. Sunday is study and exercise day. Exercise choices are as on Sat. Study choices are as on Monday through Thursday.

Let us consider the following plan:

Note that for simplicity, Saturday and Sunday are divided into Sat1, Sat2 and Sun1,Sun2

Simple back-track

Backtacking (in general) is failure handling

Suppose the student reaches node 10, and realizes that the study constraint has not been satisfied. So, she backtracks to 9 and makes a different choice. After node 9 is exhausted, she backtracks to node 8 and moves from there, ... and so on.

You can see that she is not going to succeed until she backtracks to node 5 and makes the choice of 4 study units. But before she reaches 5, she would have to try different choices at nodes 9, 8, 7, and 6 ; and thereby waste a lot of effort.

A different way of backtracking makes use of the fact that satisfaction of the constraint of studying for 20 hours depends on the choices made at some of the nodes but not at others.

This is called dependency-directed backtracking.

Here, some knowledge may be stored at each node indicating whether the node is relevant to the satisfaction of a given constraint. Then the student, after trying node 10, tries only node 5 and thus avoids any wasted effort at nodes 6, 7, 8 and 9.

The General Idea: Using state-space search trees

First, note that the book differentiates constraints into explicit and implicit.
  1. Explicit constraints are the rules that restrict each xi to take on values only from a given set. This concerns mostly the representation of the problem and valid choices therein - I would say this is defining the state space representation. Sometimes also called feasibility constraints.
  2. All tuples that satisfy the explicit constraints define a possible solution space (book says this - I find it vague as to what is the solution space)
  3. Implicit constraints determine which of the n-tuples in the space actually satisify the criterion function. (This is what I would call the solution space - it seems like the book uses "solution" as the generation of possible solutions...I use solution as the answer.) It is the implicit constraints that specify a satisfactory answer for a particular problem.
 Often solution of a problem is determined by generating a tree.

Each node in tree is a problem state

All paths from the root to other nodes define the state space of the problem

solution states: those problem states s for which the path from the root to s defines a tuple in the solution space. (In some trees it is an entire path, in others it is the leaves in the tree which correspond to solutions) (Again, terminology differs so beware - which constraints do they intend here?)

Answer states: leaf nodes which correspond to an element in the set of solutions. (i.e., satisfies the implicit constraints)

E - node - node being expanded

dead node - expanded completely or not to be expanded any further

All-in-all these definitions will not matter - it is the higher idea that matters.

I will cover a couple of examples of the text (0/1 knapsack, 8 queens) and also discuss this technique through Artificial Intelligence eyes. Notes from others cover the Graph/Map coloring problem as seen in the text. Cliques and Hamiltonian graphs we will get to soon.

Example: 0/1 knapsack

xi = {0/1} - feasibility constraint


Enumerate solution space using n-bit counter.

Use feasibility constraints to prune search tree.

xiwi < M - knapsack capacity

suppose w1 + w2 > M ; w1 + w3 > M


General technique: Decrease solution space using feasibility constraints and criterion function.

Typically, counter approach and search same in worst case

However we can improve (sometimes optimize) the search function by pruning the search tree

General knapsack (when using simply greedy method) looks like:

alternate path in search tree will not yield profit > Pm (current maximum)
do not expand search tree in that direction

Generate and test

Artificial Intelligence

AI notes on the topic (search trees, branch and bound, etc - some Ch. 8 concepts)

Another basic backtrack example: n - Queens problem

board : n x n (Use Example 7.5 of text: 4 X 4 or 4-Queens)

no two queens attack.

First a solution:

  1    
      2
3      
    4  

Then a problem:
1      
      2
  3    
. . . .

No two queens on same row, column or diagonal (not just the diagnonal diagonal)

Representation: ith queen in ith row     :     xi= column of ith queen

Figure 7.2 of text shows the entire state-space tree (permutation tree) possible. Using backtracking, we will reduce this search space and hopefully generate trees more like this:

Basic reasoning straighforward. What is it :-)

Figure 7.5 and 7.6 of text make the idea quite clear.

Consider Diagonal Attack (computational heuristic)

(R, Col)       (R, Col)

(i, xi)          (j, xj)

i - xi    =     j - xj (left to right diagonal)

i + xi    =     j + xj (right to left diagonal)

Two queens attack diagonally iff | xi - xj | = | i - j |

Pi = x1, x2, . . .xi

Below is very much pseudo code. See Place(k,i)( Algorithm 7.4) and NQueens(k,n) ( 7.5) for more detail (different). Also, see Algorithms 7.1 and 7.2 for general recursive and iterative backtracking algorithms 

Expand (i, Pi)

	// generate children of node Pi //
	j = i + 1 ; 
	found = "false";
	for all xj  {1,2, . . ., n}

	case
	: xj = xk for some 1 < k < i :
	
		next	xj

	: | xj - xk | = | j-k | for some 1 < k < i :

		next xj

	: else :
		Pj = Pi || xj  // concatenate
		ADDQ (Pj)
		found =	"true"
	endcase
        return (found)
end	EXPAND

Time for backtrack

time to generate next node

total number of nodes generated

edges with distinct labels

O(n!) nodes in worst case

Average case.

Choose a random path from root to leaf

Use number of children of node at level i on path as average for all nodes at that level

Assumes that probability of node at level i having k children is same for all nodes at level i

mi = no. of children of node at level i on random path

total no. of nodes = 1 + m1 + m1 m2 + m1 m2 m3 + . . . + m1 m2m3...mn

Estimate

The book (page 355) shows a nice "Estimate" to determine the number of nodes that will be generated. The numbers are cool - even if you do not really understand how they got them.

The book also provides nice coverage of the Sum of Subsets, Graph Coloring, Hamiltonian Cycles and Knapsack Problems using backtracking.

Also remember the notes on the web from George Washington University, where he has both more on backtracking and branch and bound