Analysis of Algorithm Chapter-5

UNIT – Five
5. Introduction to Backtracking
5.1 Backtracking:
 It is one of the most general algorithm design techniques.
 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.
 To apply backtracking method, the desired solution must be expressible as an n-tuple
(x1…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….xn).
 The major advantage of this method is, once we know that a partial vector (x1,…xi)
will not lead to an optimal solution that (mi+1………..mn) possible test vectors may be
ignored entirely.
 Many problems solved using backtracking require that all the solutions satisfy a
complex set of constraints.
 These constraints are classified as:
1) Explicit constraints.
2) Implicit constraints.

1)Explicit constraints:

Explicit constraints are rules that restrict each Xi to take values only from a given set.
Some examples are,
Xi  0 or Si = {all non-negative real nos.}
Xi =0 or 1 or Si={0,1}.
Li  Xi  Ui or Si= {a: Li  a  Ui}
 All tuples that satisfy the explicit constraint define a possible solution space for‘i’.
2)Implicit constraints:

The implicit constraint determines which of the tuples in the solution space ‘i’ can
actually satisfy the criterion functions.

1
 Analysis of Algorithm Chapter-5

Algorithm:
Algorithm Backtracking (n)
// This schema describes the backtracking procedure. All solutions are generated in
X[1:n]
//and printed as soon as they are determined.
{
k=1;
While (k  0) do {
if (there remains all untried
X[k]  T (X[1],[2],…..X[k-1]) and Bk (X[1],…..X[k])) is true ) then
{
if(X[1],……X[k] )is the path to the answer node)
Then write(X[1:k]);
k=k+1; //consider the next step.
}
else k=k-1; //consider backtracking to the previous set.
}}
 All solutions are generated in X[1:n] and printed as soon as they are determined.
 T(X[1]…..X[k-1]) is all possible values of X[k] gives that X[1],……..X[k-1] have
already been chosen.
 Bk(X[1]………X[k]) is a boundary function which determines the elements of
 X[k] which satisfies the implicit constraint.
 Certain problems which are solved using backtracking method are
1. N-Queens problem.
2. Graph coloring.
3. Hamiltonian cycle.

5.2 8-Queens Problem:

This 8 queens’ problem is to place n-queens in an ‘N*N’ matrix in such a way that no two
queens attack each otherwise no two queens should be in the same row, column, diagonal.
Solution:

The solution vector X (X1…Xn) represents a solution in which Xi is the column of
the ith row where ith queen is placed.

First, we have to check no two queens are in same row.

Second, we have to check no two queens are in same column.

The function, which is used to check these two conditions, is [I, X (j)], which gives
position of the ith queen, where I represents the row and X (j) represents the column
position.

Third, we have to check no two queens are in it diagonal.

Consider two-dimensional array A [1: n,1: n] in which we observe that every element
on the same diagonal that runs from upper left to lower right has the same value.

Also, every element on the same diagonal that runs from lower right to upper left has
the same value.

Suppose two queens are in same position (i,j) and (k,l) then two queens lie on the
same diagonal , if and only if |j-l|=|I-k|.

2
 Analysis of Algorithm Chapter-5

STEPS TO GENERATE THE SOLUTION:


Initialize x array to zero and start by placing the first queen in k=1 in the first row.

To find the column position start from value 1to n, where ‘n’ is the no. Of columns or no.
Of queens.

If k=1 then x (k)=[Link] (k,x(k)) will give the position of the k th queen. Here we have to
check whether there is any queen in the same column or diagonal.

For this considers the previous position, which had already, been found out. Check whether
X (I)=X(k) for column |X(i)-X(k)|=(I-k) for the same diagonal.

If any one of the conditions is true then return false indicating that kth queen can’t be placed
in position X(k).

For not possible condition increment X(k) value by one and precede d until the position is
found.

If the position X (k)  n and k=n then the solution is generated completely.
 If k<n, then increment the ‘k’ value and find position of the next queen.
 If the position X (k)>n then kth queen cannot be placed as the size of the matrix is‘N*N’.

