UNIT -4

Back tracking and Branch and Bounds: 8-Queens Problem, Graph

Coloring, Hamilton cycle, Knapsack Problem, 0/1Knapsack Problem,
Traveling salesperson problem.
BACKTRACKING METHODOLOGY

• Many problems which deal with searching for a set of solutions or for a optimal solution
satisfying some constraints can be solved using the backtracking formulation.

• In Backtracking method, the desired solution is expressed as an n-tuple vector :

(x1…………… xi ……………….xn ) where xi is chosen from some finite set Si.

• The problem is to find a vector, which maximizes or minimizes a criterion function

P(x1…………… xi ……………….xn ).

• The major advantage of this method is, once we know that a partial vector(x1,…xi) will
not lead to an optimal solution then the generation of remaining components i.e.,
(xi+1………..xn) are ignored entirely.
State Space Tree Terminology
1.Criterion function: It is a function P(X1, X2… X n) which needs to be maximized or
minimized for a given problem.
2. Solution Space: All tuples that satisfy the explicit constraints define a possible
solution space for a particular instance ‘I’ of the problem
3. Problem state: Each node in the tree organization defines a problem state.
4. Solution States: These are those problem states S for which the path form the root
to S define a tuple in the solution space.
5. State space tree: If we represent solution space in the form of a tree then the tree
is referred as the state space tree.
6. Answer States: These solution states S for which the path from the root to S
defines a tuple which is a member of the set of solution (i.e. it satisfies the implicit
constraints) of the problem.
State Space Tree
Terminology..contd
7. Live node: A node which has been generated and all of whose children have not yet been
generated is live node.

8. E-node: The live nodes whose children are currently being generated is called E-node (node
being expanded)

9. Dead node: It is a generated node that is either not to be expanded further or one for which
all of its children has been generated.

10. Bounding function: It will be used to kill live nodes without generating all their children

11. Branch and bound: It is a method in which E-node remains E-node until it is dead
 Applications of Backtracking

1. Producing all permutations of a set of values

2. Parsing languages
3. Games: anagrams, crosswords, word jumbles, 8 queens
4. Combinatory and logic programming
Example Problems
1.N queen’s problem
2.Sum of subsets problem.
3.Graph colorig problem
4.0/1 knapsck problem
5.Hamiltonian cycle problem
8-Queens Problem
8-Queens Problem
8-Queens Problem
8-Queens Problem
8-Queens Problem
• n– queens : Defining the problem:-
• The problem is to place n queens on an n x n chessboard so that
• no two “attack” that is no two queens on the same row, same
• column, or same diagonal.
 Assume rows and columns of chessboard are numbered 1 through n. Queens also be
numbered 1 through n.

 Condition to ensure - No two queens on same Row: Each queen must be on a different
row ,hence queen i is to be placed on row i. Therefore all solutions to the n-queens problem
can be represented as n-tuples ( x1,x2,…..xn), where xi is the column on which queen i is placed.

 Condition to ensure - No two queens on same Column:

• Select a distinct value for each xi
Condition to ensure - No two queens on same
Diagonal

If two queens are placed at positions ( i, j ) and ( k, l ). They are on the same
diagonal then following conditions hold good.
1) Every element on the same diagonal that runs from the upper left to the
lower right has the same row – column value. i – j = k – l -----(1)
2) Similarly, every element on the on the same diagonal that goes from the
upper right to the lower left has the same row + column value.
i + j = k + l -----(2)
• First equation implies :j -l=i–k
Second equation implies :j–l=k–i
• Therefore, two queens lie on the same diagonal if and only if
j–l = i–k
• Algorithm place( k, i )
• // It returns true if a queen can be placed in kth row and ith
• // column . Otherwise it returns false. x[] is a goal array whose
• // first( k-1) values have been set. Abs(r) returns the absolute value of r.
• {
• for j = 1 to k-1 do
• { // Two in the same column or in the same diagonal
• if ( ( x [ i ] = i ) or ( Abs( x[ j ] - i ) = Abs( j - k ) ) ) then
• return false;
• }
• return true ;
• }
Algorithm Nqueen(k, n)
// Using backtracking, this procedure prints all possible placements
// of n queens on an n×n chessboard so that they are nonattacking.
{
for i = 1 to n do // check place of column for queen k
{
if place( k, i ) then
{
x[ k ] = i;
if( k = n ) then write ( x[1:n] );
else NQueens( k+1, n);
}
}

}
Graph Coloring Problem
(Backtracking)
• Problem Statement
– Given an undirected graph and a number m,
– determine if the graph can be colored with at most m colors
– such that no two adjacent vertices of the graph are colored with same color.
• Problem is also called as m-colorability decision problem
• Here coloring of a graph means assignment of colors to all vertices.
Graph Coloring Problem
Graph Coloring
• Applications
• To make exam schedule for a university
• This problem can be represented as a graph where every vertex is a
subject and an edge between two vertices mean there is a common
student.
• So this is a graph coloring problem where minimum number of time
slots is equal to the chromatic number of the graph.
Graph Coloring
• Applications
• Mobile Radio Frequency Assignment
• When frequencies are assigned to towers, frequencies assigned to all
towers at the same location must be different.
• How to assign frequencies with this constraint? What is the minimum
number of frequencies needed?
• This problem is also an instance of graph coloring problem where
every tower represents a vertex and an edge between two towers
represents that they are in range of each other.
Graph Coloring
• Applications Map Coloring
• Geographical maps of countries or states where no two adjacent
cities cannot be assigned same color.
Graph coloring
• If the degree of the graph is d, it can be colored with d+1 colors
• m-colorability optimization problem finds the smallest integer m, for
which the graph G can be colored.
• This integer is referred as the chromatic number of the graph.
• Example: 3 colors sufficient for the graph given below
Graph coloring
• Represent the graph by adjacency matrix G[1:n,1:n]
• Colors represented by 1,2,3 … m
• Solutions are given by n-tuple (x1,x2,….. Xn), xi is the color of node i
Algorithm
X[1:m] is initialized to zeros
k - Index of the vertex to color
 Back tracking and Branch and Bounds

