• 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.

• Illustration:

• 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;  
}