# Backtracking method of traveling salesman problem

• ### Problem Description:

This problem requires finding the shortest path between n given cities, so that we can only visit each city once before returning to the triggered city.

• ### resolvent:

Backtracking is a brute force algorithm. Try all the possibilities once and find the best solution. The subset tree is used here. Because you can't go to a city many times, add the mark of a city. The initial value is 0. If you go there, it becomes 1.

• ### Code:

```/*
Backtracking (subset tree)
*/
#include <stdio.h>
# include <stdlib.h>
# include <time.h>
#define N 200 / / number of cities
#Define no? Path - 1 / / no path
#define MAX_WEIGHT 4000
int City_Graph[N+1][N+1];  //Save map information
int x[N+1];                //x[i] save the cities traversed in step I
int isIn[N+1];             //Save whether city i has joined the path
int bestw;                 //Total weight of optimal path
int cw;                    //Total weight of current path
int bw;                    //Total weight after depth search
int bestx[N+1];            //optimal path
//-----------------------------------------------------------------
void Travel_Backtrack(int t)
{   //Recursive method
int i,j;
if(t>N)
{                         //It's done. Output the result.
for(i=1;i<=N;i++)            //Output current path
printf("%d ",x[i]);
printf("\n");
bw = cw + City_Graph[x[N]][1]; //To return to the starting point, add the distance from the nth to the first
if(bw < bestw) //Select the optimal total weight
{
for (i=1;i<=N;i++)
{
bestx[i] = x[i];  //Save the path of each step
}
bestw = bw; // Update the optimal solution
}
return;
}
else
{
for(j=2;j<=N;j++)//Since the starting point is No. 1, No. 1 does not meet the following if condition when backtracking later
{           //Find the city you can go to in step t
if(City_Graph[x[t-1]][j] != NO_PATH && !isIn[j] /*&& cw<bestw*/)//Pruning condition: reachable and not added to the path, and the current total weight is less than the optimal weight
{
isIn[j] = 1; // The sign passed
x[t] = j;
cw += City_Graph[x[t-1]][j];
Travel_Backtrack(t+1);
isIn[j] = 0;
x[t] = 0;
cw -= City_Graph[x[t-1]][j];
}
}
}
}
int main(void)
{
int i;
int j;
srand((unsigned)time(NULL));
for(i = 1; i <= N; i++) {
for(j = 1; j <= N; j++) {
int num = 0;
num = rand() % 201;
City_Graph[i][j] = num;
printf("%d ", City_Graph[i][j]);
}
}
//Test recursion, initializing
for (i=1;i<=N;i++)
{
x[i] = 0;               //Indicates that step i has not been solved
bestx[i] = 0;           //There is no optimal solution
isIn[i] = 0;            //Indicates that the ith city has not joined the path
}

x[1] = 1;                   //Step 1: go to city 1
isIn[1] = 1;                //First city joining path
bestw = MAX_WEIGHT;  		// Because the minimum value is required to be set to the maximum value first
cw = 0;  					// Used to save every possible path and value
Travel_Backtrack(2);        //Choose a city from the second step
printf("The optimal value is%d\n",bestw);
printf("The optimal solution is:\n");
for(i=1;i<=N;i++)
{
printf("%d ",bestx[i]);
}
printf("\n");
return 0;
}
```

Keywords: less

Added by cwarn23 on Sat, 19 Oct 2019 01:03:08 +0300