Unit – IV

Back tracking:- 8-queen’s problem, Graph coloring, Hamiltonian

cycles, Knapsack problem
Branch and bound:- 0/1 knapsack problem, Traveling salesperson
problem.

Q) Define the terms: State space, Problem state, solution state,

answer state, live node, E-node, dead node, bounding function,
explicit constraints, implicit constraints.
Ans:-
State Space:- All paths from root to other nodes define the state space of
the problem.
Problem state:- Each node in the tree defines a problem state.
Example:
Fig..

Solution state:- The solution states are those problem states S for which
the path from root to S defines a tuple in the solution space.
Example:-

For the above solution space, the solution states represented in the form of
a triple i.e.,(1,3,6) (1,3,7) are the solution states.
Answer state:- Answer states are those solution states for which the path
from root to the solution state defines a tuple that is in member of set of
solution of the problem.
Live node:- A node which has been generated and all children not yet
been generated is called a live node.

B
Example:-

This node B is live node since the children of this node are not yet
generated.
E-node:- The live node whose children are currently being expanded is
called E-node.
Dead Node:- A dead node is generated node which is not to expand
further or all of whose children have been generated.
Bounding Function:- This is a function which is used to kill live nodes
without generating all their children.
Explicit constraints:- These are rules which restrict each x i to take on
values only from a given set.
Example:-
1. In knapsack problem, the explicit constraints are x i=0 or 1 and
0xi1.
2. In 4 queens problem, 4 queens can be placed in 44 chess board in
44 ways.

Q) Write the control abstraction of back tracking using recursive

approach? (Dec. 05,Q7(a)
Q) Explain the technique of back tracking with the help of an
example? (Oct-99, Q7(a)
Ans: -
Back tracking is one of the fundamental principle of algorithm
design technique. In this technique we search for the set of
solutions or optimal solution which satisfies some constraints. The
desired solution is expressed as an n tuple (x 1, x2, …. Xn) where xi
is chosen from some finite set si. The solution maximizes or
minimizes or satisfies a criterion function (objective function) C
(x1, x2, …. Xn). The basic idea of back tracking is to build up a
vector, one component at a time and to test whether the vector
being formed has any chance of success. The major advantage of
this algorithm is that we can realize the fact that partial vector
generated does not lead to an optimal solution. In such a situation
that vector can be ignored. The back tracking algorithm determine
the solution by systematically searching the solution space for the
given problem. All solutions using back tracking are required to
satisfy or complex set of constraints. The constraints may be
explicit and implicit.

 Explicit constraints are rules thalt restrict each x i to take on

values only from a given set.
 Implicit constraints are rules which determine which of the
tuples in the solution space satisfy the criterion function.

CONTROL ABSTRACTION FOR BACKTRACKING: -

It is also called general scheme for backtracking, is given below

Algorithm Backtrack(n)
{
k: =1;
while (k0)do
{
if there remains an untried x[k]T(x[1], x [2] … X[k-
1])and
Bk (x(1), x(2)….x(k)) then
{
 if (x[1], x[2], …. X[k] is a path to an answer then write
(x[1:k]);
k: = k+1
}
else
K: = k-1
}
}

Q) Explain the technique of backtracking with the help of 4-equuns

problem? (Sep.200, Q7(a)
Q) Draw the state space tree organization for 4-queens problem
and explain how backtracking can be used to find the solution.
Mark the sequencing of models expanded in the state tree?
(Sep/Oct. 98, Q7)

Answer: -
Consider a 4x4 chess board. Let there are 4 queens. The objective
is to place there 4 queens on 4x4 chess board in such a way that
no two queens should be placed in the same row, same column or
diagonal position. The explicit constraints are 4 queens are to be
placed on 4x4 chess board in 4 4
ways. The implicit constraints are
no two queens are in the same row or column or diagonal.

Let { x1, x2, x3, x4} be the solution vector where xi represents the
column number on which the queen i is to be placed.

 First queen Q, is placed in first row and first column.

Q1

 The second queen should not be placed in first row and second
column. It should be placed in second row and in second, third
 or fourth column. If we place in second column, both will be in
same diagonal, so place it in third column.

Q1
Q1 . . are
Q2
 We unable
. . Q2 . . . .
it some where else

Q1 Q1
 Q2 Q2 Now the fourth queen
Q3
should be placed in 4th
row and 3rd column but there will be a diagonal attack from Q 3.
So go back remove Q3 and place it in the next column. But it is
not possible, so move back to Q 2 and remove it to next column
but it is not possible. So go back to Q 1 and move it to next
column. It can be shown as follows.
Hence the solution to 4 queens problem is x 1=2; x2 = 4; x3=1; x4
=3.
i.e. first queen is placed in 2 nd column, second queen is placed in
4th column, third queen is placed in first column and fourth queen
is placed in third column.
Q Q Q Q
1 1 1 1
Q2 Q2 Q2
Q Q
3 3
Q4
The state space tree for the given problem is
Q) State and explain 8 queens problem? (Nov.06, July-05)
Q) Describe about 8 queens problem? (Jan -03, Q7(a)
Q) Write back tracking algorithm for 8 queens problem?
Ans: -
Consider a 8x8 chess board. Let there are 8 queens. The objective
is to place these 8 queens on the board so that no two queens are
on the same row or same column or same diagonal.

