Solving Travelling Salesman Problem with C. The travelling salesman’s problem(TSP) is a classic algorithmic challenge in the field of computer science and operations research. It asks: given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the original city? this problem is NP-hard meaning that no efficient solution exists for solving all instances of the problem. However, some algorithms can solve specific instances or approximate solutions for larger instances.
Table of Contents
In this tutorial, we will explore a basic approach to solving the TSP using C language. We will implement a simple brute-force algorithm, which, despite its limitation in terms of computational efficiency, provides a foundational understanding of the problem and its complexities.
Understanding the Travelling Salesman Problem
The TSP can be represented as a graph, where vertices represent cities and edges represent the path between means cities with their associated distances. The goal is to find the Hamiltonian circuit of minimum weight. A Hamiltonian circuit is a path that visits each vertex exactly once and ends the starting vertices.
Solving the Travelling Salesman Problem
Data Representation
First, we need to represent the graph. A 2D array can store the distances between cities.
#include<stdio.h>
#include<stdbool.h>
#define INF 9999
#define N 4
// distances between cities
int distances [N][N] = {
{ 0,10,15,20},
{10,5,35,25},
{15,35,0,20},
{20,25,30,0}
};The Brute Force Approach
The Brute force approach checks every possible tour and selects the shortest. This approach is computationally expensive but a step forward to implement.
#include<stdio.h>
#include<stdbool.h>
#define INF 9999
#define N 4
// distances between cities
int distances [N][N] = {
{ 0,10,15,20},
{10,5,35,25},
{15,35,0,20},
{20,25,30,0}
};
int minTourLength = INF;
int minTour[N+1];
void copyArray(int *source, int *destination, int length){
for (int i=0;i<length;i++){
destination[i] = source[i];
}
}
// Function to calculate the total toure length
int calculatetourLength(int tour[N+1]){
int length = 0;
for (int i=0;i<length;i++){
length += distances[tour[i]][tour[i+1]];
}
return length;
}
void permute(int level, int currenttour[N+1], bool visited[N]){
if (level == N){
currenttour[N] = currenttour[0];
int currentlength = calculatetourLength(currenttour);
if(currentlength < minTourLength){
minTourLength=currentlength;
copyArray(currenttour, minTour, N+1) ; }
return;
}
for(int i=0;i<N;i++){
if (!visited[i]){
visited[i] = true;
currenttour[level] = i;
permute(level+1,currenttour, visited);
visited[i] = false;
}
}
}
void main(){
bool visited[N] = {false};
int currenttour[N+1];
currenttour[0] = 0;
visited[0] = true;
permute(1,currenttour,visited);
printf(" Minimum Tour Length = %d", minTourLength);
}Happy Coding & Learning
2 thoughts on “Solving Travelling Salesman Problem with C”