Travelling salesman problem (TSP) is a famous computational problem in which a salesman has to visit all the given cities, each only once and return to the starting city with the shortest possible distance. This problem is an NP-hard problem, which means that the problem gets exponentially more complex as the number of cities increases. Despite its complexity, the TSP has many practical applications, including logistics, route optimization, and DNA sequencing.
In this blog, we will discuss the TSP problem and its implementation in C, C++, Java, and Python programming languages. We will provide code snippets in each language to demonstrate the implementation.
Understanding the Travelling Salesman Problem The Travelling Salesman Problem can be represented as a graph with nodes representing the cities and edges representing the distances between them. The goal is to find the shortest path that visits each city once and returns to the starting city.
The brute force approach to solve this problem is to calculate the distances between all possible permutations of cities and select the path with the shortest distance. However, this approach is not feasible for large numbers of cities as the number of permutations increases exponentially. Therefore, several algorithms have been developed to solve the TSP problem efficiently.
Implementation of the TSP Problem in C The implementation of the TSP problem in C involves the use of the branch and bound algorithm. The branch and bound algorithm is a divide and conquer technique that solves the TSP problem by dividing it into subproblems and solving each subproblem.
Here is the code snippet for implementing the TSP problem in C:
#include <stdio.h>
#include <limits.h>
#define V 4
int tsp(int graph[][V], int start_vertex, int bitmask, int visited_all, int dp[][16])
{
if (bitmask == visited_all)
{
return graph[start_vertex][0];
}
if (dp[start_vertex][bitmask] != -1)
{
return dp[start_vertex][bitmask];
}
int ans = INT_MAX;
for (int i = 0; i < V; i++)
{
if ((bitmask & (1 << i)) == 0)
{
int subproblem = graph[start_vertex][i] + tsp(graph, i, bitmask | (1 << i), visited_all, dp);
ans = (ans < subproblem) ? ans : subproblem;
}
}
dp[start_vertex][bitmask] = ans;
return ans;
}
int main()
{
int graph[][V] = { { 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 } };
int visited_all = (1 << V) - 1;
int dp[V][1 << V];
for (int i = 0; i < V; i++)
{
for (int j = 0; j < (1 << V); j++)
{
dp[i][j] = -1;
}
}
printf("The minimum distance is %d\n", tsp(graph, 0, 1, visited_all, dp));
return 0;
}
Implementation of the TSP Problem in C++ The implementation of the TSP problem in C++ involves the use of the same branch and bound algorithm used in C. Here is the code snippet for implementing the TSP problem in C++:
#include <iostream>
#include <vector>
#include <limits.h>
#define V 4
int tsp(int graph[][V], int start_vertex, int bitmask, int visited_all, int dp[][1<<V]) {
// If all the cities are visited, return the distance from last city to starting city
if(bitmask == visited_all) {
return graph[start_vertex][0];
}
// If we have already calculated the minimum distance for the current vertex and bitmask, return it
if(dp[start_vertex][bitmask] != -1) {
return dp[start_vertex][bitmask];
}
// Set initial distance as infinity
int ans = INT_MAX;
// Iterate through all the cities
for(int i=0; i<V; i++) {
// If city i is not visited yet
if((bitmask & (1<<i)) == 0) {
// Calculate the distance from current city to city i and recursively find the distance for the remaining cities
int subproblem = graph[start_vertex][i] + tsp(graph, i, bitmask | (1<<i), visited_all, dp);
// Update the minimum distance
ans = std::min(ans, subproblem);
}
}
// Store the calculated minimum distance in the dp table
dp[start_vertex][bitmask] = ans;
return ans;
}
int main() {
// Graph representation of cities and distances
int graph[][V] = { { 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 } };
// Total number of cities
int n = V;
// Calculate the bitmask for all cities visited
int visited_all = (1<<n) - 1;
// Initialize the dp table with -1
int dp[V][1<<V];
memset(dp, -1, sizeof(dp));
// Starting city is city 0
int start_vertex = 0;
// Call the tsp function and print the minimum distance
std::cout << "The minimum distance is " << tsp(graph, start_vertex, 1<<start_vertex, visited_all, dp) << std::endl;
return 0;
}
Implementation of the TSP Problem in Java The implementation of the TSP problem in Java also involves the use of the same branch and bound algorithm used in C and C++. Here is the code snippet for implementing the TSP problem in Java:
import java.util.*;
class TSP {
private static int tsp(int[][] graph, int start_vertex, int bitmask, int visited_all, int[][] dp) {
// If all the cities are visited, return the distance from last city to starting city
if(bitmask == visited_all) {
return graph[start_vertex][0];
}
// If we have already calculated the minimum distance for the current vertex and bitmask, return it
if(dp[start_vertex][bitmask] != -1) {
return dp[start_vertex][bitmask];
}
// Set initial distance as infinity
int ans = Integer.MAX_VALUE;
// Iterate through all the cities
for(int i=0; i<graph.length; i++) {
// If city i is not visited yet
if((bitmask & (1<<i)) == 0) {
// Calculate the distance from current city to city i and recursively find the distance for the remaining cities
int subproblem = graph[start_vertex][i] + tsp(graph, i, bitmask | (1<<i), visited_all, dp);
// Update the minimum distance
ans = Math.min(ans, subproblem);
}
}
// Store the calculated minimum distance in the dp table
dp[start_vertex][bitmask] = ans;
return ans;
}
public static void main(String[] args) {
// Graph representation of cities and distances
int[][] graph = { { 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 } };
// Total number of cities
int n = graph.length;
// Calculate the bitmask for all cities visited
int visited_all = (1<<n) - 1;
// Initialize the dp table with -1
int[][] dp = new int[n][1<<n];
for(int i=0; i<n; i++) {
Arrays.fill(dp[i], -1);
}
// Starting city is city 0
int start_vertex = 0;
// Call the tsp function and print the minimum distance
System.out.println("The minimum distance is " + tsp(graph, start_vertex, 1<<start_vertex, visited_all, dp));
}
}
Implementation of the TSP Problem in Python The implementation of the TSP problem in Python also involves the use of the same branch and bound algorithm used in C, C++, and Java. Here is the code snippet for implementing the TSP problem in Python:
import sys
INT_MAX = sys.maxsize
def tsp(graph, start_vertex, bitmask, visited_all, dp):
# If all the cities are visited, return the distance from last city to starting city
if(bitmask == visited_all):
return graph[start_vertex][0]
# If we have already calculated the minimum distance for the current vertex and bitmask, return it
if(dp[start_vertex][bitmask] != -1):
return dp[start_vertex][bitmask]
# Set initial distance as infinity
ans = INT_MAX
# Iterate through all the cities
for i in range(len(graph)):
# If city i is not visited yet
if((bitmask & (1<<i)) == 0):
# Calculate the distance from current city to city i and recursively find the distance for the remaining cities
subproblem = graph[start_vertex][i] + tsp(graph, i, bitmask | (1<<i), visited_all, dp)
# Update the minimum distance
ans = min(ans, subproblem)
# Store the calculated minimum distance in the dp table
dp[start_vertex][bitmask] = ans
return ans
if __name__ == '__main__':
# Graph representation of cities and distances
graph = [[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]]
# Total number of cities
n = len(graph)
# Calculate the bitmask for all cities visited
visited_all = (1<<n) - 1
# Initialize the dp table with -1
dp = [[-1]*(1<<n) for i in range(n)]
# Starting city is city 0
start_vertex = 0
# Call the tsp function and print the minimum distance
print("The minimum distance is", tsp(graph, start_vertex, 1<<start_vertex, visited_all, dp))
The Travelling Salesman Problem (TSP) is a famous problem in the field of computer science, which involves finding the shortest possible route that a travelling salesman can take to visit a given set of cities and return to his starting point. The problem is NP-hard, and several algorithms have been proposed to solve it. In this blog post, we have discussed one of the most popular algorithms for solving the TSP problem, which is the branch and bound algorithm. We have also provided the implementation of the TSP problem in C, C++, Java, and Python programming languages using the branch and bound algorithm.