• Branch and bound is one of the techniques used for problem solving.
• It is similar to the backtracking since it also uses the state space tree.
• But it follows Breadth First Search instead of Depth First Search.
• It is used for solving the optimization problems and minimization
problems.
• If we have given a maximization problem then we can convert it using
the Branch and bound technique.
 Travelling sales person problem

Example 1:
Given a set of cities and distance between every pair of cities, the
problem is to find the shortest possible tour that visits every city exactly
once and returns to the starting point.
The adjacent matrix of the problem is given below:
6

A B A B C D
4
A ∞ 4 9 5
5
8
4 B 6 ∞ 4 8
9
C 9 4 ∞ 9
D C D 5 8 9 ∞
9
 Travelling sales person problem
Solution:
Steps to solve:
1. Construct a state space tree by choosing any vertex from the given graph
as a starting vertex and find the cost for it by checking whether the matrix is a Reduced
Matrix(All row and column should contain at least one value as 0).
2. If the matrix is a reduced Matrix then calculate the cost of that node by
using the formula,
c[j] = c[i,j] + c[i] + r where, r is the reduced cost
3. Otherwise, convert the matrix into reduced matrix by subtracting the row
and column values with the minimum value respectively.
4. Take the adjacent vertices and find the cost for all.
5. Proceed the traversals by choosing the minimum cost vertices(LC Bound)
until the tour completes and reaches the starting point(starting vertex).
6. Initially the upper bound value is
Travelling sales person problem
Travelling sales person problem
Travelling sales person problem
Travelling sales person problem
0/1 Knapsack problem
Consider the instance:
M = 15,
n = 4,
(P1, P2, P3, P4) = (10, 10, 12, 18) and
(w1, w2, w3, w4) = ( 2, 4, 6, 9).

Solution:
• Construct a state space tree
• Calculate lower bound and upper bound for each node.
• No fractions are allowed in calculation of upper bound
• Fractions are allowed in calculation of lower bound
 0/1 Knapsack problem
Place first item in knapsack.
Remaining weight of knapsack is 15 – 2 = 13.
Place next item w2 in knapsack and the remaining weight of knapsack is 13 – 4 = 9.
Place next item w3 in knapsack then the remaining weight of knapsack is 9 – 6 = 3.
Profit= P1 + P2 + P3 = 10 + 10 + 12
So, Upper bound = 32

To calculate lower bound we can place w4 in knapsack since fractions are allowed in
calculation of lower bound.
Lower bound = 10 + 10 + 12 + (18/9 x 3) = 32 + 6 = 38

• Knapsack problem is maximization problem but branch and bound technique is applicable for
only minimization problems
• In order to convert maximization problem into minimization problem we have to take
negative sign for upper bound and lower bound.
0/1 Knapsack problem
0/1 Knapsack problem
 0/1 Knapsack problem
• Here the difference is same, so compare upper bounds of nodes 8 and 9. Discard the node, which has
maximum upper bound. Choose node 8, discard node 9 since, it has maximum upper bound.

• Consider the path from 1 -> 2 -> 4 -> 7 -> 8

X1 = 1
X2 = 1
X3 = 0
X4 = 1

• The solution for 0/1 Knapsack problem is (x1, x2, x3, x4) = (1, 1, 0, 1)
• Maximum profit is: ∑Pi xi = 10 x 1 + 10 x 1 + 12 x 0 + 18 x 1
= 10 + 10 + 18 = 38.