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)

Ehsan Adeli ([email protected])

2 Algorithms ([email protected])

Depth first search The algorithm

3 Algorithms ([email protected]) 4 Algorithms ([email protected])

4-Queens
4 Queens problem If checking each candidate solution …
` St t space ttree
State

Algorithms ([email protected]) 5 6 Algorithms ([email protected])

Looking for signs for dead ends Backtracking

` Nonpromising node
` Promising node
` Promisingg function
` Pruning the state space tree
` Pruned state space tree

7 Algorithms ([email protected]) 8 Algorithms ([email protected])

The generic algorithm 4-Queens problem (1)

9 Algorithms ([email protected]) 10 Algorithms ([email protected])

4-Queens problem (2) 4-Queens problem (3)

11 Algorithms ([email protected]) 12 Algorithms ([email protected])

4-Queens
4 Queens problem (4) 4-Queens problem (5)

13 Algorithms ([email protected]) 14 Algorithms ([email protected])

Pruned state space

p tree Avoid creating nonpromising nodes

15 Algorithms ([email protected]) 16 Algorithms ([email protected])

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

Algorithms ([email protected]) 17 Algorithms ([email protected]) 18

Comparison The Sum

Sum-of-Subsets
of Subsets Problem

19 Algorithms ([email protected]) 20 Algorithms ([email protected])

State Space Tree When W = 6 and w1 = 2,
2 w2 = 4,
4 w3 = 5

` w1 = 2, w2 = 4, w3 = 5

Algorithms ([email protected]) 21 22 Algorithms ([email protected])

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

23 Algorithms ([email protected]) 24 Algorithms ([email protected])

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

27 Algorithms ([email protected]) 28 Algorithms ([email protected])

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

29 Algorithms ([email protected]) 30 Algorithms ([email protected])

Example (2) The pruned state space tree

` corresponded planar graph

31 Algorithms ([email protected]) 32 Algorithms ([email protected])

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

35 Algorithms ([email protected]) 36 Algorithms ([email protected])

Example (1) Example (2)
` Hamiltonian Circuit ` No Hamiltonian Circuit!
` [v1, v2, v8, v7, v6, v5, v4, v3, v2]

37 Algorithms ([email protected]) 38 Algorithms ([email protected])

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;
}

39 Algorithms ([email protected]) 40 Algorithms ([email protected])