Travelling Salesman Problem in C and C++

Here you will find out about Traveling Salesman Problem (TSP) with example and furthermore get a

program that executes Traveling Salesman Problem in C and C++.

Let say there are a few towns (1, 2, 3, 4, 5). To work with the most pessimistic scenario let expect every

town associated with each different towns. Also, there is a Salesman living in town 1 and he needs to sell his

things in all towns by heading out and he needs to return to possess town 1.

He needs to travel every town precisely once, on the grounds that it is an exercise in futility

and vitality that returning to the same town. This is same as visiting every hub precisely once, which is Hamiltonian Circuit.

In any case, our problem is greater than the Hamiltonian cycle since this isn’t just barely discovering the

Hamiltonian way, yet in addition, we need to discover the most limited way.

At last, the problem is we need to visit every vertex precisely once with least edge cost in a chart.

Animal Force Approach takes O (nm) time since we need to

check (n-1)! ways (i.e all stages) and need to discover the least among them.

The right approach to this problem is explaining utilizing Dynamic Programming.

Dynamic Programming can be applied just if

the principle problem can be separated into sub-problems. How about we watch that.

Voyaging Salesman Problem (TSP) Using Dynamic Programming

Example Problem

Above we can see a total coordinated diagram and cost grid which incorporates separation between every town.

We can see that the cost framework is symmetric that implies a separation between town 2 to 3 is same as the separation between town 3 to 2.

Here the problem is making a trip salesman needs to discover his visit with the least cost.

Let’s assume it is T (1,{2,3,4}), implies, at first he is a town 1 and afterwards, he can go to any of {2,3,4}.

From that point to reach non-visited vertices (towns) turns into another problem. Here we can see that

principle problem spat into sub-problem, this is the property of dynamic programming.

Note: While ascertaining underneath right side qualities determined in base up way.

Red shading esteems taken from beneath estimations.

T ( 1, {2,3,4} ) = least of

