回溯法解决TSP问题

 #include<iostream>

    
 #define  MAXSUM 100
    
 #define INF 65535
    
 using namespace std;
    
 class TSP{  //TSP类
    
 public:
    
     int bestv;  //最优解即最短路径
    
     int tempv;  //当前路径长度
    
     int node;   //节点个数
    
     int edge;   //无向边条数
    
     int adj[MAXSUM][MAXSUM];  //邻接矩阵存储无向边信息
    
     int *best_route;  //最优路径记录
    
     int *route;  //当前路径记录
    
     bool *vis;   //判断该节点是被否访问数组
    
 public:
    
     /* 初始化 */
    
     void Initial(){
    
     cout<<"please input the number of nodes and edge: "<<endl;
    
     cin>>node>>edge;
    
     bestv = INF;
    
     route = new int[node * 2];
    
     vis = new bool[node * 2];
    
     best_route = new int[node * 2];
    
     for(int i = 1;i <= node;i++)
    
         for(int j = 1;j <= node;j++)adj[i][j] = INF;
    
     cout<<"please input the two nodes and value of each edge(each edge is entered only once): "<<endl;
    
     for(int i = 1;i <= edge;i++){
    
         int st,ed,val;
    
         cin>>st>>ed>>val;
    
         adj[st][ed] = adj[ed][st] = val;
    
     }
    
     for(int i = 0;i <= node;i++)vis[i] = false;
    
     route[0] = 1;
    
     vis[1] = true;
    
     tempv = 0;
    
     }
    
     /* 判断该下标代表的城市否可选 */
    
     bool Judge(int index,int depth){
    
     if(depth != node - 1)
    
         if(adj[route[depth - 1]][index] != INF &&
    
            tempv + adj[route[depth - 1]][index] < bestv &&
    
            !vis[index])return true;
    
         else return false;
    
     else
    
         if(adj[route[depth - 1]][index] != INF &&
    
            adj[route[0]][index] != INF &&
    
            tempv + adj[route[depth - 1]][index] + adj[index][route[0]] < bestv &&
    
            !vis[index])return true;
    
         else return false;
    
     }
    
     /* 选择该城市时参数设置 */
    
     void EnterSet(int index,int depth){
    
     vis[index] = true;
    
     if(depth != node - 1)tempv += adj[route[depth - 1]][index];
    
     else tempv += adj[route[depth - 1]][index] + adj[route[0]][index];
    
     }
    
     /* 从该子树退出时参数恢复 */
    
     void OutSet(int index,int depth){
    
     vis[index] = false;
    
     if(depth != node - 1)tempv -= adj[route[depth - 1]][index];
    
     else tempv -= (adj[route[depth - 1]][index] + adj[route[0]][index]);
    
     }
    
     /* 保存最优路径 */
    
     void Save(){
    
     for(int i = 0;i < node;i++)best_route[i] = route[i];
    
     bestv = tempv;
    
     }
    
     /* TSP解决问题主函数 */
    
     void TSP_Solve(int depth){
    
     if(depth == node){
    
         Save();
    
         return;
    
     }
    
     for(int i = 1;i <= node;i++){
    
         if(Judge(i,depth)){
    
             route[depth] = i;
    
             EnterSet(i,depth);
    
             TSP_Solve(depth + 1);
    
             OutSet(i,depth);
    
         }
    
     }
    
     }
    
     /* 结果显示 */
    
     void Show(){
    
     for(int i = 0;i < node;i++)cout<<best_route[i]<<" -> ";
    
     cout<<route[0]<<endl;
    
     cout<<"the minest distance is: "<<bestv<<endl;
    
     }
    
 };
    
 TSP t;
    
 int main(){
    
     t.Initial();
    
     t.TSP_Solve(1);
    
     t.Show();
    
 }
    
 /*
    
 please input the number of nodes and edge:
    
 4 6
    
 please input the two nodes and value of each edge(each edge is entered only once):
    
 1 2 30
    
 1 3 6
    
 1 4 4
    
 2 3 5
    
 2 4 10
    
 3 4 20
    
  */
    
    
    
    
    代码解读