Backtracking/Branch-and-Bound Answers

Backtracking

Question 1 - (For the search space above): What is the best case search for a ascending sorted solution? abei, height of search tree, Ω(n). A descending sorted solution? adnp, height of search tree, Ω(n). The worst case? Recall that a complete tree of height h has 2^h+1−1 nodes, the decision tree for sorting n items has height n. Brute force search of the complete space, Θ(2ⁿ⁺¹).

Question 2 - Which node(s) does the algorithm back-up to after printing node k? All the way to node a.

Question 3 - Trace and generate the call tree for the first 4 print executions. Initial call is: preOrderBT( X[] )

 

DFSbtChange( X[1..i], change ) --  pre: X[1..i] specifies first i components of a solution --  post: Solution X[1..i] if change = 0 then print X[1..i] else    for each x ∈ {25, 10, 5, 1} do       if change - x >= 0 then            X[i+1] ← x            DFSbtChange( X[1..i+1], change - x )

Question 4a - Give the first solution found for DFSbtChange( X[1..i], 11 ).

Question 4b - Can a Queen be placed anywhere above in row 3 without conflicting? No

Question 5

Are there any other partial solutions from 6? No, only state 7.

• What is the next partial solution after 8?

  	1	2	3	4
  1			Q
  2
  3
  4

• Continue to find the next solution.

  1 2 3 4 1     Q   2         3         4

  1 2 3 4 1     Q   2 Q       3         4

  1 2 3 4 1     Q   2 Q       3       Q 4

  1 2 3 4 1     Q   2 Q       3       Q 4   Q

Branch-and-bound

Question 6

1. The algorithm generates all n! costs. In what order are the costs generated? Depth first.
2. What stops the recursion (base case)? Line 1 when person d, the last person, has been assigned.
3. What is the purpose of Line 7? Remove an assignment so another can be made.
4. What is the complexity of the algorithm? 

   Obviously the bottom cost is n! since we are generating all permutations so Ω(n!).

The other n-1 levels are:

n+n(n-1)+n(n-1)(n-2)+...+n(n-1)(n-2)*...*3+n(n-1)(n-2)*...*3*2

an n-1 degree polynomial dominated by n^n-1

i.e. the last term is the largest with: n(n-1)(n-2)*...*3*2 = n! < n^n-1

Complexity is: O(n!+n^n-1) = O(n^n-1)

 

The actual number of calls for 4 Jobs/people is: 64

4 + 4(4-1) + 4(4-1)(4-2) + 4! =

4 + 4(3) + 4(3)(2) + 4! =

4 + 12 + 24 + 24 = 64

O(n^n-1) estimate is 4^4-1 = 64

 

The actual number of calls for 5 Jobs/people is: 325

5 + 5(5-1) + 5(5-1)(5-2) + 5(5-1)(5-2)(5-3) + 5! =

5 + 5(4) + 5(4)(3) + 5(4)(3)(2) + 5! =

5 + 20 + 60 + 120 + 120 = 325

O(n^n-1) estimate is 5^5-1 = 625

Not a very tight upper-bound.

Determining a tight upper-bound requires finding a closed form representation of the summation of the recursion tree calls defined by:

There is an on-line encyclopedia of integer sequences, that can be searched by providing it with a few terms of a sequence.   For example, we can search 1, 4, 15, 64, 325 (terms 1 through 5 of the sequence).   This produces:

http://www.research.att.com/~njas/sequences/A007526
 

According to this, the sequence is the number of permutations of non-empty subsets of {1,2,3,...,n}.
 
If we define the sequence a(n) to be the expression given, we find that it obeys the recursion:
 

a(n) = n + n*a(n-1).
 

It also has the closed formula  a(n) = [e*n! – 1], where the symbol [x] is the nearest integer to x, and e is the usual constant 2.718...
 

The upper-bound is then: O(e*n!) = O( n! )

Question 7

1. What is the minimum found? 13
2. Does the algorithm generate all n! costs or stop when the best is found? Continue to generate all n! costs.
3. Can you suggest a way to reduce the number of costs generated?  The greedy way would be to explore the most promising, those that are lower cost than other choices. If a partial solution is found exceeding a complete solution, terminate the search.

Question 8

Why not use an arbitrary initial lower bounds of <0+0+0+0> = cost 0?

Would increase the number of possible solutions explored. Assume all assignments to person a have been made.

The costs of person a would be: a1=9+0+0+0=9, a2=2, a3=3, and a4=8.

Exploring a2, would assign b with costs of a2+b1=2+6+0+0=8, a2+b3=2+3=5, a2+b4=2+7=9.

The best lower bound is now a3=3 when, using a more accurate initial lower bound it was 16, we never had to explore assignments other than a2.

Is assignment still a factorial time problem? We can reduce the number of possible solutions examined but it is still O(n!) in the worst case.