Let (x1, x2, … x8) represent a solution in which the queen i is

placed in the same column.

Let A [1:8, 1:8] be the 2x2 array representing the squares of chess
board. To queens are numbered 1 through 8. Each queen must be
on a different row.

The explicit constraint is 8-queens are to be placed in 8x8 chess

board in 88 ways. We reduce the solution space of explicit
constraints by applying the implicit constraints.
The implicit constraints are no two queens are in the same row, or
column or diagonal.

Suppose (i,j) and (k,l) are the two positions for two queens. They
are on the same diagonal iff
j-l  = i-k 

A typical solution to 8 queens problem is

Q1
Q2

Q3

Q4

Q5
Q
6

Q7

Q8

The solution is (x1, x2, x3, x4, x5, x6, x7, x8) = (4,6,8,2,7,1,3,5)

TIME COMPLEXITY: -
The solution space tree of 8 queens problem contain 8 8 tuple. After
imposing implicit constraints, the size of solution space reduced to
8! Tuples. Hence the time complexity is 0 (8!). For n-queens
problem, it is 0(n!).

Q) Write and explain the recursive backtracking algorithm of N-

queens problem? (Dec.2005)
Q) Write an algorithm which gives all solutions to the n-queens
problem? (Fen.2005)
Q) Write and explain the n-queens algorithm, solve using DFS
strategy. Derive its timing complexity? (Aug. 2004)
Q) Write and explain n-queens algorithm? (Sep. 2003)
Q) Write an algorithm to generate all solutions to the n-queens
problem. (Sep.2000, Oct.99)
ALGORITHM FOR n-QUEENS PROBLEM: -
Algorithm place (k,i)
//returns true if a queen can be placed in kth row and
//ith column. other wise 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 ((n[j] = i) = Abs (j-k)))//or in the same diagonal then return
false;
} return true;
Algorithm N queens (k,n)
//using backtracking, this procedure points all
//Possible placements of n queens on an nxn
//chessboard so that they are nonattacking
{ for i: = 1 to n do
{
if place (k=n) then write (x[1:n]); else N queens (k+1, n);
}
}
}
Graph Colouring: -

Q) Explain map Colouring problem and write an algorithm to find

all m-colourings of a graph (May/June 2007)
Q) Write an algorithm for finding all m-colourings for the graph –
colouring problem? (June 2006)
Q) Write the algorithm to find all m-colourings of a graph (Feb.04)
Q) Explain the logic involved in graph colouring problem (January
2003)
Q) What is meant by chromatic no. of a graph? (October 99)
Ans: -

Let ‘G’ be a graph and ‘m’ be a positive integer. The ‘m’

colorability optimization problem requires the smallest integer m
for which the graph ‘G’ can be colored so that no two adjacent
vertices have the same color. Such a minimum +Ve integer ‘m’ is
called as chromatic number and the graph is said to be ‘m’
colorable.

Eg: - A complete graph of order ‘n’ is n colorable.

4 1 4 3

2 3
1 2
A graph is said to be planar iff it can be drawn in a plane in such a
way that no two edges cross each other.

A map can be converted into a planar graph using the following

