Design and Analysis of Algorithm
Module V
Let me know, if any typos and other mistakes in the shared ppt
slides
[1]
Module 5
Module No. 5 Backtracking 6 Hours
n-Queens problem (Four & Eight) – Hamiltonian Circuit Problem
– Subset Sum Problem –Graph Coloring Problem
[2]
Backtracking
Backtracking is a class of algorithms for finding solutions
to some computational problems
Types of Backtracking Algorithm
Backtracking algorithms are classified into two types:
1. Algorithm for recursive backtracking
2. Non-recursive backtracking algorithm
[3]
Example : State-Space-Tree
• Sitting arrangement of 3 students(B1,B2,G) in a
space table of size 3 without any constraints.
B1 G
B2
B2 B2
G
B1 G B1
B1
G B2 G B1
B2
[4]
Example : State-Space-Tree
• Sitting arrangement of 3 students(B1,B2,G) in a
space table of size 3 with a constraint that girl is
not allowed to sit in the middle.
B1 B2 G
B2 B2
G B1 G
B1
B1
G G B2
[5] Applying bounding condition
Backtracking Vs Branch &Bound
• Backtracking uses DFS
• Branch & Bound uses BFS
[6]
N-Queen Problem
The n-queens puzzle is the problem of placing n queens
on an n x n chessboard such that no two queens attack
each other.
[7]
N-Queen Problem
• Consider n*n chess board and try to find all
ways to place n non-attacking queens
• N=4
Constraints
• No two or more queens in a row
• No two or more queens in a column
• No two or more queens in same diagonal
[8]
4-Queen Example
Constraints
•No two or more queens in a row
•No two or more queens in a column
C=4
C=1
Note: Q1 in Row1, Q2 in Row2 and so on.. C=2 C=3
Q1 Q1 Q3
Q1
Col=2 C=4
C=3
Q2 Q2 Q2
C=3 C=2 C=2 C=3
C=4 C=4
Q3 Q3 Q3 Q3 Q3 Q3
C=4 C=3 C=4 C=2 C=3 C=2
Q4 Q3 Q4 Q3 Q4 Q3
[9]
4-Queen Example
Constraints
•No two or more queens in a row
•No two or more queens in a column
•No two or more in same diagonal
•Note: Q1 in Row1, Q2 in Row2 and so on..
C=1
C=2
Q1 C=4 Q1
C=2
C=3
Q2 Q2 Q2
C=2 C=3
C=2
C=4
Q3 Q3 Q3
Q3
C=3
Q4
[10]
4-Queen Solution(State Space Tree)
[11]
Algorithm
[12]
Recursive Execution
Nqueens(k=1,n=4)
for(i=1 to 4) i=
{
Nqueens(k+1,4)
}
Nqueens(k=2,n=4)
for(i=1 to 4) i=
{
Nqueens(k+1,4)
}
Nqueens(k=3,n=4)
for(i=1 to 4) i=
{
Nqueens(k+1,4)
}
Nqueens(k=4,n=4)
for(i=1 to 4) i=
{
Nqueens(k+1,4)
[13] }
NQueen(k,n)
void NQueen(int k,int n)
{ int i;
for(i=1;i<=n;i++) x
{ if(place(k,i)==1)
{ x[k]=i;
if(k==n)
printboard(n);
else X 2 4 1 3
NQueen(k+1,n);
} Column Numbers
}
}
[14]
int place(k,i)
int place(int k,int i)
{ int j;
for(j=1;j<k;j++)
{ if((x[j]==i)||abs(x[j]-
i)==abs(j-k))
return 0;
}
return 1;
}
[15]
Program
void printboard(int n)
{ int i;
for(i=1;i<=n;i++)
print(x[i]);
}
===============================
void main()
{ int n;
print("Enter Value of N:");
scan(n);
NQueen(1,n);
}
[16]
Complexity
Time complexity: O(N!) :
The first queen has N placements, the second
queen must not be in the same column as the first
as well as at an oblique angle, so the second
queen has N-1 possibilities, and so on, with a time
complexity of O(N!) .
Space Complexity: O(N) : Need to use arrays to
save information.
[17]
Subset Sum Problem
[18]
Subset Sum Problem
[19]
Example
Xi=0, indicates not included
Xi=1, indicates included in the solution
X1=1 X1=0
2 2 5 8 10
X
X2=1 X2=0
5 5 N=4 and M=15
X3=1 X3=0 X3=0
8 X3=1
8
X4=1 X4=0 X4=0
10 X4=1
If we continue for all possible solutions without a
bounding condition, we will get 2n solutions
[20]
Subset Sum Problem with Bounding
Xi=0, indicates not included
Cw: current weight Xi=1, indicates included in the solution
Rw: remaining weight
X 2 5 8 10
Cw, Rw
N=4 and M=15
Xi=0
Xi=1
Bounding Condition
[21]
Example
X 5 10 12 13 15 18 0, 73
1 2 3 4 5 6 X1=1 X1=0
N=6 and M=30 5, 68 Bounding Condition
X2=1 X2=0
15, 58
X3=1 X3=0
27, 46
X4=0
X4=1
40, 33 27, 33
B1 X5=0
X5=1
42, 18 27, 18
B1 X6=0
X6=1
45, 0 27, 0
B1 B2
[22]
Example
X Bounding Condition
5 10 12 13 15 18 0, 73
1 2 3 4 5 6 X1=1 X1=0
N=6 and M=30 5, 68
X2=1 X2=0
15, 58
X3=1 X3=0
15, 46
X4=0
X4=1
28, 33
X5=0 15, 33
33, 18 X5=1
28, 18 X5=0
X6=0 X5=1
B1
X6=1
46, 0 28, 0
B1
B2
[23]
Example
N=6
M=30
W[1 : 6]={5,10,12,13,15,18}
[24]
Algorithm
27, 33 X 27,
5 10 3312 13 15 18
X5=0 X5=0
X5=1 1X5=12 3 4 5 6
X 42, 18 27, 18 27, 18
5 10 12 13 15 38 X6=0
N=6 and M=30
X6=0
B1
1 2 3 4 5X6=1
6 X6=1
S+r-w[k]>=m
N=6 and M=30
27+(33-15)>=30
Let assume
[25]
Recursive Execution Step=1
SumOfSub(s=0, k=1,r=30) X 3 5 10 12
If(s+w[k]==m)
print solution
s=0+3 1 2 3 4
Else if(s+w[k]+w[k+1]<=m) N=4 and M=20
SumOfSub(s+w[k], k+1,r-w[k])
If(s+r-w[k]>m or s+w[k+1]<m)
SumOfSub(s=0, k+1,r-w[k])
SumOfSub(s=3,k=2,r=27)
If(s+w[k]==m)
s=3+5
print solution
Else if(s+w[k]+w[k+1]<=m)
SumOfSub(s+w[k], k+1,r-w[k])
If(s+r-w[k]>m or s+w[k+1]<m)
SumOfSub(s=5, k+1,r-w[k])
SumOfSub(s=8,k=3,r=22)
If(s+w[k]==m) s=8+10
S=8+(10+12) <=20 print solution
Else if(s+w[k]+w[k+1]<=m)
NO SumOfSub(s+w[k], k+1,r-w[k])
If(s+r-w[k]>=m or s+w[k+1]<=m) 8+(22-10)>=20 &&
SumOfSub(s=8, k+1,r-w[k]) 8+12<=20
[26]
Recursive Execution Step=2
SumOfSub(s=8, k=4,r=12) X 5 8 10 12
If(s+w[k]==m) s=8+12 1 2 3 4
print solution
Else if(s+w[k]+w[k+1]<=m) N=4 and M=20
SumOfSub(s+w[k], k+1,r-w[k])
If(s+r-w[k]>m or s+w[k+1]<m)
SumOfSub(s=13, k+1,r-w[k])
[27]
Recursive Execution Step=3
SumOfSub(s=13, k=4,r=12) X 5 8 10 12
If(s+w[k]==m) s=13+12 1 2 3 4
print solution
Else if(s+w[k]+w[k+1]<=m) N=4 and M=20
SumOfSub(s, k+1,r) 13+(12-12)>20 or
If(s+r-w[k]>m AND s+w[k+1]<m) 13+12<20
SumOfSub(s=13, k+1,r-w[k]) Backtrack
SumOfSub(s=5,k=2,r=30)
If(s+w[k]==m)
s=5+8
print solution
Else if(s+w[k]+w[k+1]<=m)
SumOfSub(s, k+1,r)
If(s+r-w[k]>m or s+w[k+1]<m)
SumOfSub(s=5, k+1,r-w[k])
SumOfSub(s=13,k=3,r=22)
Backtrack If(s+w[k]==m) s=13+10
print solution
Else if(s+w[k]+w[k+1]<=m)
SumOfSub(s, k+1,r)
13+(22-10)>20 or
If(s+r-w[k]>m or s+w[k+1]<m)
13+12<20
[28] SumOfSub(s=13, k+1,r-w[k])
Complexity
Complexity analysis:
Time Complexity: O(2n) worst case
The above solution may try all subsets of the given set in the. Therefore time
complexity of the above solution is exponential.
Auxiliary Space: O(n) where n is recursion stack space.
[29]
Program
public static void main(String args[])
{
int list[] = {1, 3, 5, 2};
subset_sum(list, 0, 0, 6);
[Link](subset_count);
}
}
[30]
program
public class subset_sum_backtrack
{ static int subset_count = 0;
static void subset_sum(int list[], int sum, int starting_index, int target_sum)
{
if( target_sum == sum )
{
subset_count++;
if(starting_index < [Link])
subset_sum(list, sum - list[starting_index-1], starting_index, target_sum);
}
else
{
for( int i = starting_index; i < [Link]; i++ )
{
subset_sum(list, sum + list[i], i + 1, target_sum);
}
}
}
[31]
Graph Coloring
Problem
[32]
Graph Coloring Problem
Vertex coloring is the most commonly encountered graph
coloring problem. The problem states that given m colors,
determine a way of coloring the vertices of a graph such
that no two adjacent vertices are assigned same color.
[33]
Objective
The objective is to find
How many minimum number of colours are required to
colour the graph nodes: m-Colouring Optimization
if m colours are given then, is it possible to colour the
graph node with given number of colours or not:-Graph
colouring Algorithm/ m-Colouring Decision Problem.
[34]
Solutions without Bounding Conditions
1 2
X 1 2 3 4 5
3 M=3 {Red, Green, Blue}
4 R B
G 1
R 1 1 B
2 G R G 2
R B R G B B
2 2 2 2 2 2
3 G R G 3
2
R 3 3 3 3
3 3
4 3 3
Number of solutions =C (n+1)
[35]
Example
1 2
X 1 2 3 4 5
3 M=3 {Red, Green, Blue}
5
4 X1=R X1=B
X1=G
1
3
X4=R
[36]
Algorithm
A Graph G with n nodes and m number of given colors. Initial value of k=1
1 2 0 1 1 0 1 0,1,2,3
0,1 0,1,2 0,1 0,1,2
1 0 1 0 0
X, 1 2 3 4 5
1 1 0 1 0 M=3 {1=Red, 2=Green, 3=Blue}
3
5
0 0 1 0 1
4
1 0 0 1 0
[37]
Example
1 2
3
5
[38]
Example
1
6
5
2
10 7
9 8
4 3
[39]
Hamiltonian
Circuit Problem
[40]
Hamiltonian circuit
A Hamiltonian cycle, also called a Hamiltonian circuit, is
a graph cycle through a graph that visits each node
exactly once.
A Hamiltonian circuit is a circuit that visits
every vertex once with no repeats, and must
start and end at the same vertex.
Removing any edge from a Hamiltonian
cycle produces a Hamiltonian path
[41]
Hamiltonian Circuit Problem
2 0 1 0 1 0 1
1
1 0 1 0 0 0
0 1 0 1 0 0
3
6 1 0 1 0 1 1
4
0 0 0 1 0 1
5
1 0 0 0 1 0
[42]
Example
[43]
[44]
[45]
Algorithm
[46]
Algorithm
[47]
Algorithm
Hamilton(x[ ],k)
{ do{ nextValue(x[ ],k)
nextValue(x[ ], k); { do {
if(x[k==0) x[k]=x[k]+1 mod (n+1);
return; if(x[k]==0)
if(k==n) return;
write(x[],n) if(G[x[k-1], x[k] ] ==1)
else for(j=1; j<k; j++)
Hamilton(x[], k+1) if(x[k]==x[j])
while(True); break;
} if(j==k)
if((k<n) OR (k==n &G[ x[k], x[1] ]==1))
return;
}while(True);
}
[48]
Complexity
The time complexity of Hamiltonian Circuit is O(N!), where N
is the number of vertices.
The worst-case time complexity is O(n^6*d^2), where d is the
maximum degree of vertex.
The Hamiltonian cycle algorithm runs in exponential time, with
a time complexity of O(n^n).
The naive algorithm for Hamiltonian Path takes time about n!
= 2 (nlogn) to try all possible permutations of the nodes.
[49]