Travelling Salesman Problem
Problem Statement
A traveller needs to visit all the cities from a list, where distances between all the cities are known and each city should be visited just once. What is the shortest possible route that he visits each city exactly once and returns to the origin city?
Solution
Travelling salesman problem is the most notorious computational problem. We can use brute-force approach to evaluate every possible tour and select the best one. For n number of vertices in a graph, there are (n - 1)! number of possibilities.
Instead of brute-force using dynamic programming approach, the solution can be obtained in lesser time, though there is no polynomial time algorithm.
Let us consider a graph G = (V, E), where V is a set of cities and E is a set of weighted edges. An edge e(u, v) represents that vertices u and v are connected. Distance between vertex u and v is d(u, v), which should be non-negative.
Suppose we have started at city 1 and after visiting some cities now we are in city j. Hence, this is a partial tour. We certainly need to know j, since this will determine which cities are most convenient to visit next. We also need to know all the cities visited so far, so that we don't repeat any of them. Hence, this is an appropriate sub-problem.
For a subset of cities S Є {1, 2, 3, ... , n} that includes 1, and j Є S, let C(S, j) be the length of the shortest path visiting each node in S exactly once, starting at 1 and ending at j.
When |S| > 1, we define C(S, 1) = ∝ since the path cannot start and end at 1.
Now, let express C(S, j) in terms of smaller sub-problems. We need to start at 1 and end at j. We should select the next city in such a way that
Algorithm: Traveling-Salesman-Problem
C ({1}, 1) = 0
for s = 2 to n do
for all subsets S Є {1, 2, 3, … , n} of size s and containing 1
C (S, 1) = ∞
for all j Є S and j ≠ 1
C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j}
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)
Example1
Consider the following graph starting from vertex 1. Find the optimal tour so that a person may come back to source of journey visiting all the vertices using DP approach
6 5
V1 V2
1
8
7
solution :
9
7
3
V4 V3 4 2
The Distance matrix can be given by V1 V2 V3 V4 V1 0 5 7 7
V2 6 0 3 ∞ V3 1 9 0 4 V4 8 ∞ 2 0
Step 1: Let S= Φ then
Cost(2,Φ,1) = d21 = 6
Cost(3,Φ,1) = d31 = 1
Cost(4,Φ,1) = d41 = 8
Step 2:
For S= 1
Using cost (i,S) = min {dj + cost( j, S-{j})}
Hence from vertex 2 to 1, vertex 3 to 1 and vertex 4 to 1 by
Considering intermediate path lengths we will calculate total optimum cost
Cost (2,{3},1) = d23 +cost (3,Φ, 1)
= 3+1 = 4
Cost (2,{4}, 1) = d24+ cost (4,Φ,1)
= ∞+8 = ∞
Cost(3,{2},1) = d32 + cost( 2,Φ,1)
= 9 + 6 = 15
Cost (3,{4},1) = d34 + cost( 4,Φ,1)
= 4+8 = 12
Cost (4,{2}, 1) = d42 + cost(2,Φ,1)
= ∞ + 6= ∞
Cost(4,{3},1) = d43 + cost( 3,Φ, 1)
= 2+1 = 3
Step 3 : For {S} = 2
Cost(2,{3,4},1) = min{[d23 + Cost(3,{4},1)],[d24 + cost(4,{3},1]} =min{ [3+12], [ ∞+3 ] }
=15
Cost(3,{2,4},1) = min{ [d32 + cost(2,{4},1) ] , [d34 + cost(4,{2},1)]} = min {[9+∞], [4+∞]} = ∞
Cost(4,{2,3},1) = min { [d42 + cost(2,{3},1)], [d43 + cost(3, {2},1)] } = min{ [ ∞+ 4],[2+15] }
= 17
Step 4: For (S) = 3
Cost (1,{2,3,4},1) = min [ d12+ cost(2,{3,4},1) ]
[ d13 + cost(3,{2,4},1) ]
[ d14 + cost(4,{2,3} ,1) ]
= min{ [5+15],[7+∞], [7+17]
= min{20, ∞, 24}
= 20
Thus the optimal tour is of path length 20, and optimal tour is 1→ 2 → 3 → 4 → 1
Example 2
In the following example, we will illustrate the steps to solve the travelling salesman problem.
From the above graph, the following table is prepared.
S = Φ
Cost(2,{ Φ},1} = d21 = 5
Cost(3, { Φ},1} =d31 = 6
Cost(4, { Φ},1} =d41 = 8
S = 1
Cost(2,{ 3},1} =d23+ cost(3,{ Φ}, 1) = 9 +6 = 15
Cost(2,{ 4},1} = d24 + Cost(4, { Φ},1} = 10+8 = 18
Cost(3, { 2},1} = d32 + Cost(2,{ Φ},1} = 13+5 =18
Cost(3, { 4},1} = d34 + Cost(4, { Φ},1}= 12+8=20 Cost(4, { 2},1} = d42 + Cost(2,{ Φ},1} = 8+5 =13 Cost(4, { 3},1} = d43 + Cost(3, { Φ},1} = 9+6 =15
S = 2
Cost(2,{ 3,4},1} = min { d23 + Cost(3, { 4},1} d24 + cost(4, {3},1} =
Cost(3, { 2,4},1} min { d32+cost(2,{4},1) d34 +cost(4,{2},1) =
Cost(4, { 2,3},1} = min {d42+cost(2, {3},1} d43+cost(3,{2},1}
=
S = 3
Cost(1,{2,3,4},1) = min {d12+cost(2,{3,4},1) d13+cost(3,{2,4},1)
d14 +cost(4,{2,3},1)
Example 3
Distance Matrix
1 2 3 4
1 0 10 15 20
2 5 0 9 10
3 6 13 0 12
4 8 8 9 0
Step 1: Let S= Φ then
cost(2, {Φ},1) = d21 =5
cost(3, {Φ},1) =d31 =6
cost(4, {Φ},1) =d41 =8
Step 2: Let S= 1 then
cost (2, {3},1) = d23 + cost(3, {Φ},1) = 9+6 =15 cost (2, {4},1) = d24 +cost(4, {Φ}, 1) = 10+8 =18 cost(3, {2},1) = d32+ cost(2, {Φ},1)= 13+5 =18 cost(3, {4},1) = d34 + cost(4, {Φ}, 1) =12+8 =20 cost(4, {2},1) = d42+ cost(2, {Φ},1)= 8+5=13 cost(4, {3},1) =d43 + cost(3, {Φ},1) =9+6=15
Step 3: Let S= 2 then
cost (2, {3,4},1) min {d23+cost(3,{4},1)=9+20=29 d24+ cost(4,{3},1)=10+15=25
=25
cost(3, {2,4},1) = min { d32+cost(2{4},1)= 13+18=31 d34+cost(4,{2},1)=12+13=25
=25
cost(4, {2,3},1) = min {d42+ cost(4, {3},1)=8+15=23 d43+ cost(3, {2},1)=9+18=27
=23
Step 4: Let S= 3 then
cost(1,{2,3,4},1) = min{ d12+cost(2, {3,4},1)=10+25=35 d13+cost(3,{2,4},1)=15+25=40
d14+cost(4,{2,3},1)=20+23=43
= 35
1------- 2------4 -----3------1
Example 4:
Generate travelling salesman path. Write algorithm. Explain Complexity
0 20 25 30
10 0 12 18
9 15 0 11
7 14 16 0
Comments
Post a Comment