Backtracking Technique
Eg. Big Castle – Large Rooms & “Sleeping Beauty”
• Systematic search - BFS, DFS
• Many paths led to nothing but “dead-ends”
• Can we avoid these unnecessary labor?
(bounding function or promising function)
• DFS with bounding function (promising function)
• Worst-Case : Exhaustive Search
Backtracking Technique
• Useful because it is efficient for “many” large instances
• NP-Complete problems
Eg. 0-1 knapsack problem
D.P. : O(min(2n, nW))
Backtracking : can be very efficient
if good bounding function(promising function)
• Recursion
Outline of Backtracking Approach
• Backtracking : DFS of a tree except that nodes
are visited if promising
• DFS(Depth First Search) 1
2 6
• Procedure d_f_s_tree(v: node)
3 4 5 7 11
var u : node
{ 8 9 10
visit v; // some action //
for each child u of v
do d_f_s_tree(u);
}
N-Queens Problem
N-Queens Problem
• nⅹn Chess board
• n-Queens 1 2 3 4 5 6 7 8
Q
12345678
Q
Eg. 8-Queens problem Q
Q
2 n 2
n
(n) , , n , n!,
n
n
N-Queens Problem: DFS
• State Space Tree for 4-Queens Problem
N-Queens Problem: DFS (Same Col/Row x)
• State Space Tree for 4-Queens Problem
X1=1 2 3 4
X2=2 3 4 1 3 4 1 2 4 1 2 3
3 4 2 4 2 3 3 4 1 4 1 3 2 4
4 3 4 2 3 2 3 2
(x1, x2, x3, x4)=(2, 4, 1, 3)
• #leaf nodes : n!=4!
• DFS : “Backtrack” at dead ends – 4! leaf nodes (n!)
Cf. Backtracking : “Backtrack” if non-promising
(pruning)
N-Queens Problem: Backtracking
• Promising Function(Bounding Function)
(i) same row ⅹ
(ii) same column ⅹ (col(i) ≠ col(k))
(iii) same diagonal ⅹ (|col(i)-col(k)|≠|i-k|)
Q Q
(i, (i,col(i))
Q
col(i))
(k, Q
col(k)) (k,col(k))
N-Queens Problem: Backtracking
• State Space Tree for 4-Queens Problem
N-Queens Problem
#Nodes Checked
#Nodes Checked
DFS #Nodes Checked
n DFS
(same col/row X) Backtracking
(nn)
(n!)
4 341 24 61
8 19,173,961 40,320 15,721
12 9.73ⅹ1012 4.79ⅹ108 1.01ⅹ107
14 1.20ⅹ1016 8.72ⅹ1010 3.78ⅹ108
• Better (faster) Algorithm
Monte Carlo Algorithm
“place almost all queens randomly,
then do remaining queens using backtracking.”
Graph Coloring
• M-coloring problem:
Color undirected graph with ≤m colors
2 adjacent vertices : different colors
(Eg) V1 V2
2-coloring X
3-coloring O
V4 V3
Graph Coloring
start
1 2 3
m
1 2 3
X
1 2 3
X X
1 2 3
X X
• State-Space Tree : mn leaves
• Promising function : check adjacent vertices
for the same color
Hamiltonian Circuits Problem
• TSP problem in chapter 3.
– Brute-force: n!, (n-1)!
– D.P. : (n 1)(n 2)2 n 3
– When n=20, B.F. 3,800 years
D.P. 45 sec.
– More efficient solution? See chapter 6
• Given an undirected or directed graph, find a
tour(HC). (need not be S.P.)
Hamiltonian Circuits Problem
(Eg) V1 V2 V3
V1 V2 V3 V4
V5 V6 V7 V8 V5 V4
HC : X
• State-Space Tree
(n-1)! Leaves : worst-case
• Promising function:
1. i-th node (i+1)-th node
2.(n-1)-th node 0-th node
3. i-th node ≠ 0 ~ (i-1)-th node
Sum-of-Subsets Problem
• A special case of 0/1-knapsack
• S = {item1, item2,…, itemn}, w[1..n] = (w1, w2, …, wn) weights & W
Find a subset A⊆S s.t. ∑wi=W
A
(Eg) n=3, w[1..3]=(2,4,5), W=6
Solution : {w1,w2}
• NP-Complete w1 O
• State Space Tree : 2n leaves
w2 O w2 O
w3 O w3 O w3 O w3 O
{w1,w2}
Sum-of-Subsets Problem
• Assumption : weights are in sorted order
• Promising function
ⅹ weight(up_to_that_node) + w i+1 > W (at i-th level)
ⅹ weight(up_to_that_node) + total(remaining) < W
(Eg) n=4, (w1,w2,w3,w4)=(3,4,5,6), W=13
0
w1=3 3 0
3 0
w2=4 4 0 4 0
7 3 4 0
w3=5 5 0 5 0 5 0 ⅹ:
12 7 8 3 9 4 0+5+6=11<13
w4=6 ⅹ 6 0 ⅹ ⅹ ⅹ: ⅹ
13 7 9+6=15>13
ⅹ
0-1 Knapsack Problem
• w[1..n] = (w1, w2,…, wn)
p[1..n] = (p1, p2,…, pn)
W: Knapsack size
• Determine A⊆S maximizing p
A
i s.t. w
A
i W
• State-Space Tree
x1= 0
x2= 1 0 x2= 0
x3= 1 0 11 1 0
1 0 0
1
x4= 0 1 0 1 0 1 01 0 1 0 1 0 1 0
1
• 2n leaves
Branch-and-Bound
Backtracking
Non-optimization P. n-Queens, m-coloring…
Optimization Prob. 0/1 Knapsack
Compute promising fcn.
Branch & Bound
Optimization Prob.- compute promising fcn.
Maximization Prob. → upper bound in each node
Minimization Prob. → lower bound in each node
BFS with B&B
Best-First-Search with B&B
Breadth First Search
1
procedure BFS(T : tree);
2 3
{ initialize(Q);
4 5 6 7
v = root of T;
visit v; 8 9
enqueue(Q,v);
BFS of a graph
while not empty(Q) do {
dequeue(Q,v);
1
for each child u of v do {
visit u; 2 3 4
enqueue(Q,u); } 5 6 7 8 9 10 11
} 12 13 14 15
}
BFS of a tree
0-1 Knapsack Problem
• BFS with B&B pruning
(Eg) n=4, p[1…4]=(40,30,50,10), w[1…4]=(2,5,10,5),
W=16
0
0
p1=40, w1=2 115
40 0
2 0
115 82
p2=30, w2=5
70 40 30 0
7 2 5 0
115 98 82 60
p3=50, w3=10
120 70 90 40 80 30
17 7 12 2 15 5
0 80 98 50 82 40
p4=10, w4=5 80 70 100 90
12 7 17 12
80 70 0 90
0-1 Knapsack Problem
– Bound = current profit + profit of remaining “fractional”
K.S.
– Non-promising if bound ≤ max profit (or weight ≥W)
(Eg) n=4, p[1…4]=(40,30,50,10), w[1…4]=(2,5,10,5),
0 W=16
0
p1=40, w1=2 115
40 0
2 0
115 82
p2=30, w2=5
70 40 30 0
7 2 5 0
115 98 82 60
p3=50, w3=10
120 70 90 40 80 30
17 7 12 2 15 5
0 80 98 50 82 40
p4=10, w4=5 80 70 100 90
12 7 17 12
80 70 0 90
0-1 Knapsack Problem
• Best First Search with B&B pruning
0
0
p1=40, w1=2 115
40 0
2 0
p2=30, w2=5 115 82
70 40
7 2
115 98
p3=50, w3=10
120 70 90 40
17 7 12 2
0 80 98 50
p4=10, w4=5 100 90
17 12
0 90