So decrement the ‘k’ value by one i.e. we have to back track and after the position of
the previous queen.

Algorithm:
Algorithm place (k,I)
//return true if a queen can be placed in kth row and ith column. otherwise it returns //
//false. X[] is a global array whose first k-1 values have been set. Abs® returns the
//absolute value of r.
{
For j=1 to k-1 do
If ((X [j]=I) //two in same column.
Or (abs (X [j]-I)=Abs (j-k)))
Then return false;
Return true;
}
Algorithm Nqueen (k,n)
//using backtracking it prints all possible positions of n queens in ‘n*n’ chessboard. So
//that they are non-tracking.
{
For I=1 to n do
{
If place (k,I) then
{
X [k]=I;
If (k=n) then write (X [1:n]);
Else nquenns(k+1,n) ;
}
}
}

3
 Analysis of Algorithm Chapter-5

Example: 4 queens.

Two possible solutions are

Q Q
Q Q
Q Q
Q Q

Solutin-1 Solution 2
(2 4 1 3) (3 1 4 2)
Example: One solution to 8 queens.

Q
Q
Q
Q
Q
Q
Q
Q

4
 Analysis of Algorithm Chapter-5

5.3 Sum of Subsets

• The Sum of Subset Problem is, there will be a set of distinct positive Numbers X and a
given Number N. Now, we have to find all the combination of numbers from X that sum
up to N. Make a Set of those Number.
• If we sort the weights in nondecreasing order before doing the search, there is an obvious
sign telling us that a node is nonpromising.
• Bounding function
• Bk(x1,..,xk)=true iff

wixi wi m
k n

i1 ik1
• Assuming wi’s in nondecreasing order, (x1,..,xk) cannot lead to an answer node if
w x w
k
i i k1 m
i1
• So, the bounding function is
Bk (x1,...,xk )  trueiffwixi  wi  m
k n

i1 ik1

w x w
k
and i i k1 m
i1
• Example: Show the pruned state space tree when backtracking is used with
n = 4, W = 13, and w1 = 3, w2 = 4, w3 = 5, and w4 = 6.

5
 Analysis of Algorithm Chapter-5

5.4 Graph Coloring:


Let ‘G’ be a graph and ‘m’ be a given positive integer. If the nodes of ‘G’ can be colored
in such a way that no two adjacent nodes have the same color. Yet only ‘M’ colors are
used. 

There are Two Problems:
The m-coloring optimization problem, calls for coloring a graph using the
minimum number of coloring.
The m-coloring decision problem, known as K-coloring asks whether a graph is
colourable using at most k-colors.

The graph G can be colored using the smallest integer ‘m’. This integer is referred to
as chromatic number of the graph.

A graph is said to be planar iff it can be drawn on plane in such a way that no two
edges cross each other.

Suppose we are given a map then; we have to convert it into planar. Consider each and
every region as a node. If two regions are adjacent then the corresponding nodes are
joined by an edge.
Consider a map with five regions and its graph.

4 5

2
1
3

1 is adjacent to 2, 3, 4.
2 is adjacent to 1, 3, 4, 5
3 is adjacent to 1, 2, 4
4 is adjacent to 1, 2, 3, 5
5 is adjacent to 2, 4

2 3

5 4

6
 Analysis of Algorithm Chapter-5

Steps to color the Graph:


First create the adjacency matrix graph(1:m,1:n) for a graph, if there is an edge between
i,j then C(i,j) = 1 otherwise C(i,j) =0.

The Colors will be represented by the integers 1,2,…..m and the solutions will be stored
in the array X(1),X(2),………..,X(n) ,X(index) is the color, index is the node.

He formula is used to set the color is,
X(k) = (X(k)+1) % (m+1)

First one chromatic number is assigned, after assigning a number for ‘k’ node, we have
to check whether the adjacent nodes has got the same values if so then we have to
assign the next value.

Repeat the procedure until all possible combinations of colors are found.

The function which is used to check the adjacent nodes and same color is,
If(( Graph (k,j) == 1) and X(k) = X(j))
Example:
2
1

