旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 ——————百度百科

#include<iostream>
#include<algorithm>
#define MAX 20
using  namespace std;
int n;                              //城市的个数。 
int city_distance[MAX][MAX];       //城市间的距离矩阵。 
int current_steps[MAX];           //当前路线。 
int best_route[MAX]  = {0};      //最佳路线。 
long shortest_path = 0xffff;    //最短路径长度,起始值为一个相对大的数。 
int current_distance = 0;      //当前累加起来的路径长。 
void backpack(int t=2){
     if(t>n){//
        if((city_distance[current_steps[n]][1])&&(city_distance[current_steps[n]][1]+current_distance<shortest_path)){//贪心,找更小的路径 
		//最后一个城市加上最后一个城市的距离，将结果与向前最短路径长度比较，若更小，则修改其值。 
		//并把走城市的最佳路线也修改一遍。 
              shortest_path = city_distance[current_steps[n]][1]+current_distance;//加上最后一个城市到起始城市的距离，形成环路。 
              for(int i = 1;i<=n;i++){
                 best_route[i] = current_steps[i];//将当前可能的路线替换之前的最佳路线。 
              }
        }
     }else{
         for(int i = t;i<=n;i++){
            if((city_distance[current_steps[t-1]][current_steps[i]])&&(current_distance+city_distance[current_steps[t-1]][current_steps[i]]<shortest_path)){
                swap(current_steps[t],current_steps[i]);   //1,2,3,4 回溯 --> 1,2,3,4 ,下一种可能--> 1,2,4,3 回溯-->1,2,3,4…… 
                current_distance+=city_distance[current_steps[t-1]][current_steps[t]];
                backpack(t+1);//递归,从当前层深入下一层,下一层重复上述操作。(这样就可以遍历所有可能,起始1是固定的)。 
                current_distance-=city_distance[current_steps[t-1]][current_steps[t]];//回溯,将修改的步骤恢复到上一个状态。 
                swap(current_steps[t],current_steps[i]);
            }
         }
    }
}
int main(){
    cout<<"输入城市个数:"<<endl;
    cin>>n;//顶点数
    while(n<=1){
    	cout<<"请输入大于1的数"<<endl;//不允许城市个数小于等于1。 
		cin>>n; 
	}
    for(int i = 1;i<=n;i++){
         current_steps[i] = i;
    }
    cout<<"输入城市之间的距离(0表示城市间不通):"<<endl;
    for(int i = 1;i<=n;i++){//输入距离矩阵。 
        for(int j = 1;j<=n;j++){
            cin>>city_distance[i][j];
        }
    }
    backpack();//默认第一个城市为起始城市。 
    cout<<"最短环路距离为: "<<shortest_path<<endl;
    cout<<"经过城市顺序依次为:";
    for(int i = 1;i<=n;i++){
       cout<<best_route[i]<<" ";
    }
    cout<<best_route[1]<<endl;
    return 0;
}

实现思想:
通过递归与回溯遍历所有的可能，后通过贪心选择最佳路线和最短环路距离。

测试样例一:

测试数据：
0 7 5 2
7 0 15 8
5 15 0 3
2 8 3 0
运行结果：

测试样例二：

测试数据:
0 8 2 6 7 0
8 0 9 5 4 4
2 9 0 0 2 3
6 5 0 0 8 0
7 4 2 8 0 2
0 4 3 0 2 0
运行结果: