# Traveling Salesman Problem – Solve it using Dynamic Programming

Traveling salesman problem (TSP) is the well studied and well-explored problem of computer science. Due to its application in diverse fields, TSP has been one of the most interesting problems for researchers and mathematicians.

## Traveling salesman problem – Description

- Traveling salesman problem is stated as, “Given a set of
*n*cities and distance between each pair of cities, find the minimum length path such that it covers each city exactly once and terminates the tour at starting city.” - It is not difficult to show that this problem is NP complete problem. There exists
*n!*paths, a search of the optimal path becomes very slow when*n*is considerably large. - Each edge (u, v) in TSP graph is assigned some non-negative weight, which represents the distance between city u and v. This problem can be solved by finding the Hamiltonian cycle of the graph.
- The distance between cities is best described by the weighted graph, where edge (u, v) indicates the path from city u to v and w(u, v) represents the distance between cities u and v.
- Let us formulate the solution of TSP using dynamic programming.

## Algorithm for Traveling salesman problem

**Step 1:**
Let d[i, j] indicates the distance between cities i and j. Function C[x, V – { x }]is the cost of the path starting from city x. V is the set of cities/vertices in given graph. The aim of TSP is to minimize the cost function.
**Step 2:**
Assume that graph contains n vertices V1, V2, ..., Vn. TSP finds a path covering all vertices exactly once, and the same time it tries to minimize the overall traveling distance.
**Step 3:**
Mathematical formula to find minimum distance is stated below:
C(i, V) = min { d[i, j] + C(j, V – { j }) }, j ∈ V and i ∉ V.
TSP problem possesses the principle of optimality, i.e. for d[V1, Vn] to be minimum, any intermediate path (Vi, Vj) must be minimum.

- From following figure, d[i, j] = min(d[i, j], d[i, k] + d[k, j])
- Dynamic programming always selects the path which is minimum.

## Complexity Analysis of Traveling salesman problem

Dynamic programming creates n.2^{n} subproblems for n cities. Each sub-problem can be solved in linear time. Thus the time complexity of TSP using dynamic programming would be O(n^{2}2^{n}). It is much less than n! but still, it is an exponent. Space complexity is also exponential.

## Example

**Problem: Solve the traveling salesman problem with the associated cost adjacency matrix using dynamic programming.**

– | 24 | 11 | 10 | 9 |

8 | – | 2 | 5 | 11 |

26 | 12 | – | 8 | 7 |

11 | 23 | 24 | – | 6 |

5 | 4 | 8 | 11 | – |

**Solution:**

Let us start our tour from city 1.

**Step 1:** Initially, we will find the distance between city 1 and city {2, 3, 4, 5} without visiting any intermediate city.

Cost(x, y, z) represents the distance from x to z and y as an intermediate city.

Cost(2, Φ, 1) = d[2, 1] = 24

Cost(3, Φ, 1) = d[3, 1] = 11

Cost(4, Φ , 1) = d[4, 1] = 10

Cost(5, Φ , 1) = d[5, 1] = 9

**Step 2:** In this step, we will find the minimum distance by visiting 1 city as intermediate city.

Cost{2, {3}, 1} = d[2, 3] + Cost(3, f, 1)

= 2 + 11 = 13

Cost{2, {4}, 1} = d[2, 4] + Cost(4, f, 1)

= 5 + 10 = 15

Cost{2, {5}, 1} = d[2, 5] + Cost(5, f, 1)

= 11 + 9 = 20

Cost{3, {2}, 1} = d[3, 2] + Cost(2, f, 1)

= 12 + 24 = 36

Cost{3, {4}, 1} = d[3, 4] + Cost(4, f, 1)

= 8 + 10 = 18

Cost{3, {5}, 1} = d[3, 5] + Cost(5, f, 1)

= 7 + 9 = 16

Cost{4, {2}, 1} = d[4, 2] + Cost(2, f, 1)

= 23 + 24 = 47

Cost{4, {3}, 1} = d[4, 3] + Cost(3, f, 1)

= 24 + 11 = 35

Cost{4, {5}, 1} = d[4, 5] + Cost(5, f, 1)

= 6 + 9 = 15

Cost{5, {2}, 1} = d[5, 2] + Cost(2, f, 1)

= 4 + 24 = 28

Cost{5, {3}, 1} = d[5, 3] + Cost(3, f, 1)

= 8 + 11 = 19

Cost{5, {4}, 1} = d[5, 4] + Cost(4, f, 1)

= 11 + 10 = 21

**Step 3:** In this step, we will find the minimum distance by visiting 2 cities as intermediate city.

Cost(2, {3, 4}, 1) = min { d[2, 3] + Cost(3, {4}, 1), d[2, 4] + Cost(4, {3}, 1)]}

= min { [2 + 18], [5 + 35] }

= min{20, 40} = 20

Cost(2, {4, 5}, 1) = min { d[2, 4] + Cost(4, {5}, 1), d[2, 5] + Cost(5, {4}, 1)]}

= min { [5 + 15], [11 + 21] }

= min{20, 32} = 20

Cost(2, {3, 5}, 1) = min { d[2, 3] + Cost(3, {4}, 1), d[2, 4] + Cost(4, {3}, 1)]}

= min { [2 + 18], [5 + 35] }

= min{20, 40} = 20

Cost(3, {2, 4}, 1) = min { d[3, 2] + Cost(2, {4}, 1), d[3, 4] + Cost(4, {2}, 1)]}

= min { [12 + 15], [8 + 47] }

= min{27, 55} = 27

Cost(3, {4, 5}, 1) = min { d[3, 4] + Cost(4, {5}, 1), d[3, 5] + Cost(5, {4}, 1)]}

= min { [8 + 15], [7 + 21] }

= min{23, 28} = 23

Cost(3, {2, 5}, 1) = min { d[3, 2] + Cost(2, {5}, 1), d[3, 5] + Cost(5, {2}, 1)]}

= min { [12 + 20], [7 + 28] }

= min{32, 35} = 32

Cost(4, {2, 3}, 1) = min{ d[4, 2] + Cost(2, {3}, 1), d[4, 3] + Cost(3, {2}, 1)]}

= min { [23 + 13], [24 + 36] }

= min{36, 60} = 36

Cost(4, {3, 5}, 1) = min{ d[4, 3] + Cost(3, {5}, 1), d[4, 5] + Cost(5, {3}, 1)]}

= min { [24 + 16], [6 + 19] }

= min{40, 25} = 25

Cost(4, {2, 5}, 1) = min{ d[4, 2] + Cost(2, {5}, 1), d[4, 5] + Cost(5, {2}, 1)]}

= min { [23 + 20], [6 + 28] }

= min{43, 34} = 34

Cost(5, {2, 3}, 1) = min{ d[5, 2] + Cost(2, {3}, 1), d[5, 3] + Cost(3, {2}, 1)]}

= min { [4 + 13], [8 + 36] }

= min{17, 44} = 17

Cost(5, {3, 4}, 1) = min{ d[5, 3] + Cost(3, {4}, 1), d[5, 4] + Cost(4, {3}, 1)]}

= min { [8 + 18], [11 + 35] }

= min{26, 46} = 26

Cost(5, {2, 4}, 1) = min{ d[5, 2] + Cost(2, {4}, 1), d[5, 4] + Cost(4, {2}, 1)]}

= min { [4 + 15], [11 + 47] }

= min{19, 58} = 19

**Step 4 :** In this step, we will find the minimum distance by visiting 3 cities as intermediate city.

Cost(2, {3, 4, 5}, 1) = min { d[2, 3] + Cost(3, {4, 5}, 1), d[2, 4] + Cost(4, {3, 5}, 1), d[2, 5] + Cost(5, {3, 4}, 1)}

= min { 2 + 23, 5 + 25, 11 + 36}

= min{25, 30, 47} = 25

Cost(3, {2, 4, 5}, 1) = min { d[3, 2] + Cost(2, {4, 5}, 1), d[3, 4] + Cost(4, {2, 5}, 1), d[3, 5] + Cost(5, {2, 4}, 1)}

= min { 12 + 20, 8 + 34, 7 + 19}

= min{32, 42, 26} = 26

Cost(4, {2, 3, 5}, 1) = min { d[4, 2] + Cost(2, {3, 5}, 1), d[4, 3] + Cost(3, {2, 5}, 1), d[4, 5] + Cost(5, {2, 3}, 1)}

= min {23 + 30, 24 + 32, 6 + 17}

= min{53, 56, 23} = 23

Cost(5, {2, 3, 4}, 1) = min { d[5, 2] + Cost(2, {3, 4}, 1), d[5, 3] + Cost(3, {2, 4}, 1), d[5, 4] + Cost(4, {2, 3}, 1)}

= min {4 + 30, 8 + 27, 11 + 36}

= min{34, 35, 47} = 34

**Step 5 :** In this step, we will find the minimum distance by visiting 4 cities as an intermediate city.

Cost(1, {2, 3, 4, 5}, 1) = min { d[1, 2] + Cost(2, {3, 4, 5}, 1), d[1, 3] + Cost(3, {2, 4, 5}, 1), d[1, 4] + Cost(4, {2, 3, 5}, 1) , d[1, 5] + Cost(5, {2, 3, 4}, 1)}

= min { 24 + 25, 11 + 26, 10 + 23, 9 + 34 }

= min{49, 37, 33, 43} = 33

Thus, minimum length tour would be of 33.

**Trace the path**:

- Let us find the path that gives the distance of 33.
- Cost(1, {2, 3, 4, 5}, 1) is minimum due to d[1, 4], so move from 1 to 4. Path = {1, 4}.
- Cost(4, {2, 3, 5}, 1) is minimum due to d[4, 5], so move from 4 to 5. Path = {1, 4, 5}.
- Cost(5, {2, 3}, 1) is minimum due to d[5, 2], so move from 5 to 2. Path = {1, 4, 5, 2}.
- Cost(2, {3}, 1) is minimum due to d[2, 3], so move from 2 to 3. Path = {1, 4, 5, 2, 3}.

All cities are visited so come back to 1. Hence the optimum tour would be 1 – 4 – 5 – 2 – 3 – 1.

## Some Popular Problems Solved using Dynamic Programming

- Binomial Coefficient
- Making a Change
- Knapsack Problem
- Multistate Graph Problem
- Optimal Binary Search Tree
- Matrix Chain Multiplication
- Longest Common Subsequence
- Bellman-Ford (Single Source Shortest Path) Algorithm
- Floyd-Warshall (All Pair Shortest Path) Problem
- Assembly Line Scheduling
- Travelling Salseman Problem
- Flow Shop Scheduling

Additional Reading: Click to read more