01 knapsack using backtracking

1. 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

2. Backtracking Technique
•Useful because it is efficient for “many” large instances
•NP-Complete problems
Eg. 0-1 knapsack problem
D.P. : O(min(2
n
, nW))
Backtracking : can be very efficient
if good bounding function(promising function)
•Recursion

3. Outline of Backtracking Approach
•Backtracking : DFS of a tree except that nodes
are visited if promising
•DFS(Depth First Search)
•Procedure d_f_s_tree(v: node)
var u : node
{
visit v; // some action //
for each child u of v
do d_f_s_tree(u);
}
1
2
3 57 114
6
8910

4. N-Queens Problem

5. N-Queens Problem
•nⅹn Chess board
•n-Queens

Eg. 8-Queens problem
, ,)(
2
2
÷
÷
ø
ö
ç
ç
è
æ
n
n
n
n
 ,! ,nn
n
Q
Q
Q
Q
1 2 3 4 5 6 7 8
1

2

3

4

5

6

7

8

6. N-Queens Problem: DFS
•State Space Tree for 4-Queens Problem

7. N-Queens Problem: DFS (Same Col/Row x)
•State Space Tree for 4-Queens Problem
X
1=1
X
2=234
43
434232 3 2
24 32 34141324
134 124 321
2 3 4
(x
1, x
2, x
3, x
4)=(2, 4, 1, 3)
•#leaf nodes : n!=4!
•DFS : “Backtrack” at dead ends – 4! leaf nodes (n!)
Cf. Backtracking : “Backtrack” if non-promising
(pruning)

8. 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
(i,
col(i))
Q
(k,
col(k))
Q
(i,col(i))
Q
(k,col(k))

9. N-Queens Problem: Backtracking
•State Space Tree for 4-Queens Problem

10. N-Queens Problem
•Better (faster) Algorithm
Monte Carlo Algorithm
“place almost all queens randomly,
then do remaining queens using backtracking.”
#Nodes Checked
DFS
(n
n
)
#Nodes Checked
DFS
(same col/row X)
(n!)
#Nodes Checked
Backtracking
341
19,173,961
9.73ⅹ10
12
1.20ⅹ10
16
24
40,320
4.79ⅹ10
8
8.72ⅹ10
10
61
15,721
1.01ⅹ10
7
3.78ⅹ10
8
4
8
12
14
n

11. Graph Coloring
•M-coloring problem:
Color undirected graph with ≤m colors
2 adjacent vertices : different colors
(Eg)
V
1
V
2
V
4
V
3
2-coloring X
3-coloring
O

12. Graph Coloring
•State-Space Tree : m
n
leaves
•Promising function : check adjacent vertices
for the same color
m£
start
1 2 3
21 3
21 3
21 3
X
X
X
X X

13. Hamiltonian Circuits Problem
•TSP problem in chapter 3.
–Brute-force: n!, (n-1)!
–D.P. :
–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.)
3
2)2)(1(
-
--
n
nn

14. Hamiltonian Circuits Problem
•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
V
1
V
2
V
6
V
5
V
3
V
7
V
4
V
8
V
1
V
2
V
5
V
3
V
4
HC : X
(Eg)

15. Sum-of-Subsets Problem
•A special case of 0/1-knapsack
•S = {item
1
, item
2
,…, item
n
}, w[1..n] = (w
1
, w
2
, …, w
n
) weights & W
Find a subset A S s.t. ∑w
⊆
i
=W
(Eg) n=3, w[1..3]=(2,4,5), W=6
Solution : {w
1
,w
2
}
•NP-Complete
•State Space Tree : 2
n
leaves
A
w
1
w
2
w
3
w
2
w
3
w
3
w
3
O
O O
OOOO
{w
1
,w
2
}

16. 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, (w
1
,w
2
,w
3
,w
4
)=(3,4,5,6), W=13
ⅹ
12
7
3 97 8
13
4
0437
0
03
3 0
4
5
0 04
55
6
0 00
0ⅹ
ⅹ:
0+5+6=11<13
ⅹⅹ:
9+6=15>13
ⅹⅹ
w1=3
w2=4
w3=5
w4=6

17. 0-1 Knapsack Problem
•w[1..n] = (w
1
, w
2
,…, w
n
)
p[1..n] = (p
1
, p
2
,…, p
n
)
W: Knapsack size
•Determine A S maximizing
⊆
•State-Space Tree
•2
n
leaves
x
1
=1
x
2
=1
x
3
=1
x
4
=1
0
0
0
000
00
0000
0
0
1
11 110
1
1 1
1
1
x
2
=1
Wwtsp
A
i
A
i £åå ..

18. 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

19. Breadth First Search
procedure BFS(T : tree);
{initialize(Q);
v = root of T;
visit v;
enqueue(Q,v);
while not empty(Q) do {
dequeue(Q,v);
for each child u of v do {
visit u;
enqueue(Q,u); }
}
}
1
2 3
4 5 6 7
8 9
1
2
56789
3 4
1011
1213 1415
BFS of a graph
BFS of a tree

20. 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
115
40
2
115
0
0
82
70
7
115
40
2
98
120
17
0
70
7
80
80
12
80
70
7
70
90
12
98
40
2
50
100
17
0
90
12
90
30
5
82
80
15
82
30
5
40
0
0
60
p1=40, w1=2
p2=30, w2=5
p3=50, w3=10
p4=10, w4=5

21. 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), W=16
0
0
115
40
2
115
0
0
82
70
7
115
40
2
98
120
17
0
70
7
80
80
12
80
70
7
70
90
12
98
40
2
50
100
17
0
90
12
90
30
5
82
80
15
82
30
5
40
0
0
60
p1=40, w1=2
p2=30, w2=5
p3=50, w3=10
p4=10, w4=5

22. 0-1 Knapsack Problem
•Best First Search with B&B pruning
0
0
115
40
2
115
0
0
82
70
7
115
40
2
98
120
17
0
70
7
80
90
12
98
40
2
50
100
17
0
p1=40, w1=2
p2=30, w2=5
p3=50, w3=10
p4=10, w4=5
90
12
90