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.
Traveling salesman problem

Complexity Analysis of Traveling salesman problem

Dynamic programming creates n.2n 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(n22n). 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.

2411109
82511
261287
1123246
54811

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.


Additional Reading: Click to read more

You may also like...

Leave a Reply

Your email address will not be published.