Analysis & Design of Algorithms

Q.6: Explain how branch and bound techniques can be used to solve travelling sales person problem.

Travelling Salesman Problem - Least cost branch-and-bound (LCBB) technique can be used to find a minimum cost tour from a given set of the nodes. For this, we need to define two cost functions c(*) and u(*) such that ĉ(r) The cost function c(*) should be such that the solution node with least c(*) corresponds to a shortest tour in G. One way for deciding value of c(*) is -

C(A)= Length of tour defined by the path from the root to A, if A is a leaf cost of a minimum cost leaf in the subtree A, if A is not a leaf.

State space tree for such problem is shown in fig. with each edge assigned a value indicates the root to be followed.

For example, node 8 shows the path 1, 3, 4 and node 13 shows path 1, 3, 2, 4. Reduced cost matrix is used for finding better value of ĉ(*). For this, we have to reduce a matrix. A matrix is said to be reduced if its rows and columns are reduced, and a row (column) is said to be reduced iff it contains at least one zero and all remaining entries are non-negative.

We associate a reduced cost matrix with every node in the travelling salesperson state space tree. Suppose that A be the reduced cost matrix for a node P and Q be a child for node P, also suppose that P is not a leaf child. Here tree edge (P, Q) corresponds to including edge in the tour.

A reduced cost matrix for P can be obtained as follows -
(i) Change all entries in row i and column j of A to 0. This prevents the use of any more edges leaving vertex i or entering vertex j.
(ii) Set A(j, 1) to co. This prevents the use of edge (j, 1).
(iii) Reduce all rows and columns in the resulting matrix except for rows and columns containing only ∞.

Total cost of Q can be given as -
ĉ (Q) = ĉ(P) +A(i, j) +r

where r is the total amount subtracted in step (iii).

At each step of determining minimum cost tour we select a node ha minimum cost and go ahead step-by-step by doing same, and finally we result with a minimum cost tour.

notes For Error Please Whatsapp @9300930012