4 3
N= 4
M= 3

Adjacency Matrix:

0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0


Problem is to color the given graph of 4 nodes using 3 colors
.

Node-1 can take the given graph of 4 nodes using 3 colors.

which are inside the circles
The state space tree will give all possible colors in that, the numbers
are nodes, and the branch with a number is the colors of the nodes.
State Space Tree:

7
 Analysis of Algorithm Chapter-5

Algorithm:
Algorithm mColoring(k)
// the graph is represented by its Boolean adjacency matrix G[1:n,1:n] .All assignments
//of 1,2,……….,m to the vertices of the graph such that adjacent vertices are assigned
//distinct integers are printed. ’k’ is the index of the next vertex to color.
{
repeat
{
// generate all legal assignment for X[k].
Nextvalue(k); // Assign to X[k] a legal color.
If (X[k]=0) then return; // No new color possible.
If (k=n) then // Almost ‘m’ colors have been used to color the ‘n’ vertices
Write(x[1:n]);
Else mcoloring(k+1);
}until(false);
}
Algorithm Nextvalue(k)
// X[1],……X[k-1] have been assigned integer values in the range[1,m] such that
//adjacent values have distinct integers. A value for X[k] is determined in the
//range[0,m].X[k] is assigned the next highest numbers color while maintaining
//distinctness form the adjacent vertices of vertex K. If no such color exists, then X[k] is 0.
{
repeat
{
X[k] = (X[k]+1)mod(m+1); // next highest color.
If(X[k]=0) then return; //All colors have been used.
For j=1 to n do
{
// Check if this color is distinct from adjacent color.
If((G[k,j]  0)and(X[k] = X[j]))
// If (k,j) is an edge and if adjacent vertices have the same
color. Then break;
}
if(j=n+1) then return; //new color found.
} until(false); //otherwise try to find another color.
}
 The time spent by Next value to determine the children is (mn)
 Total time is =(mn *n).

8
 Analysis of Algorithm Chapter-5

5.5 Hamiltonian cycles:


Let G=(V,E) be a connected graph with ‘n’ vertices. A HAMILTONIAN CYCLE
is a round trip path along ‘n’ edges of G which every vertex once and returns to its

starting position.

If the Hamiltonian cycle begins at some vertex V1 belongs to G and the vertex are
visited in the order of V1,V2…….Vn+1,then the edges are in E,1<=I<=n and the

Vi are distinct except V1 and Vn+1 which are equal.


Consider an example graph G1.

1 2 3 4

8 7 6 5

The graph G1 has Hamiltonian cycles:

->1,3,4,5,6,7,8,2,1 and
->1,2,8,7,6,5,4,3,1.

 The backtracking algorithm helps to find Hamiltonian cycle for any type of graph.
 The following graphs (figure A, B, and C) are not Hamiltonian cycle.
 In figure A Vertex 3 connected two graphs, so, the vertex is Articulate point It’s not
Hamiltonian Cycle
 In figure B Vertex 5, 6 are pendant vertex. So, It’s not Hamiltonian Cycles

Figure (A) Figure (B) Figure (C)

9
 Analysis of Algorithm Chapter-5

Procedure:
1. Define a solution vector X(Xi……..Xn) where Xi represents the I th visited
vertex of the proposed cycle.
2. Create a cost adjacency matrix for the given graph.
3. The solution array initialized to all zeros except X(1)=1,becuase the cycle should
start at vertex ‘1’.
4. Now we have to find the second vertex to be visited in the cycle.
5. The vertex from 1 to n are included in the cycle one by one by checking 2
conditions,
1. There should be a path from previous visited vertex to current vertex.
2. The current vertex must be distinct and should not have been visited earlier.
6. When these two conditions are satisfied the current vertex is included in the
cycle, else the next vertex is tried.
7. When the nth vertex is visited, we have to check, is there any path from nth vertex to
first 8vertex. if no path, the go back one step and after the previous visited node.
8. Repeat the above steps to generate possible Hamiltonian cycle.

Algorithm:(Finding all Hamiltonian cycle)