= { (1,2) + T (2, {3,4} ) 4+6=10

= { (1,3) + T (3, {2,4} ) 1+3=4

= { (1,4) + T (4, {2,3} ) 3+3=6

Here least of over 3 ways is answer however we realize just estimations of (1,2) , (1,3) , (1,4) outstanding thing which is

T ( 2, {3,4} ) … are new problems now. First we need to tackle those and substitute here.

T (2, {3,4} ) = least of

= { (2,3) + T (3, {4} ) 2+5=7

= { (2,4) + T {4, {3} ) 1+5=6

T (3, {2,4} ) = least of

= { (3,2) + T (2, {4} ) 2+1=3

= { (3,4) + T {4, {2} ) 5+1=6

T (4, {2,3} ) = least of

= { (4,2) + T (2, {3} ) 1+2=3

= { (4,3) + T {3, {2} ) 5+2=7

T ( 3, {4} ) = (3,4) + T (4, {} ) 5+0=5

T ( 4, {3} ) = (4,3) + T (3, {} ) 5+0=5

T ( 2, {4} ) = (2,4) + T (4, {} ) 1+0=1

T ( 4, {2} ) = (4,2) + T (2, {} ) 1+0 = 1

T ( 2, {3} ) = (2,3) + T (3, {} ) 2+0 = 2

T ( 3, {2} ) = (3,2) + T (2, {} ) 2+0=2

Here T ( 4, {} ) is arriving at base condition in recursion, which returns 0 (zero ) separation.

This is the place we can discover last answer,

T ( 1, {2,3,4} ) = least of

= { (1,2) + T (2, {3,4} ) 4+6=10 in this way we need to include +1 in light of the fact that this way finishes with 3.

From that point, we need to arrive at 1 so 3->1 separation 1 will be included complete separation is 10+1=11

= { (1,3) + T (3, {2,4} ) 1+3=4 in this way we need to include +3 in light of the fact that this way finishes with 3.

From that point, we need to arrive at 1 so 4->1 separation 3 will be included complete separation is 4+3=7

= { (1,4) + T (4, {2,3} ) 3+3=6 in this way we need to include +1 in light of the fact that this way finishes with 3.

From that point, we need to arrive at 1 so 3->1 separation 1 will be included absolute separation is 6+1=7

Least separation is 7 which incorporates way 1->3->2->4->1.

In the wake of taking care of example problem, we can without much of a stretch compose recursive condition.

Recursive Equation

T (I , s) = min ( I , j) + T ( j , S – { j }) ) ; S!= Ø ; j € S ;

S is set that contains non visited vertices

= ( I, 1 ) ; S=ø, This is base condition for this recursive condition.

Here,

T (I, S) implies We are going from a vertex “I” and need to visit set of non-visited vertices “S” and need to return to vertex 1 (let we began from vertex 1).

( I, j ) means the cost of the way from the hub I to hub j

On the off chance that we watch the main recursive condition from a hub we are discovering the

cost to every single other hub (i,j) and from that hub to residual utilizing recursion ( T (j, {S-j}))

In any case, it isn’t ensured that each vertex is associated with another vertex then we

accept that cost as limitlessness. After that, we are taking least among all so the way which isn’t associated

get vastness in figuring and won’t be consider.

In the event that S is vacant, that implies we visited all hubs, we take

good ways from that last visited hub to hub 1 (first hub). Since in the

wake of visiting all he needs to return to the beginning hub.

Time Complexity

Since we are illuminating this utilizing Dynamic Programming,

we realize that the Dynamic Programming approach contains sub-problems.

Here in the wake of coming to ith hub finding staying least separation to that ith hub is a sub-problem.

In the event that we explain the recursive condition,

we will get all out (n-1) 2(n-2) sub-problems, which is O (n2n).

Each sub-problem will take O (n) time (discovering way to outstanding (n-1) hubs).

In this manner all-out time unpredictability is O (n2n) * O (n) = O (n22n)

Space multifaceted nature is likewise number of sub-problems which is O (n2n)

Program for Traveling Salesman Problem in C

#include<stdio.h>
 
int ary[10][10],completed[10],n,cost=0;
 
void takeInput()
{
	int i,j;
 
	printf("Enter the number of villages: ");
	scanf("%d",&n);
 
	printf("\nEnter the Cost Matrix\n");
 
	for(i=0;i < n;i++)
	{
		printf("\nEnter Elements of Row: %d\n",i+1);
 
		for( j=0;j < n;j++)
			scanf("%d",&ary[i][j]);
 
		completed[i]=0;
	}
 
	printf("\n\nThe cost list is:");
 
	for( i=0;i < n;i++)
	{
		printf("\n");
 
		for(j=0;j < n;j++)
			printf("\t%d",ary[i][j]);
	}
}
 
void mincost(int city)
{
	int i,ncity;
 
	completed[city]=1;
 
	printf("%d--->",city+1);
	ncity=least(city);
 
	if(ncity==999)
	{
		ncity=0;
		printf("%d",ncity+1);
		cost+=ary[city][ncity];
 
		return;
	}
 
	mincost(ncity);
}
 
int least(int c)
{
	int i,nc=999;
	int min=999,kmin;
 
	for(i=0;i < n;i++)
	{
		if((ary[c][i]!=0)&&(completed[i]==0))
			if(ary[c][i]+ary[i][c] < min)
			{
				min=ary[i][0]+ary[c][i];
				kmin=ary[c][i];
				nc=i;
			}
	}
 
	if(min!=999)
		cost+=kmin;
 
	return nc;
}
 
int main()
{
	takeInput();
 
	printf("\n\nThe Path is:\n");
	mincost(0); //passing 0 because starting vertex
 
	printf("\n\nMinimum cost is %d\n ",cost);
 
	return 0;
}

Output

Enter the number of villages: 4

Enter the Cost Matrix

Enter Elements of Row: 1
0 4 1 3

Enter Elements of Row: 2
4 0 2 1

Enter Elements of Row: 3
1 2 0 5

Enter Elements of Row: 4
3 1 5 0
The cost list is:
0 4 1 3
4 0 2 1
1 2 0 5
3 1 5 0

The Path is:
1—>3—>2—>4—>1

Minimum cost is 7

Program for Travelling Salesman Problem in C++

#include<iostream>
 
using namespace std;
 
int ary[10][10],completed[10],n,cost=0;
 
void takeInput()
{
	int i,j;
 
	cout<<"Enter the number of villages: ";
	cin>>n;
 
	cout<<"\nEnter the Cost Matrix\n";
 
	for(i=0;i < n;i++)
	{
		cout<<"\nEnter Elements of Row: "<<i+1<<"\n";
 
		for( j=0;j < n;j++)
			cin>>ary[i][j];
 
		completed[i]=0;
	}
 
	cout<<"\n\nThe cost list is:";
 
	for( i=0;i < n;i++)
	{
		cout<<"\n";
 
		for(j=0;j < n;j++)
			cout<<"\t"<<ary[i][j];
	}
}
 
int least(int c)
{
	int i,nc=999;
	int min=999,kmin;
 
	for(i=0;i < n;i++)
	{
		if((ary[c][i]!=0)&&(completed[i]==0))
			if(ary[c][i]+ary[i][c] < min)
			{
				min=ary[i][0]+ary[c][i];
				kmin=ary[c][i];
				nc=i;
			}
	}
 
	if(min!=999)
		cost+=kmin;
 
	return nc;
}
 
void mincost(int city)
{
	int i,ncity;
 
	completed[city]=1;
 
	cout<<city+1<<"--->";
	ncity=least(city);
 
	if(ncity==999)
	{
		ncity=0;
		cout<<ncity+1;
		cost+=ary[city][ncity];
 
		return;
	}
 
	mincost(ncity);
}
 
int main()
{
	takeInput();
 
	cout<<"\n\nThe Path is:\n";
	mincost(0); //passing 0 because starting vertex
 
	cout<<"\n\nMinimum cost is "<<cost;
 
	return 0;
}

Remark underneath on the off chance that you found any data off base or have questions in regards to Traveling Salesman Problem calculation.

1 thought on “Travelling Salesman Problem in C and C++”

Leave a Comment

error: Alert: Content is protected!!