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ⁿ 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ⁿ). 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