The idea
Tehran Technical College of Shariaty
Fall 2008
` Maze off hedges
M h d by
b Hampton
H Court
C Palace
P l
` A sequence of objects is chosen from a specified set so
that the sequence satisfies some criterion
` Example: n-Queens problem
` Sequence: n positions on the chessboard
Chapter 5 `
`
Set: n2 possible positions
Criterion: no two queens can threaten each other
Backtracking ` Depth-first search of a tree (preorder tree traversal)
2 Algorithms ([email protected])
Depth first search The algorithm
4-Queens
4 Queens problem If checking each candidate solution …
` St t space ttree
State
Looking for signs for dead ends Backtracking
` Nonpromising node
` Promising node
` Promisingg function
` Pruning the state space tree
` Pruned state space tree
The generic algorithm 4-Queens problem (1)
4-Queens problem (2) 4-Queens problem (3)
4-Queens
4 Queens problem (4) 4-Queens problem (5)
Pruned state space
p tree Avoid creating nonpromising nodes
The n
n-Queens
Queens Problem Efficiency
y
` Check whether two queens threaten ` Checking the entire state space tree (number of nodes
each other: checked)
` col(i) – col(k) = i – k
` col(i) – col(k) = k - i
` Taking the advantage that no two queens can be placed in
th same row or in
the i th
the same column
l
1 + n + n(n-1) + n(n-1)(n-2) + … + n! promising nodes
Comparison The Sum
Sum-of-Subsets
of Subsets Problem
State Space Tree When W = 6 and w1 = 2,
2 w2 = 4,
4 w3 = 5
` w1 = 2, w2 = 4, w3 = 5
To check whether a node is promising Wh W = 13 and
When d w1 = 3,
3 w2 = 4,
4 w3 = 5,
5 w4 = 6
` Sort the weights in nondecreasing order
` To check the node at level i
` weight + wi+1 > W
` weight + total < W
The algorithm 5
5.4
4 Time complexity
void sum_of_subsets
sum of subsets (index i,i int weight,
weight int total){
if (promising (i))
` The first call to the function
if (weight == W) sum_of_subsets(0, 0, total) where
coutt << include
i l d [1] through
h h include
i l d [i][i];
n
total = ∑ w[ j ]
else{
include [i + 1] = "yes";
sum_of_subsets
f b ( + 1,
(i 1 weight
h + w[i [ + 1],
1] totall - w[i
[ + 1]);
1]) j =1
include [i + 1] = "no";
sum_of_subsets (i + 1, weight, total - w [i + 1]); ` The number of nodes checked
} 1 + 2 + 22 + … + 2n = 2n+1
}
bool promising (index i);{
return (weight + total >=W) &&
((weight
g == W || weight
g + w[i + 1] <= W);
)
}
25 Algorithms (
[email protected]) Algorithms (
[email protected]) 26
Graph coloring Example
` The m-Coloring problem
` Finding all ways to color an undirected graph using at most m ` 2-coloring problem
different colors, so that no two adjacent vertices are the same ` No solution!
color.
l ` 3-coloring problem
` Usually the m-Coloring problem consider as a unique problem
for each value of m.
m
Vertex Color
v1 color1
v2 color2
v3 color3
v4 color2
Application: Coloring of maps Example (1)
` Planar graph ` Map
` It can be drawn in a plane in such a way that no two edges
cross each other.
` To every map there corresponds a planar graph
Example (2) The pruned state space tree
` corresponded planar graph
Algorithm 5.5
5 5 (1) Algorithm 5.5
5 5 (2)
void m_coloring (index i) { booll promising
b p i i (index(i d i) {
int color; index j;
bool switch;
if (promising (i)) switch = true;
if (i == n) j = 1;
cout << vcolor [1] through vcolor [n]; while (j<i && switch){
else if (W[i][j] && vcolor[i] == vcolor[j])
for (color = 1; color <= m; color++){ switch
it h = false;
f l
j++;
vcolor [i + 1] = color;
}
m_coloring (i + 1); return switch;
} }
}
33 Algorithms (
[email protected]) 34 Algorithms (
[email protected])
Algorithm 5.5
5 5 (3) The Hamiltonian Circuits Problem
` The top level call to m_coloring ` The traveling sales person problem
` m_coloring(0) ` Chapter 3: Dynamic programming
` The number of nodes in the state space tree for this ` T(n) = (n-1)(n-2)2n-3
algorithm ` Hamiltonian Circuit (also called a tour)
` Given a connected, undirected graph
` A path that starts at a given vertex, visits each vertex in the
graph exactly once, and ends at the starting vertex
Example (1) Example (2)
` Hamiltonian Circuit ` No Hamiltonian Circuit!
` [v1, v2, v8, v7, v6, v5, v4, v3, v2]
Algorithm 5.6
5 6 (1) Algorithm 5.6
5 6 (2)
void
id hamiltonian
h ilt i (index (i d i) { bool promising (index i) {
index j;
index j; bool switch;
if (p
(promisingg (i))
( )) if (i == nn-1
1 && !W[vindex[n - 1]] [vindex [0]])
if (i == n-1) switch = false;
cout << vindex [0] through vindex [n - 1]; else if (i > 0 && !W[vindex[i - 1]] [vindex [i]])
switch = false;
else
l else{
for (j = 2; j <=n; j++){ switch = true;
vindex [[i + 1]] = j; j = 1;
while (j < i && switch){
hamiltonian (i + 1); if (vindex[i] == vindex [j])
} switch = false; j++;
} }
}
return switch;
}
