The travelling salesman problem is a popular optimization problem in computer-science and mathematics. All students of computer science will study this problem at some point in their academic paths.
The motivation behind the Travelling Salesman Problem is the problem faced by a salesperson who needs to visit a number of customers located in different cities and tries to find the shortest round trip accomplishing this task. There are numerous practical problems that are based out of TSP, optimizing delivery routes for couriers and delivery services, planning circuit design on computer chips, and even in DNA sequencing.
Objective: If there are ‘n’ cities and the cost of going from any one city to another is given, then the travelling salesman problem is to find the cheapest way to travel to all cities and return back to the original city.
Brute-Force Method:
In the brute-force method, we will calculate all the paths that touch all the nodes and calculate the cost for all the paths. The path with the lowest cost is then chosen. The issue with this method is the time complexity in calculating the costs for all paths.
Nearest Neighbour Method:
The next method is followed in a way to apply common sense. Visit the nearest neighbour, and then continue to do so until you visit all the nodes and then return to the original node. At a particular node, ignore the nodes that have already been visited before.
The Branch & Bound Approach:
With branch and bound, we first start by calculating a bound on the cost of a solution. If our current cost already exceeds that bound, we immediately backtrack, thus saving time. Though theoretically sound, the real challenge of the branch-and-bound approach to the TSP lies in its practical implementation as it can become quite resource-intensive for larger lists of cities. It’s an important method in computer science for solving heavy computational problems more efficiently.
Solving the TSP can be challenging due to its computational complexity. As the number of cities increases, the problem becomes exponentially harder to solve. Additionally, approximating an optimal solution for large datasets can be time-consuming.
C Algorithm –
/*Branch and Bound Algorithm for Traveling Salesman Problem*/
#include<stdio.h>
#include<conio.h>
int a[10][10],visited[10],n,cost=0;
void get()
{
int i,j;
printf(“Enter No. of Cities: “);
scanf(“%d”,&n);
printf(“\nEnter Cost Matrix: \n”);
for( i=0;i<n;i++)
{
printf(“\n Enter Elements of Row # : %d\n”,i+1);
for( j=0;j<n;j++)
scanf(“%d”,&a[i][j]);
visited[i]=0;
}
printf(“\n\nThe cost list is:\n\n”);
for( i=0;i<n;i++)
{
printf(“\n\n”);
for( j=0;j<n;j++)
printf(“\t%d”,a[i][j]);
}
}
void mincost(int city)
{
int i,ncity;
visited[city]=1;
printf(“%d –>”,city+1);
ncity=least(city);
if(ncity==999)
{
ncity=0;
printf(“%d”,ncity+1);
cost+=a[city][ncity];
return;
}
mincost(ncity);
}
int least(int c)
{
int i,nc=999;
int min=999,kmin;
for(i=0;i<n;i++)
{
if((a[c][i]!=0)&&(visited[i]==0))
if(a[c][i]<min)
{
min=a[i][0]+a[c][i];
kmin=a[c][i];
nc=i;
}
}
if(min!=999)
cost+=kmin;
return nc;
}
void put()
{
printf(“\n\nMinimum cost:”);
printf(“%d”,cost);
}
void main()
{
clrscr();
get();
printf(“\n\nThe Path is:\n\n”);
mincost(0);
put();
getch();
}
Input Sample:
No. of Nodes : 6
Cost Matrix:
99 10 15 20 99 8
5 99 9 10 8 99
6 13 99 12 99 5
8 8 9 99 6 99
99 10 99 6 99 99
10 99 5 99 99 99
Hope this is useful, thank you
You may like to read: Program vs. Process vs. Thread, Basics of Microcontrollers & Arduino Uno, & Control Blocks in Scratch Programming