steps.

1) Take each region in the map as a vertex in the graph.

2) If two regions have a common boundary then places an edge
between the corresponding vertices.
1
Ex: -
4 5
2
2 3

3 4
5
Fig: - A map and its planar graph representation. The above graph
requires 4 colors.
Algorithm m coloring (k)
//This algorithm was formed using the recursive
//back backing schema. 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 assignments for x[k]
nextvalue (k); //assign to x[k] a legal color
if (k=n) then //atmost m colors have been used
//to color the n vertices
write (x[1:n]);
else mcoloring (k+1);
}until(false);
}
Algorithm next value (k)
//x[1], …., x[k-1] have been assigned integer values in
//the range [1,m] such that adjacent vertices have
//district integers. A value for x[k] is determined in
//the range [o,m]. x[k] is assigned the next
//highest numbered color while maintaining
//distinctness from the adjacent vertices of vertex k
//if no such color exists, then x[k] is o.
{
Repeat
{
x[k]: - (x[k]+1) mad (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 distinet from adj.colors
if ((G[k,j]0) and (x[k]=x[j]))
//if [k,j] is an edge and if adj.vertices have
//the same color
Then break;
}
if (j=n+1) then return; //new color found
} until (false); //otherwise try to find another color
}
q) Generate all possible 3 coloring for the following graphs with 4-
nodes using a state space. (feb.2004)
1 2

4 3
Hamiltonian Cycles: - (HC)
Q) Explain what is a Hamiltonian cycle? (Jan.2006)
Q) Briefly explain about Hamiltonian cycle? (Jan. 2003)
Q) What is a HC? Give an example? (July 2005)
Q) What is a HC? Give an example for the same? (Oct.99)
Q) Write a recursive back tracking algorithm to find all the HC’s of
a given graph? (Nov.2006, July 2005)
Q) Write an algorithm for finding HC of a graph? (Feb. 2005)
Q) What is a HC? Write a recursive back tracking algorithm to find
all the HC of a given graph? (Feb.2004)
Q) Develop an algorithm for finding minimum cost HC in a given
connected graph using back tracking porinciple? (Apr/May 2007)
Q) Develop a recursive backtracking algorithm to find the least
cost HC in a given connected graph? (April 2000)
Q) Define the term HC and explain the back tracking algorithm for
finding all the HC in a given graph? (April 1998)

Ans: -
Let G = (V,E) be a connected graph consisting of n vertices. A HC is
a round trip path along n edges of G that visits every vertex once
and returns to its starting position.

Example: - Consider the graph

2 3

4 5

The HC is 1-2-4-6-5-3-1. To determine whether a given graph contains a HC

or not, we use back tracking technique.

Let [X1, X2, …., Xn] be the solution vector where X i is the ith visited vertex of
the proposed H.C. We have to determine how to compute the set of
possible vertices for Xk if X1, X2, …. Xk-1 have been already chosen.

If k=1, the X1 can be any of the n vertices. To avoid printing same cycle n
times, we require that X1 = 1 (i.e. the vertex is selected). If 1<k<n, then X k
can be any vertex v which is distinct from X 1, X2, …. Xk-1 and v is connected
by an edge to Xk-1. The vertex Xn can only be the one remaining vertex and
it must be connect5ed to both Xn-1 and X1.

Algorithm Hamiltonian (k)

//This algorithm uses the recursive formulation of
//back tracking to find all the H cycles of a graph
//The graph is stored as an adjacency matrix
// G[1:n, 1:n]. All cycles begin at node 1
{
 repeat
{ //generate values for x[k]
next value (k); //Assign a legal next value to x[k]
if (x[k]=0) then return;
if (k=n) then write (x[1:n]);
else
hamiltonian (k+1)
}until (false);
}
Algorithm next value (k)
//x[1:k-1] is a path of k-1 distinct vertices if x[k] =0
//then no vertex has as yet been assigned to x[k]
//After execution, x[k] is assigned to the next
//highest numbered vertex which does not already
//appear in x[1:k-1] and is connected by an edge
//to x[k-1] . otherwise x[k] – 0. If k=n, then in
//addition x[k] is connected to x[1]
{
Repeat
{
x[k]: = (x[k]+1) mad (n+1); // next vertex
if (x[k] = 0) then return;
if (G[x[k-1], x[k]] 0) then
{ // is there an edge?
for j: = 1 to k-1 do
if (x[j]=x[k]) then break;
//check for distinctness
if (j=k) then //if true, then vertex is
//distinct
if ((k<n) or ((k=m) and
g[x[n], x[1]]  0))
then return;
 }
}

KNAPSACK PROBLEM: -

Q) Give a backtracking solution to the 0/1 Knapsack problem? (Feb. 2005)

