Travelling Salesman Problem
Subject: Design and Analysis of Algorithm Lab Project Submitted by: Sukhendu Sekhar Guria
Traveling Salesman ProblemThe traveling salesman problem consists of a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one (e.g. the hometown) and returning to the same city. The challenge of the problem is that the traveling salesman wants to minimize the total length of the trip.
The traveling salesman problem can be described as follows:
TSP = {(G, f, t): G = (V, E) a complete graph, f is a function V×V → Z,
t ∈ Z,
G is a graph that contains a traveling salesman tour with cost that does not exceed
t}. Example:
Consider the following set of cities:
The problem lies in finding a minimal path passing from all vertices once. For example the path Path1 {A, B, C, D, E, A} and the path Path2 {A, B, C, E, D, A} pass all the vertices but Path1 has a total length of 24 and Path2 has a total length of 31.
Dynamic Programming Approach for Solving TSP
Pseudo code:
Implementation:
#include <stdio.h>
int matrix[25][25], visited_cities[10], limit, cost = 0; int tsp(int c)
{
int count, nearest_city = 999; int minimum = 999, temp;
for (count = 0; count < limit; count++)
{
if ((matrix[c][count] != 0) && (visited_cities[count] == 0))
{
if (matrix[c][count] < minimum)
{
minimum = matrix[count][0] + matrix[c][count];
}
temp = matrix[c][count]; nearest_city = count;
}
}
if (minimum != 999)
{
cost = cost + temp;
}
return nearest_city;
}
void minimum_cost(int city)
{
int nearest_city; visited_cities[city] = 1; printf("%d ", city + 1); nearest_city = tsp(city); if (nearest_city == 999)
{
nearest_city = 0;
printf("%d", nearest_city + 1);
cost = cost + matrix[city][nearest_city]; return;
}
minimum_cost(nearest_city);
}
int main()
{
int i, j;
printf("Enter Total Number of Cities:\t"); scanf("%d", &limit);
printf("\nEnter Cost Matrix\n"); for (i = 0; i < limit; i++)
{
printf("\nEnter %d Elements in Row[%d]\n", limit, i + 1);
for (j = 0; j < limit; j++)
{
scanf("%d", &matrix[i][j]);
}
visited_cities[i] = 0;
}
printf("\nEntered Cost Matrix\n"); for (i = 0; i < limit; i++)
{
printf("\n");
for (j = 0; j < limit; j++)
{
printf("%d ", matrix[i][j]);
}
}
printf("\n\nPath:\t"); minimum_cost(0); printf("\n\nMinimum Cost: \t"); printf("%d\n", cost);
return 0;
}
Output:
Complexity:
In the dynamic algorithm for TSP, the number of possible subsets can be at most N x 2N. Each subset can be solved in O(N) times. Therefore, the time complexity of this algorithm would be O(N2 x 2N)
Greedy Algorithm:
Pseudo code:
X[1] HOME;
FOR I 1 TO N-1 DO
SELECT (U,V) WITH MIN WEIGHT SUCH THAT (U,V)ϵE, UϵS, VϵS
X[… S Sá´—{V};…
UNTIL V≠{}
RETURN SOMETHING;
Implementation :
#include <bits/stdc++.h> using namespace std;
void findMinRoute(vector<vector<int>> tsp)
{
int sum = 0;
int counter = 0; int j = 0, i = 0;
int min = INT_MAX;
map<int, int> visitedRouteList; visitedRouteList[0] = 1;
int route[tsp.size()];
while (i < tsp.size() && j < tsp[i].size())
{
if (counter >= tsp[i].size() - 1)
{
break;
}
if (j != i && (visitedRouteList[j] == 0))
{
if (tsp[i][j] < min)
{
min = tsp[i][j]; route[counter] = j + 1;
}
}
j++;
if (j == tsp[i].size())
{
sum += min;
min = INT_MAX; visitedRouteList[route[counter] - 1] = 1;
j = 0;
i = route[counter] - 1; counter++;
}
}
i = route[counter - 1] - 1; for (j = 0; j < tsp.size(); j++)
{
if ((i != j) && tsp[i][j] < min)
{
min = tsp[i][j]; route[counter] = j + 1;
}
}
sum += min;
cout << ("Minimum Cost is : "); cout << (sum);
}
int main()
{
int V;
printf("Enter Edge: "); cin >> V;
vector<vector<int>> graph(V, vector<int>(V)); printf("Enter %dX%d Vertices:\n", V, V);
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
cin >> graph[i][j];
}
}
int S = graph[0][0]; findMinRoute(graph); return 0;
}
Complexity:
Time Complexity: O(N2*log2N) Auxiliary Space: O(N)
0 Comments