Algorithm Hamiltonian (k){
Loop
Next value (k)
If (x (k=0) then return;
{
If k=n then
Print (x)
else
Hamiltonian (k+1);
End if
}
Repeat
}
Algorithm Nextvalue (k){
Repeat{
X [k]=(X [k]+1) mod (n+1); //next vertex
If (X [k]=0) then return;
If (G [X [k-1], X [k]]  0) then
{
For j=1 to k-1 do if (X [j]=X [k]) then break;
// Check for distinction.
If (j=k) then //if true then the vertex is distinct.
If ((k<n) or ((k=n) and G [X [n], X [1]]  0)) then return;
}
} Until (false);
}

10
 Analysis of Algorithm Chapter-5

5.6 Knapsack Problem using Backtracking

 The problem is similar to the zero-one (0/1) knapsack optimization problem is

dynamic programming algorithm.
 We are given ‘n’ positive weights Wi and ’n’ positive profits Pi, and a positive
number ‘m’ that is the knapsack capacity, the is problem calls for choosing a subset
of the weights such that,

WiXi  PiXi is Maximized.

 m and
1in 1in

Xi Constitute Zero-one valued Vector.

 The Solution space is the same as that for the sum of subset’s problem.
 Bounding functions are needed to help kill some live nodes without expanding
them. A good bounding function for this problem is obtained by using an upper
bound on the value of the best feasible solution obtainable by expanding the given
live node.
 The profits and weights are assigned in descending order depend upon the ratio.

(i.e.) Pi/Wi  P(I+1) / W(I+1)

Solution:

After assigning the profit and weights, we have to take the first object weights and
check if the first weight is less than or equal to the capacity, if so then we include
that object (i.e.) the unit is 1.(i.e.) K 1.

Then we are going to the next object, if the object weight is exceeded that object does not
fit. So unit of that object is ‘0’.(i.e.) K=0.

Then we are going to the bounding function, this function determines an upper bound on
the best solution obtainable at level K+1.
 Repeat the process until we reach the optimal solution.

Algorithm:
Algorithm Bknap(k,cp,cw)
// ‘m’ is the size of the knapsack; ‘n’  no. of weights & profits. W[]&P[] are the //weights &
weights. P[I]/W[I]  P[I+1]/W[I+1].
//fwFinal weights of knapsack.
//fp final [Link].
//x[k] = 0 if W[k] is not the knapsack,else X[k]=1.
{ // Generate left child. If((W+W[k]  m) then
{
Y[k] =1;
If(k<n) then Bnap(k+1,cp+P[k],Cw +W[k])
If((Cp + p[w] > fp) and (k=n)) then
{
fp = cp + P[k];
fw = Cw+W[k];
for j=1 to k do X[j] = Y[j];
}
}

11
 Analysis of Algorithm Chapter-5

if(Bound(cp,cw,k)≥ fp) then

{
y[k] = 0;
if(k<n) then Bnap (K+1,cp,cw);
if((cp>fp) and (k=n)) then
{
fp = cp;
fw = cw;
for j=1 to k do X[j] = Y[j];
}
}
}
Algorithm for Bounding function:

Algorithm Bound(cp,cw,k)
 
// cp current profit total. //cw
current weight total.

//k the index of the last removed item.

//m the knapsack size.
{
b=cp;
c=cw;
for I =- k+1 to n do
{
c= c+w[I];
if (c<m) then b=b+p[I];
else return b+ (1-(c-m)/W[I]) * P[I];
}
return b;
}
Example:
M= 6 Wi = 2,3,4 4 2 2
N= 3 Pi = 1,2,5 Pi/Wi (i.e.) 5 2 1
Xi = 1 0 1
The maximum weight is 6

The Maximum profit is (1*5)
 + (0*2) + (1*1)
5+1

6.
Fp = (-1)
 1  3 & 0+4  6
cw = 4,cp = 5,y(1) =1
k = k+2
 2  3 but 7>6
so y(2) = 0
 So bound(5,4,2,6)
B=5
C=4
I=3 to 3
C=6

12
 Analysis of Algorithm Chapter-5

66
So return 5+(1-(6-6))/(2*1)
 5.5 is not less than fp.
So, k=k+1 (i.e.) 3.
3=3 & 4+2  6
cw= 6,cp = 6, y(3)=1.
K=4.
 If 4> 3 then
Fp =6,fw=6,k=3 ,x(1) 1 0 1
The solution Xi 1 0 1
Profit 6
Weight 6.

13
Analysis of Algorithm Chapter-5

14
 Analysis of Algorithm Chapter-5

BRANCH AND BOUND -- THE METHOD

The design technique known as branch and bound is very similar to backtracking (seen
in unit 4) in that it searches a tree model of the solution space and is applicable to a wide
variety of discrete combinatorial problems.

Each node in the combinatorial tree generated in the last Unit defines a problem state.
All paths from the root to other nodes define the state space of the problem.

Solution states are those problem states 's' for which the path from the root to 's' defines
a tuple in the solution space. The leaf nodes in the combinatorial tree are the solution states.

Answer states are those solution states 's' for which the path from the root to 's' defines
a tuple that is a member of the set of solutions (i.e.,it satisfies the implicit constraints) of
the problem.

The tree organization of the solution space is referred to as the state space tree.

A node which has been generated and all of whose children have not yet been generated
is called a live node.

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

A dead node is a generated node, which is not to be expanded further or all of whose
children have been generated.

13

15
 Analysis of Algorithm Chapter-5

Design and Analysis of Algorithm

Bounding functions are used to kill live nodes without generating all their children.

Depth first node generation with bounding function is called backtracking. State
generation methods in which the E-node remains the E-node until it is dead lead to branch-
and-bound method.

The term branch-and-bound refers to all state space search methods in which all children
of the E-node are generated before any other live node can become the E-node.

In branch-and-bound terminology breadth first search(BFS)- like state space search

will be called FIFO (First In First Output) search as the list of live nodes is a first -in-first
-out list(or queue).

A D-search (depth search) state space search will be called LIFO (Last In First Out)
search, as the list of live nodes is a list-in-first-out list (or stack).

Bounding functions are used to help avoid the generation of sub trees that do not
contain an answer node.

The branch-and-bound algorithms search a tree model of the solution space to get the
solution. However, this type of algorithms is oriented more toward optimization. An
algorithm of this type specifies a real -valued cost function for each of the nodes that appear
in the search tree.

Usually, the goal here is to find a configuration for which the cost function is
minimized. The branch-and-bound algorithms are rarely simple. They tend to be quite
complicated in many cases.

Least Cost (LC) Search:

In both LIFO and FIFO branch-and-bound the selection rule for the next E-node is
rather rigid and in a sense blind. The selection rule for the next E-node does not give any
preference to a node that has a very good chance of getting the search to an answer node
quickly.

Thus, in Example 8.1, when node 30 is generated, it should have become obvious to the
search algorithm that this node will lead to answer node in one move. However, the rigid
FIFO rule first requires the expansion of all live nodes generated before node 30 was
expanded.

The search for an answer node can often be speeded by using an "intelligent" ranking
function (.) for live nodes. The next E-node is selected on the basis of this ranking
function.

If in the 4-queens example we use a ranking function that assigns node 30 a better rank
than all other live nodes, then node 30 will become E-node, following node [Link]

16
 Analysis of Algorithm Chapter-5

14

17
 Analysis of Algorithm Chapter-5

Design and Analysis of Algorithm

remaining live nodes will never become E-nodes as the expansion of node 30 results in the
generation of an answer node (node 31).

The ideal way to assign ranks would be on the basis of the additional computational
effort (or cost) needed to reach an answer node from the live node. For any node x, this
cost could be

(1) The number of nodes on the sub-tree x that need to be generated before any
answer node is generated or, more simply,

(2) The number of levels the nearest answer node (in the sub-tree x) is from x

Using cost measure (2), the cost of the root of the tree of Figure 8.1 is 4 (node 31 is four
levels from node 1).The costs of nodes 18 and 34,29 and 35,and 30 and 38 are respectively
3, 2, and [Link] costs of all remaining nodes on levels 2, 3, and 4 are respectively greater
than 3, 2, and 1.

Using these costs as a basis to select the next E-node, the E-nodes are nodes 1, 18, 29,
and 30 (in that order).The only other nodes to get generated are nodes 2, 34, 50, 19, 24, 32,
and 31.

The difficulty of using the ideal cost function is that computing the cost of a node usually
involves a search of the sub-tree x for an answer node. Hence, by the time the cost of a
node is determined, that sub-tree has been searched and there is no need to explore x again.
For this reason, search algorithms usually rank nodes only based on an estimate (.) of
their cost.

Let (x) be an estimate of the additional effort needed to reach an answer node from x.
node x is assigned a rank using a function (.) such that (x) =f (h(x)) + (x), where h(x) is
the cost of reaching x from the root and f(.) is any non-decreasing function.

A search strategy that uses a cost function (x) =f (h(x)) + (x), to select the next e-
node would always choose for its next e-node a live node with least (.).Hence, such a
strategy is called an LC-search (least cost search).

Cost function c (.) is defined as, if x is an answer node, then c(x) is the cost (level,
computational difficulty, etc.) of reaching x from the root of the state space tree. If x is not
an answer node, then c(x) =infinity, providing the sub-tree x contains no answer node;
otherwise c(x) is equals the cost of a minimum cost answer node in the sub-tree x.

It should be easy to see that (.) with f (h(x)) =h(x) is an approximation to c (.). From
now on (x) is referred to as the cost of x.

Bounding:

18
 Analysis of Algorithm Chapter-5

A branch -and-bound searches the state space tree using any search mechanism in which
all the children of the E-node are generated before another node becomes the E-node.

We assume that each answer node x has a cost c(x) associated with it and that a minimum-
cost answer node is to be found. Three common search strategies are FIFO, LIFO, and LC.
A cost function ̂( ) such that ̂( ) ≤ ( ) is used to provide lower bounds on solutions obtainable from any node x. If upper is an upper bound on the cost of
a minimum-cost solution, then all live nodes x with > upper may be killed as all answer nodes reachable from x have cost c(x) >= ̂( )> upper. The starting value for
upper can be set to infinity.

Clearly, so long as the initial value for upper is no less than the cost of a minimum-
cost answer node, the above rule to kill live nodes will not result in the killing of a live
node that can reach a minimum-cost answer node. Each time a new answer is found, the
value of upper can be updated.

LC branch and bound and FIFO branch and bound of knapsack problem—
Refer to class notes

TRAVELLING SALESMAN PROBLEM

INTRODUCTION:
It is algorithmic procedures similar to backtracking in which a new branch is chosen and
is there (bound there) until new branch is choosing for advancing.

Travelling salesman is a minimization problem. It can be solved using Branch and bound
by generating state space tree by calculating cost and upper bound.

Reduced row or column: A row or column is said to be reduced if it has atleast one element
zero.
Reduced Matrix: A matrix is said to be reduced if all its row and columns are reduced.

Reducing a matrix: For reducing a matrix, we can reduce all its row and columns by
subtracting a smallest value in that tow and column from all its elements in the row or
column.

Cost function: If node S is a child of node R then

̂( ) = ̂( ) + ( , ) +

STEPS INVOLVED IN THIS PROCEDURE ARE AS FOLLOWS:

16

19
 Analysis of Algorithm Chapter-5

Design and Analysis of Algorithm

To find cost of any node:

1. Take a reduced matrix of its parent.

2. For (i,j), make row ‘i’ and column ‘j’ as ‘α’
3. Select location (j,i) as ‘α’

4.
̂( ) = ̂( ) + ( , ) +
Reduce the matrix and let cost of reduction be ‘r’.
̂( )
A(i,j) is the reduced matrix
R=cost of reduction

Example:
For the given cost matrix, apply LC branch and bound

∞ 20 30 10 11

15 ∞ 16 4 2

3 5 ∞ 2 4

19 6 18 ∞ 3

16 4 7 16 ∞

1. Row Reduced matrix

∞ 10 20 0 1
13 ∞ 14 2 0
1 3 ∞ 0 2
16 3 15 ∞ 0
12 0 3 12 ∞
Reduction on rows=10+2+2+3+4

2. Column Reduced matrix

∞ 10 17 0 1
12 ∞ 11 2 0
1 3 ∞ 0 2
15 3 12 ∞ 0
11 0 0 12 ∞
Reduction on columns=1+0+3+0+0

20
 Analysis of Algorithm Chapter-5

R=10+2+2+3+4+1+0+3+0+0=25

3. Cost of node ‘2’ is

A(i,j)=A(1,2)=10

Make all elements in row-1and column-2 as α and A(2,1) as α in the previous reduced
matrix.
∞ ∞ ∞ ∞ ∞
∞ ∞ 11 2 0
1 ∞ ∞ 0 2
15 ∞ 12 ∞ 0
11 ∞ 0 12 ∞

No need to reduce as

Every row and column has ‘0’. Therefore ‘r’=0

  ̂(2) = ̂(1) + (1,2) +
=25+10+0=35

4. Cost of node ‘3’ is

A(i,j)=A(1,3)=17

Make all elements in row-1and column-3 as α and A(3,1) as α in the previous reduced
matrix.
∞ ∞ ∞ ∞ ∞
12 ∞ ∞ 2 0
∞ 3 ∞ 0 2
15 3 ∞ ∞ 0
11 0 ∞ 12 ∞
Reduce rows and columns
∞ ∞ ∞ ∞ ∞
1 ∞ ∞ 2 0
∞ 3 ∞ 0 2
4 3 ∞ ∞ 0
0 0 ∞ 12 ∞

Reduction factor ‘r’=11

̂ ̂
(3) = (1) + (1,3) +

18
21
 Analysis of Algorithm Chapter-5

Design and Analysis of Algorithm

=25+17+11=53

5. Similarly cost of node 4 is 25

6. Cost of node 5 is 31
7. The least cost among nodes 2,3,4,5 is with node 4 i.e, 25
8. Extend node 4 by taking the node-4 matrix as the matrix for consideration and
generate the following tree and the final path is 1-4-2-5-3-1 and the total path cost
is 28.

1
C=25

5
2 3 4 C=31
C=35 C=53 C=25

2 3 5
C=50
C=28 C=36

3 5
C=52 C=28

3
C=28

22
 Analysis of Algorithm Chapter-5

19

23
 Analysis of Algorithm Chapter-5

Design and Analysis of Algorithm

EXERCISE: Given graph G, apply the LC branch and bound

5
1
9 19
25
5 2
1
50
15
6

4 3

MATRIX:

1 2 3 4 5
 25 40 31 27
1
5  17 30 25
2
19 15  6 1
3
9 50 24  6
4
22 8 7 10 
5

Final result:
3—2—1—4—5—3

Cost is 15+15+31+6+7=64
Short answer questions:
1. What is Lower-Bound theory?
2. State graph coloring problem.
3. What is Hamiltonian cycle?
4. What is branch and bound?
5. Write the control abstraction of LC-search.
Long answer questions:
1. Explain Branch and Bound. Give LCBB solution for the following knapsack
instance n=4, (P1,P2,P3,P4)=(10,10,12,18), (W1,W2,W3,W4)=(2,4,6,9) and
m=15.
2. Explain Branch and Bound Technique? Give an Example.
3. Explain travelling sales person problem with an example.
24
 Analysis of Algorithm Chapter-5

4. Explain LC Branch and Bound.

5. Write a recursive backtracking algorithm to find all the Hamiltonian cycles of a
given graph.
6. Explain FIFO Branch and Bound.
7. Explain graph coloring problem.
8. Explain the terms FIFO branch and bound, LC branch and bound and LC search.
9. Write the differences between backtracking and branch-and-bound techniques.
10. Write short notes on
a. M-coloring problem
b. 8-queens problem

25