Travelling Salesman

1. Traveling salesman

2. What are the differences between 'Backtracking' and 'Branch & Bound' Algorithm techniques? Backtracking [1] It is used to find all possible solutions available to the problem. [2] It traverse tree by DFS (Depth First Search). [3] It realizes that it has made a bad choice & undoes the last choice by backing up. [4] It search the state space tree until it found a solution. [5] It involves feasibility function Branch-and-Bound [ 1] It is used to solve optimization problem. [2] It may traverse the tree in any manner, DFS or BFS. [ 3] It realizes that it already has a better optimal solution that the pre-solution leads to so it abandons that pre-solution . [ 4] It completely searches the state space tree to get optimal solution . [ 5] It involves bounding function.

3. Here is the state space tree for n=4 (Using Branch And Bound)

4. What is traveling salesman problem? Let us look at a situation that there are 5 cities, which are represented as NODES. There is a Person at NODE-1 This person has to reach each nodes one and only ones and come back to original (starting) position This process has to occur with minimum cost or minimum distance travelled. Note that starting point can start with any Node. For Example: 1-2-4-5-3-1 1 -5-2-3-4-1

5. How to compute the cost of each node? A row/column is said to be reduce iff it contains at least one zero and all remaining entries are non-negative. A matrix is reduced iff every row and column is reduced. Rules of reduced cost matrix : 1. Change all entries in row i and column j from A to inf 2. Set A[j,1] to inf 3. Reduce all rows and columns in the resulting except for rows and column containing only inf. 4. Cost Function C(s)=C(R)+A[ i ,j ]+ r [r – total reduce value]

6. -10 -2 -2 -3 -4 REDUCTION (ROW) INF 20 30 10 11 15 INF 16 4 2 3 5 INF 2 4 19 6 18 INF 3 16 4 7 16 INF -1 -3 COLUMN REDUCTION TOTAL REDUCTION = (10+2+2+3+4)+(1+3) = 25 INF 10 17 1 12 INF 11 2 1 3 INF 2 15 3 12 INF 11 3 12 INF INF 10 17 1 12 INF 11 2 3 INF 2 15 3 12 INF 11 12 INF

7. Thank you all…….