Q) Solve the following instance of 0/1 Knapsack problem
P = (11,21,31,33,43,53,55,56)
W = (1,11,21,23,33,43,45,55)
M = 110
N=8
Ans: -

The solution space consists of the “2” distinct ways to assign zero and one
values to the x’s. Bounding functions are used to kill those live nodes which
are not to be expanded. 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 and any of its descendents. If
this upper bound is not higher than the value of the best solution
determined so far then that live node may be killed.

The bounding function is derived as follows:

If at node Z the values of x i, 1 i  k have already been determined, then

an upper bound for Z can be obtained by relaxing the requirement x i = 0 or
1 to 0  xi  1 for k+1  I V n and using a greedy algorithm.

Function Bound (cp, cw, k) determines an upper bound on the best solution
obtainable by expanding any node Z at level k+1 of the state space tree.
The object weights and profits are w[i] and p[i]. It is assumed that

, 1  i <n

Algorithm Bound (cp, cw, k)

//cp is the current profit total, cw is the current
//weight total; k is the index of the last
//removed item; and m is the knapasacksize
{
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;
}
Algorithm Bknap(k,cp,cw)
// m is the size of the knapsack; n is the number of
//weights and profits. W[ ] and p[ ] are the weights &
//profits. P[j]/w[i]  p[i+1]/w[i+1]. fw is the final
//weight of knapsack; fp is the final maximum
//profit. X[k] = 0 if w[k] is not in the knapsack;
//else x[k]=1
{
//generate left child
if (cw+w[k]  m) then
{
y [k]: = 1;
if (k<m) then Bnap (k+1, cp+p[k], cw+w[k]);
if ((cp+p[k] >fp) and (k=n)) then
{
fp: = (p+p[k];
fw : = cw+w[k];
for j: = 1 to k do x[j]: = y[j];
}
}
 //generate right child
if (bound(cp,cw,k)  fp) then
{
y[k] : = 0;
if (k<n) then
Bknap (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];
}
}
}

SOLUTION FOR THE PROBLEM: -

The greedy solution corresponding to the root node is X =

{1,1,1,1,1,21/45,0,0}. Its value is 164.88.

 The two sub trees of the root correspond to X 6 = 0 and X6 = 1

respectively. The greedy solution at node 2 is X =
{1,1,1,1,1,0,21/45,0}. Its value is 164.66.
 The fig. below shows the tree that gets generated as various choices are
made for the vector i. the i th level of the tree corresponds to an
assignment of one or zero to y(i), either including or excluding the
weight w(i).
 The two numbers contained in a node are the weight (cw) and profit (cp)
given the assignments down to the level of the node.

Q) What is branch-and-bound technique? Give an example? (Nov. 2007,

Q7(a)
Q) What is branch-and-bound strategy? Explain? (July 2005, Q8(a)
Q!) Explain the branch and bound strategy with the help of an example?
(Sep.2000, Q8)
Q) Explain the technique of branch-and-bound with the help of an example?
(Oct. 99, Q8(c)
Ans: -
The back tracking algorithm is effective for decision problems. But it is not
designed for optimization problems. This drawback is rectified in branch
and bound technique. Here also we use bounding functions similar to back
tracking. The essential difference between back tracking and branch and
bound is – if we get a solution then we will terminate the search procedure
in backtracking, where as in branch and bound we will continue the process
until we get an optimal solution.

A branch and bound method searches a state space tree using a

mechanism in which all the children of the e-node are generated before
another node becomes e-nod.

The technique generally searches a solution space using three search

techniques FIFO, LIFO and LC (Least Cost).

FIFO: - BFS like state space search will be called FIFO search because the
list of live node is a first in first out.

LIFO: - A d-search like state space search will be called LIFO search
because the list of live node is last in first out list.

LC: -

 In this method a space tree of possible solutions is generated. Then

partitioning is done at each node of the tree. We compute lower and
upper bound at each node. This leads to selection of answer node.
 Bounding functions are used to avoid generation of subtrees that do not
contain an answer node.
Example: - Assume there is a problem ‘x’ for which state space tree
generated is as follows.

2 3 4

5 6 7 8 9
B B B

10 1 12
B 1B
Assume that node 12 is the answer node.
FIFO SEARCH: -
 In FIFO search first we will take node 1 as e-node. Then we generate the
children of node 1. All these live nodes are placed into a queue.
2 3 4

 Delete an element from queue i.e. node ‘2’. Generate the children of
node two and place it on to the queue.
3 4 5 6

 Delete node ‘3’ and generate its children. The children of ‘3’ -7 and 8
are killed by the bounding functions (since they do not lead to answer
node). So they are not placed into the queue.
4 5 6
 Delete node ‘4’ and the child of ‘4’ is ‘9’. ‘9’ is killed by the bounding
function and hence is not added into the queue.
5 6
 Delete node ‘5’ children of 5 are 10 & 11. They are killed by bounding
function.
 6
 The last node is ‘6’ and its child 12 satisfied the condition of the problem
which is the answer node. So the search terminates.
LIFO SEARCH: -
 Generate children of node ‘1’ and place them into stack.

3
2
 Remove the top most elements from the stack and its child ‘9’ is
generated and killed by the bounding functions.

3
2
 Remove the next top most element i.e. 3 and its children 7 and 8 are
generated and killed by the bounding functions.

2
 Pop 2 from stack and push its children 5 and 6 into the stack.

6
5
 Delete top element ‘6’ and generate its child 12 which is the answer
node. So the search process terminates.

LC SEARCH: -
In this we use ranking function or cost function which is denoted by .

we generate the children of E-node and among those line nodes we select
a node which has minimum cost.

Ranking function is used to calculate the cost of each node.

Fig: -

 Node ‘1’ is the e-node. The children of node 1 i.e. 2,3 and 4 are
generated.
 We select node 2 because its cost is minimum.
 The children of ‘2’ i.e. 5 and 6 are generated.
 Node 6 is selected because its cost is minimum.
 The children for node ‘6’ i.e. 12 and 13 are generated and the cost of 12
is minimum and it is the answer node. The search terminates.

Q) Give the state space tree generated in the process of FIFO branch and
bound search method for 4-queens problem. (November 2007)
Ans: -
Initially there is only one live node, node 1. This represents the case in
which no queen has been placed on the chess board. This node becomes
the e-node. It is expanded and its children nodes 2,3,4,5 are generated.

 These nodes represent a chess board with queen 1 in row 1, and

columns 1,2,3 and 4 respectively.

Fig: -

 The only live nodes now are 2,3,5 and 5. If the nodes are generated in
this order, then the next e-node is node 2. It is expanded and nodes 6,7
and 8 are generated. Node 6 is immediately killed using the bounding
functions.
 Nodes 7 and 8 are added to the queue of live nodes.
 Node 3 becomes the next E-node.
 Nodes 9,10 and 11 are generated.
 Nodes 9 and 10 are killed as a result of the bounding functions.
 Node 11 is added to the queue of live nodes and soon.

Q) What is LC-Search? Give control abstraction for LC search. (March 2001)

Q) What is least cost search? Explain briefly how a problem is solved using
LC-Search mechanism. (Dec. 2005)

Ans: -

In Branch and bound method the basic idea is selection of E-node. In FIFO
& LIFO methods the selection of E-node is very complicated. The search for

an answer node can be speeded up by using a ranking function for

live nodes.

 Each time the next E-node is selected on the basis of this function.
 For this ranking function additional computation is needed to reach to
answer node from the live node.
 For any node cost could be the no. of levels the nearest answer node is
from x.
 The difficulty with using either of these ideal cost function is that
computing the cost of a node usually involves a search of the sub tree x
for an answer node.

 Let be an estimate of the additional effort needed to reach an

answer node from x and h(x) be the cost of reaching x from root and
f(x) be any non-decreasing function, such that

= f(h(x)) +

 A search strategy that uses a cost function to select the next E-

node would always choose for its next E-node a live node with least

such a strategy is called an LC search.

CONTJROL ABSTRACTION: - Let t be a state space tree and C() be a cost
function for the nodes in t. If x is a node in t, then C(x) is the minimum cost
of any answer node in the subtree with root x.

 C(t) is the cost of min. cost answer node in t. Usually it is not possible to

find an easily computable function C(). An estimate C() is used. It is

easy to compute and has the property that if x is either an answer

node or node then C(x) = .

 A LCBB search of tree uses two functions least () and add (). Begin with
an upper bound with  and node 1 as the first node. When node 1 is
expanded nodes 2,3,4… are generated in the order. Add a live node to
the list of live nodes if the function least () finds least cost node and the
node is deleted.

From the list of live nodes and returned. The output of least cost search is
tracing the path from the answer node to the root node of the tree.
Algorithm LC search (t)

{
if (t is an answer node) then
{
write (t);
return;
}
Et;
repeat
{
for (each child x of E) do
{
 if (x is answer node) then
{
output the path from x to t;
return;
}
Add(x);
X parent  E //pointing the path from x to root;
}
If (no more live nodes) then
{
write (“No answer node”)
return;
}
Eleast ();
} outil(false);
}

PROPERTIES OF LC SEARCH: -

1) It is desirable to find an answer node that has minimum cost among

all answer nodes. But LC search can not guarantee to find an answer
node G with minimum cost C.
2) Where there exist is two nodes in a graph such that C(x) > C(y) in
one branch while C(x) < C(y), (CCy) < c(y)) in other branch, LC
search can not find minimum cost answer node.
3) Even if C(x) < C(y) for every pair of nodes (x,y) such that c(x) < c(y),
LC may not find a minimum cost answer node.

4) When the estimate () for a node is less than cost c() then a slight

modification to the LC search results in search algorithm that

terminates when a minimum cost answer node is reached. In this
modification, the search continues until an answer node becomes E-
node.
Q) Discuss the features of 0/1 knapsack problem? (July 2002)
Q) Describe a method of solving 0/1 knapsack problem using LC branch
and bound method? (April 99)
Ans: -

The 0/1 knapsack problem states that, there are n objects given and
capacity of knapsack is m. Then select some objects to fill the knapsack in
such a way that it should not exceed the capacity of knapsack and max.
Profit can be earned.

The 0/1 knapsack problem can be stated as

Max Z = P1 X1 + P2 X2 + …. + Pn Xn
s.t.c
W1X1+W2X2+ … + WnXn  m
Xi = 0 or 1.
A branch and bound technique is used to find solution to the knapsack
problem. But we can not directly apply the branch and bound technique to
the knapsack problem, because the branch and bound deals only the
minimization problems. After minimization the modified problem is

Min Z =- P1 X1 - P2 X2 + …. - Pn Xn
s.t.c
W1X1+W2X2+ … + WnXn  m
Xi = 0 or 1.

Let and are the two cost functions such that  c(x)  ,

satisfying the requirements where c(x) = -

 The c(x) is the cost function for answer node x, which lies between two
functions called lower and upper bounds for the cost function c(x). The
search begins at the root node. Initially we compute the lower and

upper bound at root node called and . Consider the first

variable x, to take a decision. The X 1 tales varies 0 or 1. Compute the

 lower and upper bounds in each case of the variable. These are the
nodes at the first level. Select the node whose cost is min. i.e.

(cx) = min{c(lchild(x)), c(rchild(x))}

((1) = min { , }

The problem can be solved by making a sequence of decisions on the

variables X1, X2, …. Xn level wise. A decision on the variable X i involves
determining which of the values 0 or 1 is to be assigned, to it by defining
c(x) recursively.

The path from root to the leaf node whose height is max. is selected and is
the solution space for the knapsack problem.
Algorithm LU bound (p, w, rw, rp, n, k, LBB, UBB)
//p is array of profit values, w is array of weights
//rw is remaining weight, rp is remaining profit
//n is no. of objects, k is object
//LBB is lower bound, UBB is upper bound
{
LBB  rp; c rw
for i k to n do
{
if (c<w(i)) then
{
UBB  LBB+c*p(i)/w(i);
for j i+1 to n do
{
if (cw(i)) then
c c-w(i);
LBB  LBB+p(j);
}
}
cc-w(i);
 LBB  LBB;
}

Q) Distinguish between fixed tuple sized and variable tuple sized state
space tree organizations?
Ans: -
Variable tuple sized Fixed tuple sized organization
organization
1) The tuple size is variable in this 1) The tuple size is fixed in this type
type of state space tree of tree organization
organization 2) Edges can have the weights zero
2) Edges can have different or one.
weights. 3) It is independent of the problem
3) It is dependent of the problem instance being solved. Fixed tuple
instance being solved variable sized organization.
tuple sized organization 4) The tree organization is
4) The tree organization is determined statistically as the
determined dynamically as the solution space is being searched.
solution space is being searched.

Q) Draw a portion of the state space tree generated by LCBB for the
following knapsack problem. n = 5, (P1, P2, P3, P4, P5) = (10,15,6,8,4)
(W1, W2, W3, W4, W5) = (4,6,3,4,2) and
m = 12. Assume fixed-size tuple formulation?
(March 2001, May/June-07, August 04)
Ans: -
Hence, the solution is (X1, X2, X3, X4, X5) = (1,1,0,0,1)

Q) Draw the portion of state tree generated by LC knap for the knapsack
instance
n =4; (P1, P2, P3, P4) = (10,10,12,18)
(W1, W2, W3, W4) = (2,4,6,9) and m = 15
Ans: -
Knapsack is a maximization problem, but branch and bound technique is
applied for minimization problem only. To convert the problem into
minimization, take – ve signs for profits.

(P1,P2,P3,P4) = (-10, -10, -12, -18)

In branch and bound technique, we calculate lower bound and upper bound
for each node.

FOR NODE -1:

 Place first item in bag i.e. rem. Weight is 15-2=13 second item is place
and then third item, rem. Weight is 13-(4+6)=3. Since fractions are not
allowed in calculation of upper bound, so we can not place fourth item
in bag.
 Profit earned = -10-10 -12= -32 = upper bound.
 To calculate lower bound, place fourth item in a bag since fractions are
allowed.

Lower bound = -10-10-12- = -38

= -32

= 32

FOR NODE -2: - x1 =1 MEANS WE SHOULD PLACE FIRST ITEM IN THE BAG.

= -10-10-12- = -38

= -10-10-12 = -32

FOR NODE -3: - X1 = 0

It means we should not place first item in the bag

= -10-12- = - 32

= -10-12 = - 22

X1 =1 X1 =0
2 3

 Select the minimum of lower bounds i.e. min{ } = min {-38,-

32} =
 = -38 =

 Choose the node 2 to be exponded.

 First object is selected i.e. X1 = 1
Consider the second variable to take the decision at second level.

FOR NODE -4: - X2 = 1

= -10-10-12- = -38

= -10-10-12 = - 32

FOR NODE -5: X2 = 0

= -10-12- = -36

= -10-12 = - 22

 min { , } = min {-38, -36} = -38

 Node 4 is selected
 Second object is selected i.e. X2 = 1

1
X1 =1 X1 =0

22 3
X2 =1 X2 =0

44 5
5

Consider the third variable (X3): -

FOR NODE -6: - (X3 =1)

= -10-10-12 = - 32

= -10-10-12- 6 = - 38
FOR NODE -7: - X3 = 0

= -10-10-18 = - 38

= -10-10-18 = - 38

Since the lower bounds are same, select the minimum of upper bounds.

Min { , } = Min {-32, -38} = -38

 Node 7 is selected i.e. X3 = 0

FOR NODE -9: - X4 = 0

= -10-10 = - 20

= -10-10 = - 20

Min { , } = min {-38, -20} = -38

 Node 8 is selected and 9 is discarded.

 X4 = 1
Path is 1 2  4  7  8
The solution for 0/1 knapsack problem is (X1, X2, X3, X4) = (1,1,0,1)
Max. Profit = 10x1+10x1+12x0+18x1

TRAVELLING SALESPERSON PROBLEM: -

Q) Explain how the traveling salesperson problem is solved using LC

branch and bound.
Q) Explain the method of reduction to solve TSP problem using branch and
bound.
Q) Solve the following instance of traveling salesperson problem using
LCBB.

1 2 3 4 5
1  20 30 10 11
2 15  16 4 2
3 3 5  2 4
4 19 6 18  3
5 16 4 7 16 

Row reduction:
 20 30 10 11 10  20 20 0 1
15  16 4 2 2 13  14 2 0
3 5  2 4 2  1 3  0 2
19 6 18  3 3 16 3 15  0
16 4 7 16  4 12 0 3 12 
_____
21
_____
Row reduction:
 10 20 0 1  10 17 0 1
13  12 2 0 12  11 2 0
1 3  0 2  0 3  0 2
16 3 15  0 15 3 12  0
12 0 3 12  11 0 0 12 
1 - 3 - - =4

Total amount subtracted, r = 21+4 = 25

1 25

35
53 5 31
2
3 4 25
Consider the path (1,2)
Change all entries of 1st row and 2nd column of reduced matrix to , & set A
(2,1) = 
    
  11 2 0
0   0 2
15  12  0
11  0 12 
Apply row reduction and column reduction
r=0

= + A(1,2)+r = 25+10+0 = 35

Consider the Path (1,3)

Change all entries of first row & 3rd column of reduced matrix to  and set A
(3,1) = 
    
12   2 0
 3  0 2
15 3   0
11 0  12 
Apply row reduction and column reduction, r= 11

= + A(1,3)+r = 25+17+11 = 53

Consider the Path (1,4)

Change all entries of 1st row & 4th column of reduced matrix to  and set A
(4,1) = 
    
12  11  0
0 3   2
 3 12  0
11 0 0  
Apply row reduction and column reduction, r= 0
 = + A(1,4)+r = 25+0+0 = 25

Consider the Path (1,5)

Change all entries of 1st row & 4th column of reduced matrix to  and set A
(4,1) = 
    
12  11 2  2
0 3  0 
15 3 12   3
 0 0 12  __
5

= + A(1,5)+r = 25+1+5 = 31

Since the minimum cost is 25, select node 4. The matrix obtained for r path
(1,4) is considered as reduced cost matrix
    
A= 12  11  0
0 3   2
 3 12  0
11 0 0  

Consider the path (4,2)

Change all entries of 4th row and 2nd column to A to  and set A (2,1) to 
    
  11  0
0    2
    
11  0  

Apply row reduction and column reduction, r=0

 = + A(4,2)+r = 25+3+0 = 28

Consider the path (4,3)

         
12    0 1    0
 3   0   1   0
         
11 0    0 0   

11 r = 2+11 =
13 = 25+12+13 = 50

= + A(4,3)+r

Consider the path (4,5)

Change all entries of fourth row and fifth column to  and set A(5,1) to 
    
12  11   Apply row reduction and column
reduction
0 3   
    
 0 0  

    
1  0  r= 11+0 = 11
0 3   
    
 0 0  

= + A(4,5)+r = 25+0+11 = 36
1

Since the min. cost is 28. Select node 2.

2 3 4 5

2 3 5

3 5
 35 53 25 31

28 50 36

The matrix obtained for path (4,2) is considered as reduced cost matrix.

    
  11  0
A= 0    2
    
11  0  

Consider the path (2,3)

Change all entries of second row and third column to  and set A (3,1) to 
    
    
    2
    
11    

Apply row reduction and column reduction.

    
    
    0 r = 2+11 = 13
    
0    
 = + A(2,3)+r = 28+11+13 = 52

Consider the path (2,5)

Change all entries of second row and fifth column to  and set A (5,1) to 
    
    
0     r=0
    
  0  

= + A(2,5)+r = 28+0+0 = 28

Since the min. cost is 28, select node 5.

The matrix obtained for path (2,5) is considered as reduced cost matrix.

Consider the Path (5,3)

Change all entries in fifth row and third column to  and set A (3,1) to .
    
    
     r=0
    
    

= + A(25,3)+r = 28+0+0 = 28

35 53 25 31
2 3 4 5

2 3 5
28 50 36

3 5 52 28

3
 28
The Path is 1 4  2  5  3  1
Min. Cost = 10+6+2+7+3 = 28