1.

INTRODUCTION
General Method:
 The basic idea of backtracking 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 the partial vector
generated does not lead to an optimal solution. In such a situation that vector can be ignored.
 Backtracking algorithm determines the solution by systematically searching the solution
space (i.,e set of all feasible solutions) for the given problem.
 Backtracking is a depth first search with some bounding function. All solutions using
backtracking are required to satisfy a complex set of constraints. The constraints may be explicit or
implicit.

Algorithm: Recursive backtracking

Applications of Backtracking
Backtracking is an algorithm design technique that can effectively solve the larger instances
of combinational problems. It follows a systematic approach for obtaining solution to a problem. The
applications of backtracking includes as following:
1. N-Queen’s Problem
2. Sum of subsets problem
3. M-coloring problem
4. Hamiltonian cycle problem.

2. N-QUEEN’S PROBLEM
N-Queens Problem: This is generalization problem. If we taken n=8 then the problem is
called as 8 queens problem. If we taken n=4then the problem is called 4 queens problem. A classic
combinational problem is to place n queens on a n*n chess board so that no two attack, i.,e no two
queens are on the same row, column or diagonal.
Algorithm of n-queens problem is given below:

Algorithm: All solutions to the n queens problem

4-Queens problem:
Consider a 4*4 chessboard. Let there are 4 queens. The objective is place there 4 queens on
4*4 chessboard 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 4*4 chessboards in 44 ways.
The implicit constraints are no two queens are in the same row column or diagonal.
Let{x1, x2, x3, x4} be the solution vector where x1 column on which the queen i is placed.
First queen is placed in first row and first column.
 1

(a)
The second queen should not be in first row and second column. It should be placed in second row
and in second, third or fourth column. It we place in second column, both will be in same diagonal,
so place it in third column.
1 1
2

(b) (c)
We are unable to place queen 3 in third row so go back to queen 2 and place it somewhere else.
1 1

2 2

(d) (e)
Now the fourth queen should be placed in 4th row and 3rd column but there will be a diagonal attack
from queen 3. So go back, remove queen 3 and place it in the next column. But it is not possible, so
move back to queen 2 and remove it to next column but it is not possible. So go back to queen 1 and
move it to next column.
1 1

(f) (g)

1 1

2 2

3 3

4
(h) (i)
Fig: Example of Backtrack solution to the 4-queens problem
Hence the solution of to 4-queens’s problem is x1=2, x2=4, x3=1, x4=3, i.,e first queen is placed in
2nd column, second queen is placed in 4th column and third queen is placed in first column and
fourth queen is placed in third column.
 1
Row 1
x1=1 x1=2

2 3 Row 2
x2=2 x2=3 x2=4 x2=1 x2=3 x2=4

4 5 6 7 8 9 Row 3
B x3=2 x3=4 x3=2 x3=3 B B
x3=1
10 11 12 13 15 Row 4
B B x =3 B x4=3
4

14 16
B
Fig: Portion of the tree that is generated during Backtracking
8-queens problem
A classic combinatorial problem is to place 8 queens on a 8*8 chess board so that no two
attack, i.,e no two queens are to the same row, column or diagonal.
Now, we will solve 8 queens problem by using similar procedure adapted for 4 queens problem. The
algorithm of 8 queens problem can be obtained by placing n=8, in N queens algorithm.
We observe that, for every element on the same diagonal which runs from the upper left to the lower
right, each element has the same “row-column” value. Also every element on the same diagonal
which goes from upper right to lower left has the same “row+column” value.
If two queens are placed at positions (i,j) and (k,l). They are on the same diagonal only if
i-j=k-l ……………….(1) or
i+j=k+l ……………….(2).
From (1) and (2) implies
j-l=i-k and
j-l=k-i
two queens lie on the same diagonal iff
|j-l|=|i-k|
But how can we determine whether more than one queen is lying on the same diagonal? To answer
this question, a technique is deviced. Assume that the chess board is divided into rows

1....8, 1....8
rows columns
And columns say A:
This can be diagrammatically represented as follows
 1 2 3 4 5 6 7 8
1
2
3 Q
4
5
6
7
8
Now, assume that, we had placed a queen at position (3,2).
Now, its diagonal cells includes (2,1)(4,3)(5,4)….(if we traverse from upper left to lower right).
If we subtract values in these cells say 2-1=1,4-3=1,5-4=1, we get same values, also if we traverse
from upper right to lower left say (2,3) (1,4)(4,1)….we get common values when we add the bits of
these cells i.,e 2+3=5, 1+4=5, 4+1=5. Hence, we say that, on traversing from upper left to lower
right, if (m,n)(a,b) are the diagonal elements(of a cell) than m-n=a-b or on traversing from upper
right to lower left if(m,n)(a,b) are the diagonal elements(of a cell) then m+n=a+b.

The solution of 8 queens problem can be obtained similar to the solution of 4 queens. problem.X1=3,
X2=6, X3=2, X4=7, X5=1, X6=4, X7=8, X8=5,
The solution can be shown as
1

2
3
4
5

7
8
Time complexity: The solution space tree of 8-queens problem contains 88 tuples. After imposing
implicit constraints, the size of solution space is reduced to 8! tuples.
The state space tree for the above solution is given
 1

x1=1 x3=1

x2=2 2

3 4 5 6 7
1 2 4 5 x2=6
B 3 4
x3=2 4 5 6 7 8 1 x3=2

5 6 7
B x4=7
x4=2 4 7 8
6 4 5
8
x5=4 7 8 B B B x5=1
6
9
x6=7
7 8 x6=4
10 14
x7=7 8 x3=1 x7=8

11 12
B
x8=2 B
x8=5
13
12

3. SUM OF SUBSETS BPROBLEM

Given a set of n objects with weights (w1,w2,…..w3) and a positive integer M. We have to
find a subset S’ of the given set S, such that
 S’S
 Sum of the elements of subset S’ is equal to M.
For example, if a given set S=(1,2,3,4) and M=5, then there exists sets S’(3,2) and S’=(1,4) whose
sum is equal to M.
It can also be noted that some instance of the problem does not have any solution.
For example, if a given set S=(1,3,5) and M=7, then no subset occurs for which the sum is equal to
M=7.
The sum of subsets problem can be solved by using the back tracking approach. In this implicit tree
is created, which is a binary tree. The root of the tree is selected in such a way that it represents that
no decision is yet taken on any input. We assume that, the elements of the given set are arranged
increasing order.
The left child of the root node indicates that, we have to include the first element and right child of
the root node indicates that, we have to exclude the first element and so on for other nodes. Each
node stores the sum of the partial solution element. If at any stage, the number equals to ‘M’ then the
search is successful. At this time search will terminate or continues if all the possible solutions need
to be obtain. The dead end in the tree occurs only when either of the two inequalities exists.
The sum of S’ is too large.
The sum of S’ is too small.
Thus we take back one step and continue the search.
ALGORITHM:

Algorithm: Recursive backtracking algorithm for sum of subsets

Example:
Let m=31 and w= {7, 11, 13, 24} draw a portions of state space tree.
Solution: Initially we will pass some subset (0, 1, 55). The sum of all the weights from w is 55, i.e.,
7+11+13+24=55. Hence the portion of state –space tree can be
Here Solution A={1, 1, 1, 0} i.e., subset {7, 11, 13}
And Solution B={1, 0, 0,1} i.e. subset {7, 24}
Satisfy given condition=31;

Example: Consider a set S={5, 10, 12, 13, 15, 18} and N=30.
 Subset {Empty} Sum=0 Initially subset is 0
5 5
5, 10 15
5, 10, 12 27
5, 10, 12, 13 40 Sum exceeds N=30,Hence Backtrack
5, 10, 12, 15 Not Feasible
5, 10, 12, 18 Not feasible
5, 10 List ends. Backrack
5, 10, 13 28
5, 10, 13, 15 33 Not feasible. Backtrack
5, 10 15
5, 10, 15 30 Solution obtained
We can represent various solutions to sum of subset by a state space tree as,
0

x1=1 x1=0

5 0
x2=1 x2=0 x2=1 x2=0

15 5 10 0

x3=1 x3=0 x3=1 x3=0 x3=1 x3=1

27 15 17 5 22 12

x4=1 x4=0 x4=1 x4=0 x4=0 x4=0

28 15 30 5 22 12
B
x5=1 x5=1 x5=0
30 20 12
A
x6=1
30
C
 4. GAPH COLORING
Let G be a graph and m be a given positive integer. The graph coloring problem is to find 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. This is termed the m-colorability decision problem. The m-colorability optimization
problem asks for the smallest integer m for which the graph G can be colored. This integer is
referred to as the chromatic number of the graph.

Figure. An Ex. Of graph coloring

Algorithm: Finding all m-colorings of graph

Algorithm: Finding next color

Fig. A map and it’s planar graph representation

To color the above graph chromatic number is 4. And the order of coloring is X1=1, X2=2, X3=3,
X4=4, X5=1
Time Complexity: At each internal node O(mn) time is spent by Nextcolor to determine the
children corresponding to legal coloring. Hen the total time is bounded by,
n
min = n(m+m2+.......+mn
i=1
=n.mn
=O(n.mn)
 5. KNAPSACK PROBLEM
Knapsack Problem using Backtracking can be solved as follow:

The knapsack problem is useful in solving resource allocation problems.

Let X = <x1, x2, x3, . . . . . , xn> be the set of n items,
W = <w1, w2, w3, . . . , wn> and V = <v1, v2, v3, . . . , vn> be the set of weight and value associated
with each item in X, respectively.
▪ Let M be the total capacity of the knapsack, i.e. knapsack cannot hold items having a
collective weight greater than M.
▪ Select items from X such that it maximizes the profit and the collective weight of
selected items does not exceed the knapsack capacity.
▪ The knapsack problem has two variants. 0/1 knapsack does not allow breaking up the
item, whereas a fractional knapsack does. 0/1 knapsack is also known as a binary
knapsack.
▪ The Knapsack problem can be formulated as,
▪ Maximize
Sumi=1n vixi
▪ subjected to
Sumi=1n wixi <= M
xi in (0,1)
Algorithm:

Algorithm: 0/1 Knapsack using backtracking

Example:
Consider knapsack problem: n = 8. (W1, W2, W3, W4, W5, W6, W2, W8) = (1, 11, 21, 23, 33, 43, 45,
55), P = (11, 21, 31, 33, 43, 53, 55, 65), m = 110. Solve the problem using backtracking approach.
Solution:
Let arrange all items in non-decreasing order of p[i] / w[i].
 i p[i] w[i] p[i]/w[i]
1 11 1 11
2 21 11 1.90
3 31 21 1.47
4 33 23 1.43
5 43 33 1.30
6 54 43 1.23
7 55 45 1.22
8 65 55 1.18

Here M = 110 and n = 8.

Initially, cp = cw = 0, fp = – 1, k = 0

For k = 1:
cp = cp + p1 = 0 + 11 = 11
cw = cw + w1 = 0 + 1 = 1
cw < M, so select item 1
k = k+1=2
For k=1:
cp = cp + p2 = 11 + 21 = 32
cw = cw + w2 = 1 + 11 = 12
cw < M, so select item 2
k = k+1=2
For k = 2:
cp = cp + p3 = 32 + 31 = 63
cw = cw + w3 = 12 + 21 = 33
cw < M, so select item 3
k = k+1=3
For k = 3:
cp = cp + p4 = 63 + 33 = 96
cw = cw + w4 = 33 + 23 = 56
cw < M, so select item 4
k = k+1=4
For k = 4:
cp = cp + p5 = 96 + 43 = 139
cw = cw + w5 = 56 + 33 = 89
cw < M, so select item 5
k = k+1=5
For k = 5:
cp = cp + p6 = 139 + 53 = 192
cw = cw + w6 = 89 + 43 = 132
cw > M, so reject item 6 and find upper bound
cp = cp – p6 = 192 – 53 = 139
 cw = cw – w6 = 132 – 43 = 89
ub = cp + ((M – cw ) / w i+1) * pi+1
b = cp + [(110 – 89) / 43] * 53 = 164.88
Inclusion of any item from {I6, I7, I8} will exceed the capacity. So let’s backtrack to item 4.
The space tree would look like as shown in Fig. P. 6.7.2.
Upper bound at node 1:
ub = cp + ((M – cw ) / w i+1) * pi+1
= 139 + [(110 – 89)] / 43 * 53 = 164.88
Upper bound at node 2:
= 96 + [(110 – 56) / 33] * 43 = 166.09
Upper bound at node 3:
= 63 + [(110 – 33) / 33] * 43 = 163.33

Time Complexity: O(2N)

Space Complexity: O(N.
Introduction:
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 becomes the E-Node.
Branch and Bound is the generalization of both graph search strategies, BFS and D-search.
 A BFS like state space search is called as FIFO (First in first out) search as the list of
live nodes in a first in first out.
 A D-search like state space search is called as LIFO (last in first out) search as the list of
live nodes in a last in first out list.
Live node is a node that has been generated but whose children have not yet been generated.
E- node is a live node whose children are currently being explored. In other words, an E-node is
a node currently being expanded.
Dead node is a generated anode that is not be expanded or explored any further. All children of a
dead node have already been expanded.
Here we will use 3 types of search strategies:
1. FIFO (First In First Out)
2. LIFO (Last In First Out)
3. LC (Least Cost) Search
FIFO Branch and Bound Search:
For this we will use a data structure called Queue. Initially Queue is empty.

Example:

Assume the node 12 is an answer node (solution)

In FIFO search, first we will take E-node as a node 1.
Next we generate the children of node 1. We will place all these live nodes in a queue.

Now we will delete an element from queue, i.e. node 2, next generate children of node 2
and place in this queue.
 Next, delete an element from queue and take it as E-node, generate the children of node
3, 7, 8 are children of 3 and these live nodes are killed by bounding functions. So we will not
include in the queue.

Again delete an element an from queue. Take it as E-node, generate the children of 4.
Node 9 is generated and killed by boundary function.

Next, delete an element from queue. Generate children of nodes 5, i.e., nodes 10 and 11
are generated and by boundary function, last node in queue is 6. The child of node 6 is 12 and it
satisfies the conditions of the problem, which is the answer node, so search terminates.
LIFO Branch and Bound Search
For this we will use a data structure called stack. Initially stack is empty.
Example:

Generate children of node 1 and place these live nodes into stack.

Remove element from stack and generate the children of it, place those nodes into stack.
2 is removed from stack. The children of 2 are 5, 6. The content of stack is,
 Again remove an element from stack, i.,e node 5 is removed and nodes generated by 5
are 10, 11 which are killed by bounded function, so we will not place 10, 11 into stack.

Delete an element from stack, i.,e node 6. Generate child of node 6, i.,e 12, which is the
answer node, so search process terminates.
LC (Least Cost) Branch and Bound Search
In both FIFO and LIFO Branch and Bound the selection rules for the next E-node in rigid
and blind. The selection rule for the next E-node does not give any preferences to a node that has
a very good chance of getting the search to an answer node quickly.
In this we will use ranking function or cost function. We generate the children of E-node, among
these live nodes; we select a node which has minimum cost. By using ranking function we will
calculate the cost of each node.

Initially we will take node 1 as E-node. Generate children of node 1, the children are 2, 3,
4. By using ranking function we will calculate the cost of 2, 3, 4 nodes is ĉ =2, ĉ =3, ĉ =4
respectively. Now we will select a node which has minimum cost i.,e node 2. For node 2, the
children are 5, 6. Between 5 and 6 we will select the node 6 since its cost minimum. Generate
children of node 6 i.,e 12 and 13. We will select node 12 since its cost (ĉ =1) is minimum. More
over 12 is the answer node. So, we terminate search process.
Control Abstraction for LC-search
Let t be a state space tree and c() 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 sub tree with root x. Thus, c(t) is the cost of a
minimum-cost answer node in t.
LC search uses ĉ to find an answer node. The algorithm uses two functions
 1. Least-cost()
2. Add_node().
Least-cost() finds a live node with least c(). This node is deleted from the list of live nodes and
returned.
Add_node() to delete and add a live node from or to the list of live nodes.
Add_node(x)adds the new live node x to the list of live nodes. The list of live nodes be
implemented as a min-heap.

BOUNDING
 A branch and bound method searches a 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.
 A good bounding helps to prune (reduce) efficiently the tree, leading to a faster
exploration of the solution space. Each time a new answer node is found, the value of
upper can be updated.
 Branch and bound algorithms are used for optimization problem where we deal directly
only with minimization problems. A maximization problem is easily converted to a
minimization problem by changing the sign of the objective function.

APPLICATION: 0/1 KNAPSACK PROBLEM (LCBB)

There are n objects given and capacity of knapsack is M. Select some objects to fill the
knapsack in such a way that it should not exceed the capacity of Knapsack and maximum profit
can be earned. The Knapsack problem is maximization problem. It means we will always seek
for maximum p1x1 (where p1 represents profit of object x1).
A branch bound technique is used to find solution to the knapsack problem. But we
cannot directly apply the branch and bound technique to the knapsack problem. Because the
branch bound deals only the minimization problems. We modify the knapsack problem to the
minimization problem. The modifies problem is,
 Algorithm: KNAPSACK PROBLEM
Example: 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: knapsack problem can be solved by using branch and bound technique. In this problem
we will calculate lower bound and upper bound for each node.
Arrange the item profits and weights with respect of profit by weight ratio. After that,
place the first item in the 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. No fraction are allowed in calculation of upper
bound so w4, cannot be placed in knapsack.
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+ (3/9*18)=32+6=38
Knapsack is maximization problem but branch 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.
Therefore, upper bound (U) =-32
Lower bound (L)=-38
We choose the path, which has minimized difference of upper bound and lower bound. If
the difference is equal then we choose the path by comparing upper bounds and we discard node
with maximum upper bound.
Now we will calculate upper bound and lower bound for nodes 2, 3
For node 2, x1=1, means we should place first item in the knapsack.
U=10+10+12=32, make it as -32
L=10+10+12+ (3/9*18) = 32+6=38, we make it as -38
For node 3, x1=0, means we should not place first item in the knapsack.
U=10+12=22, make it as -22
L=10+12+ (5/9*18) = 10+12+10=32, we make it as -32

Next we will calculate difference of upper bound and lower bound for nodes 2, 3
For node 2, U-L=-32+38=6
For node 3, U-L=-22+32=10
Choose node 2, since it has minimum difference value of 6.

Now we will calculate lower bound and upper bound of node 4 and 5. Calculate difference of
lower and upper bound of nodes 4 and 5.
For node 4, U-L=-32+38=6
For node 5, U-L=-22+36=14
Choose node 4, since it has minimum difference value of 6
Now we will calculate lower bound and upper bound of node 6 and 7. Calculate difference of
lower and upper bound of nodes 6 and 7.
For node 6, U-L=-32+38=6
For node 7, U-L=-38+38=0
Choose node 7, since it has minimum difference value of 0.
Now we will calculate lower bound and upper bound of node 8 and 9. Calculate difference of
lower and upper bound of nodes 8 and 9.
For node 8, U-L=-38+38=0
For node 9, U-L=-20+20=0
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:
∑pixi=10*1+10*1+12*0+18*1
10+10+18=38.

FIFO Branch-and-Bound Solution

Now, let us trace through the FIFOBB algorithm using the same knapsack instance as in
above Example. Initially the root node, node 1 of following Figure, is the E-node and the queue
of live nodes is empty. Since this is not a solution node, upper is initialized to u(l) = -32. We
assume the children of a node are generated left to right. Nodes 2 and 3 are generated and added
to the queue (in that order). The value of upper remains unchanged. Node 2 becomes the next E-
node. Its children, nodes 4 and 5, are generated and added to the queue.
Node 3, the next-node, is expanded. Its children nodes are generated; Node 6 gets added
to the queue. Node 7 is immediately killed as L (7) > upper. Node 4 is expanded next. Nodes 8
and 9 are generated and added to the queue. Then Upper is updated to u(9) = -38, Nodes 5 and 6
are the next two nodes to become B-nodes. Neither is expanded as for each, L > upper. Node 8 is
the next E-node. Nodes 10 and 11 are generated; Node 10 is infeasible and so killed. Node 11
has L (11) > upper and so is also killed. Node 9 is expanded next.
When node 12 is generated, 'Upper and ans are updated to -38 and 12 respectively. Node
12 joins the queue of live nodes. Node 13 is killed before it can get onto the queue of live nodes
as L (13) > upper. The only remaining live node is node 12. It has no children and the search
terminates. The value of upper and the path from node 12 to the root is output. So solution is
X1=1, X2=1, X3=0, X4=1.
APPLICATON: TRAVELLING SALES PERSON PROBLEM
Let G = (V', E) be a directed graph defining an instance of the traveling salesperson
problem. Let Cij equal the cost of edge (i, j), Cij = ∞ if (i, j) != E, and let IVI = n, without loss of
generality, we can assume that every tour starts and ends at vertex 1.

Procedure for solving travelling sales person problem

1. Reduce the given cost matrix. A matrix is reduced if every row and column is reduced. This
can be done as follows:
Row Reduction:
a) Take the minimum element from first row, subtract it from all elements of first row, next
take minimum element from the second row and subtract it from second row. Similarly
apply the same procedure for all rows.
b) Find the sum of elements, which were subtracted from rows.
c) Apply column reductions for the matrix obtained after row reduction.
Column Reduction:
d) Take the minimum element from first column, subtract it from all elements of first
column, next take minimum element from the second column and subtract it from second
column. Similarly apply the same procedure for all columns.
e) Find the sum of elements, which were subtracted from columns.
f) Obtain the cumulative sum of row wise reduction and column wise reduction.
Cumulative reduced sum=Row wise reduction sum + Column wise reduction sum.
Associate the cumulative reduced sum to the starting state as lower bound and α as upper
bound.
2. Calculate the reduced cost matrix for every node.
a) If path (i,j) is considered then change all entries in row i and column j of A to α.
b) Set A(j,1) to α.
c) Apply row reduction and column reduction except for rows and columns containing
only α. Let r is the total amount subtracted to reduce the matrix.
d) Find ĉ(S)= ĉ(R)+A(i,j)+r.
Repeat step 2 until all nodes are visited.
Example: Find the LC branch and bound solution for the travelling sales person problem whose
cost matrix is as follows.
∞ 20 30 10 11
15 ∞ 16 4 2
The cost matrix is 3 5 ∞ 2 4
19 6 18 ∞ 3
16 4 7 16 ∞

Step 1: Find the reduced cost matrix

Apply now reduction method:

Deduct 10 (which is the minimum) from all values in the 1st row.
Deduct 2 (which is the minimum) from all values in the 2nd row.
Deduct 2 (which is the minimum) from all values in the 3rd t row.
Deduct 3 (which is the minimum) from all values in the 4th row.
Deduct 4 (which is the minimum) from all values in the 5th row.
∞ 10 20 0 1
13 ∞ 14 2 0
The resulting row wise reduced cost matrix = 1 3 ∞ 0 2
16 3 15 ∞ 0
12 0 3 12 ∞
Row wise reduction sum = 10+2+2+3+4=21.
Now apply column reduction for the above matrix:
Deduct 1 (which is the minimum) from all values in the 1st column.
Deduct 3 (which is the minimum) from all values in the 2nd column.
∞ 10 17 0 1
12 ∞ 11 2 0
The resulting column wise reduced cost matrix (A) = 0 3 ∞ 0 2
15 3 12 ∞ 0
11 0 3 12 ∞
Column wise reduction sum = 1+0+3+0+0=4.
Cumulative reduced sum = row wise reduction + column wise reduction sum.
=21+ 4 =25.
This is the cost of a root i.e. node 1, because this is the initially reduced cost matrix.
The lower bound for node is 25 and upper bound is ∞.
Starting from node 1, we can next visit 2, 3, 4 and 5 vertices. So, consider to explore the paths (1,
2), (1,3), (1, 4), (1,5).
The tree organization up to this as follows;
Variable i indicate the next node to visit.
Step 2:
Now consider the path (1, 2)
Change all entries of row 1 and column 2 of A to ∞ and also set A (2, 1) to ∞.
∞ ∞ ∞ ∞ ∞
∞ ∞ 11 2 0
0 ∞ ∞ 0 2
15 ∞ 12 ∞ 0
11 ∞ 0 12 ∞
Apply row and column reduction for the rows and columns whose rows and column are not
completely ∞. Then the resultant matrix is

Row reduction sum = 0 + 0 + 0 + 0 = 0

Column reduction sum = 0 + 0 + 0 + 0= 0
Cumulative reduction(r) = 0 + 0=0
Therefore, as ĉ(S)= ĉ(R)+A(1,2)+r  ĉ(S)= 25 + 10 + 0 = 35.
Now consider the path (1, 3)
Change all entries of row 1 and column 3 of A to ∞ and also set A (3, 1) to ∞.
∞ ∞ ∞ ∞ ∞
12 ∞ ∞ 2 0
∞ 3 ∞ 0 2
15 3 ∞ ∞ 0
11 0 ∞ 12 ∞

Apply row and column reduction for the rows and columns whose rows and column are not
completely ∞
∞ ∞ ∞ ∞ ∞
1 ∞ ∞ 2 0
Then the resultant matrix is = ∞ 3 ∞ 0 2
4 3 ∞ ∞ 0
0 0 ∞ 12 ∞

Row reduction sum = 0

Column reduction sum = 11
Cumulative reduction(r) = 0 +11=11
Therefore, as ĉ(S)= ĉ(R)+A(1,3)+r
ĉ(S)= 25 + 17 +11 = 53.

Now consider the path (1, 4)

Change all entries of row 1 and column 4 of A to ∞ and also set A(4,1) to ∞.
∞ ∞ ∞ ∞ ∞
12 ∞ 11 ∞ 0
0 3 ∞ ∞ 2
∞ 3 12 ∞ 0
11 0 0 ∞ ∞
Apply row and column reduction for the rows and columns whose rows and column are not
completely ∞
∞ ∞ ∞ ∞ ∞
12 ∞ 11 ∞ 0
Then the resultant matrix is = 0 3 ∞ ∞ 2
∞ 3 12 ∞ 0
11 0 0 ∞ ∞
Row reduction sum = 0
Column reduction sum = 0
Cumulative reduction(r) = 0 +0=0
Therefore, as ĉ(S)= ĉ(R)+A(1,4)+r
ĉ(S)= 25 + 0 +0 = 25.
Now Consider the path (1, 5)
Change all entries of row 1 and column 5 of A to ∞ and also set A(5,1) to ∞.
∞ ∞ ∞ ∞ ∞
12 ∞ 11 2 ∞
0 3 ∞ 0 ∞
15 3 12 ∞ ∞
∞ 0 0 12 ∞
Apply row and column reduction for the rows and columns whose rows and column are not
completely ∞
∞ ∞ ∞ ∞ ∞
10 ∞ 9 0 ∞
Then the resultant matrix is = 0 3 ∞ 0 ∞
12 0 9 ∞ ∞
∞ 0 0 12 ∞
Row reduction sum = 5
Column reduction sum = 0
Cumulative reduction(r) = 5 +0=0
Therefore, as ĉ(S)= ĉ(R)+A(1,5)+r

ĉ(S)= 25 + 1 +5 = 31.
The tree organization up to this as follows:
 The cost of the between (1, 2) = 35, (1, 3) = 53, ( 1, 4) = 25, (1, 5) = 31. The cost of the
path between (1, 4) is minimum. Hence the matrix obtained for path (1, 4) is considered as
reduced cost matrix.
∞ ∞ ∞ ∞ ∞
12 ∞ 11 ∞ 0
A= 0 3 ∞ ∞ 2
∞ 3 12 ∞ 0
11 0 0 ∞ ∞
The new possible paths are (4, 2), (4, 3) and (4, 5).
Now consider the path (4, 2)
Change all entries of row 4 and column 2 of A to ∞ and also set A(2,1) to ∞.
∞ ∞ ∞ ∞ ∞
∞ ∞ 11 ∞ 0
0 ∞ ∞ ∞ 2
∞ ∞ ∞ ∞ ∞
11 ∞ 0 ∞ ∞
Apply row and column reduction for the rows and columns whose rows and column are not
completely ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ 11 ∞ 0
Then the resultant matrix is = 0 ∞ ∞ ∞ 2
∞ ∞ ∞ ∞ ∞
11 ∞ 0 ∞ ∞
Row reduction sum = 0
Column reduction sum = 0
Cumulative reduction(r) = 0 +0=0
Therefore, as ĉ(S)= ĉ(R)+A(4,2)+r
ĉ(S)= 25 + 3 +0 = 28.

Now consider the path (4, 3)

Change all entries of row 4 and column 3 of A to ∞ and also set A(3,1) to ∞.
∞ ∞ ∞ ∞ ∞
12 ∞ ∞ ∞ 0
∞ 3 ∞ ∞ 2
∞ ∞ ∞ ∞ ∞
11 0 ∞ ∞ ∞
Apply row and column reduction for the rows and columns whose rows and column are not
completely ∞
∞ ∞ ∞ ∞ ∞
1 ∞ ∞ ∞ 0
Then the resultant matrix is = ∞ 1 ∞ ∞ 0
∞ ∞ ∞ ∞ ∞
0 0 ∞ ∞ ∞
Row reduction sum = 2
Column reduction sum = 11
Cumulative reduction(r) = 2 +11=13
Therefore, as ĉ(S)= ĉ(R)+A(4,3)+r
ĉ(S)= 25 + 12 +13 = 50.
.Now consider the path (4, 5)
Change all entries of row 4 and column 5 of A to ∞ and also set A(5,1) to ∞.
∞ ∞ ∞ ∞ ∞
12 ∞ 11 ∞ ∞
0 3 ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ 0 0 ∞ ∞
Apply row and column reduction for the rows and columns whose rows and column are not
completely ∞
∞ ∞ ∞ ∞ ∞
1 ∞ 0 ∞ ∞
Then the resultant matrix is = 0 3 ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ 0 0 ∞ ∞
Row reduction sum =11
Column reduction sum = 0
Cumulative reduction(r) = 11 +0=11
Therefore, as ĉ(S)= ĉ(R)+A(4,5)+r
ĉ(S)= 25 + 0 +11 = 36.
The tree organization up to this as follows:

The cost of the between (4, 2) = 28, (4, 3) = 50, ( 4, 5) = 36. The cost of the path between
(4, 2) is minimum. Hence the matrix obtained for path (4, 2) is considered as reduced cost
matrix.
∞ ∞ ∞ ∞ ∞
∞ ∞ 11 ∞ 0
A= 0 ∞ ∞ ∞ 2
∞ ∞ ∞ ∞ ∞
11 ∞ 0 ∞ ∞
The new possible paths are (2, 3) and (2, 5).
Now Consider the path (2, 3):
Change all entries of row 2 and column 3 of A to ∞ and also set A(3,1) to ∞.
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ 2
∞ ∞ ∞ ∞ ∞
11 ∞ ∞ ∞ ∞
Apply row and column reduction for the rows and columns whose rows and column are not
completely ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
Then the resultant matrix is = ∞ ∞ ∞ ∞ 0
∞ ∞ ∞ ∞ ∞
0 ∞ ∞ ∞ ∞
Row reduction sum =13
Column reduction sum = 0
Cumulative reduction(r) = 13 +0=13
Therefore, as ĉ(S)= ĉ(R)+A(2,3)+r
ĉ(S)= 28 + 11 +13 = 52.

Now Consider the path (2, 5):

Change all entries of row 2 and column 5 of A to ∞ and also set A(5,1) to ∞.
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
0 ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ 0 ∞ ∞
Apply row and column reduction for the rows and columns whose rows and column are not
completely ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
Then the resultant matrix is = 0 ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ 0 ∞ ∞
Row reduction sum =0
Column reduction sum = 0
Cumulative reduction(r) = 0 +0=0
Therefore, as ĉ(S)= ĉ(R)+A(2,5)+r  ĉ(S)= 28 + 0 +0 = 28.
The tree organization up to this as follows:
The cost of the between (2, 3) = 52 and (2, 5) = 28. The cost of the path between (2, 5) is
minimum. Hence the matrix obtained for path (2, 5) is considered as reduced cost matrix.
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
A= 0 ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ 0 ∞ ∞
The new possible path is (5, 3).

Now consider the path (5, 3):

Change all entries of row 5 and column 3 of A to ∞ and also set A(3,1) to ∞. Apply row and
column reduction for the rows and columns whose rows and column are not completely ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
Then the resultant matrix is = ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
Row reduction sum =0
Column reduction sum = 0
Cumulative reduction(r) = 0 +0=0
Therefore, as ĉ(S)= ĉ(R)+A(5,3)+r
ĉ(S)= 28 + 0 +0 = 28.
The path travelling sales person problem is:
142531:
The minimum cost of the path is: 10+2+6+7+3=28.
The overall tree organization is as follows: