Backtracking.pdf-Backtracking ˜ Examples...
Backtracking.pdf-Backtracking ˜ Examples: • Maze problem
Showing 8-13 out of 13
Backtracking.pdf-Backtracking ˜ Examples: • Maze p...
Backtracking.pdf-Backtracking ˜ Examples: • Maze problem
Backtracking.pdf-Backtracking ˜ Exa...
Backtracking.pdf-Backtracking ˜ Examples: • Maze problem
Page 8
W1
L
W2
L
W3
L
W4
L
Bounding function:
Function bound(k)
Begin
If
=
=
=
n
1
k
i
k
1
i
)
M
i
w
]
i
[
X
(
and
)
M
i
w
k
1
i
i
w
]
i
[
X
(
Then
Return(True);
Else
Return(False);
Endif;
End;
ROOT
1000
S=11<3
0000
S=0<31
1100
S=11+13<31
1101
S=11+13+7 = 31
1000
S=11<3
1100
S=11+13<31
1110
S=11+13+24>31
1010
S=11+24>31
1100
S=11+13<3
1000
S=11<3


Page 9
˜
Hamiltonian Cycle
Definition: A Hamiltonian cycle in an undirected graph
G=(V,E) is a simple cycle that passes through every vertex
once.
Input: a graph G with n vertices
Output: Hamiltonian cycle
Solution:
ü
Use dynamic tree where level i corresponds to the
selection of the ith vertex.
ü
The solution vector X[1..n] is such that X[I] is the
vertex in the cycle.
Example:
ü
Start at vertex 1
1
2
3
4
8
7
6
5


Page 10
2
3
4
5
3
4
5
6
3
4
5
6
7
3
4
5
6
7
8
2
3
4
5
6
7
8
4
3
1
X[2]
X[3]
X[8]


Page 11
Bounding function:
Function bound(k)
integer i;
begin
for i=1 to k-1 do
/* check for distinctness */
If x[i]=x[k]
then
return(False);
endif;
endfor;
If (X[k],X[k]-1) is an edge in G
then
return (True);
else
return(False);
endif;
end;


Page 12
˜
Graph coloring:
Definition: A coloring of a graph G=(V,E) is a mapping
F:V
C where C is a finite set of colors such that if
<v,w> is an element of E then F(v) is different from F(w);
in other words, adjacent vertices are not assigned the same
color.
Input:
Graph G of n vertices and a set of m colors in
C={1,2,…,m}
Output: - color the vertices of G such that no two adjacent
vertices have the same color
Solution:
ü
Use a static tree
ü
The solution vector X[1..n] is such X[i has the color
of the ith node.
Example:
n=4 and m=3
1
3
4
2


Page 13
Bounding function:
Function next_color(k)
Integer i;
begin
for i=1 to k-1 do
If ((k,i) is an edge) and (X[i]=X[k])
then
return (False);
endif;
endfor;
end;
1
2
3
1
2
3
1
2
3
1
2
3
X[2]
X[1]
X[3]
X[4]


Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
George Washington Univers...
George_Washington_University
School:
Design_and_Analysis_of_Algorithms
Course: