Python Laboratory 2023-24
Program 6
Implementation of TSP using heuristic approach
Algorithm for Traveling Salesman Problem
We will use the dynamic programming approach to solve the Travelling Salesman Problem (TSP).
A graph G=(V, E), which is a set of vertices and edges.
V is the set of vertices.
E is the set of edges.
Vertices are connected through edges.
Dist(i,j) denotes the non-negative distance between two vertices, i and j.
cities in that subset. Now cost(i, S, j) is defined in such a way as the length of the shortest path visiting node in S,
which is exactly once having the starting and ending point as i and j respectively.
For example, cost (1, {2, 3, 4}, 1) denotes the length of the shortest path where:
Starting city is 1
Cities 2, 3, and 4 are visited only once
The ending point is 1
The dynamic programming algorithm would be:
Set cost(i, , i) = 0, which means we start and end at i, and the cost is 0.
When |S| > 1, we define cost(i, S, 1) = where i !=1 . Because initially, we do not know the exact cost to
reach city i to city 1 through other cities.
Now, we need to start at 1 and complete the tour. We need to select the next city in such a way-
For the given figure, the adjacency matrix would be the following:
Dept. of AD, CIT, Gubbi 25
Python Laboratory 2023-24
dist(i,j) 1 2 3 4
1 0 10 15 20
2 10 0 35 25
3 15 35 0 30
4 20 25 30 0
Step 1) We are considering our journey starting at city 1, visit other cities once and return to city 1.
Step 2) S is the subset of cities. According to our algorithm, for all |S| > 1, we will set the distance cost(i, S, 1) =
. Here cost(i, S, j) means we are starting at city i, visiting the cities of S once, and now we are at city j. We set
this path cost as infinity because we do not know the distance yet. So the values will be the following:
Cost (2, {3, 4}, 1) = ; the notation denotes we are starting at city 2, going through cities 3, 4, and reaching 1.
And the path cost is infinity. Similarly-
cost(3, {2, 4}, 1) =
cost(4, {2, 3}, 1) =
Step 3) Now, for all subsets of S, we need to find the following:
cost(i, S, j)=min
That means the minimum cost path for starting at i, going through the subset of cities once, and returning to city
j. Considering that the journey starts at city 1, the optimal path cost would be= cost(1, {other cities}, 1).
Now S = {1, 2, 3, 4}. There are four elements. Hence the number of subsets will be 2^4 or 16. Those subsets are-
1) |S| = Null:
2) |S| = 1:
{{1}, {2}, {3}, {4}}
3) |S| = 2:
{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
4) |S| = 3:
{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}
Dept. of AD, CIT, Gubbi 26
Python Laboratory 2023-24
5) |S| = 4:
{{1, 2, 3, 4}}
As we are starting at 1, we could discard the subsets containing city 1.
The algorithm calculation:
10
2) |S| = 1:
= 45
3) |S| = 2:
cost (2, {3, 4}, 1) = min [ dist[2,3]+Cost(3,{4},1) = 35+50 = 85,
dist[2,4]+Cost(4,{3},1) = 25+45 = 70 ] = 70
cost (3, {2, 4}, 1) = min [ dist[3,2]+Cost(2,{4},1) = 35+45 = 80,
dist[3,4]+Cost(4,{2},1) = 30+35 = 65 ] = 65
cost (4, {2, 3}, 1) = min [ dist[4,2]+Cost(2,{3},1) = 25+50 = 75
dist[4,3]+Cost(3,{2},1) = 30+45 = 75 ] = 75
4) |S| = 3:
cost (1, {2, 3, 4}, 1) = min [ dist[1,2]+Cost(2,{3,4},1) = 10+70 = 80
dist[1,3]+Cost(3,{2,4},1) = 15+65 = 80
dist[1,4]+Cost(4,{2,3},1) = 20+75 = 95 ] = 80
So the optimal solution would be 1-2-4-3-1
Dept. of AD, CIT, Gubbi 27
Python Laboratory 2023-24
Output of Given Graph:
Minimum weight Hamiltonian Cycle:
10 + 25 + 30 + 15:= 80
Program:
Result:
Dept. of AD, CIT, Gubbi 28