还是回溯法,TSP问题

 //TSP问题,Travel Salesman Problem,又称为货担郎问题,邮递员问题

    
 //题目要求:从n个城市中的某一个出发,不重复的走网其余n-1个城市,并且回到起始点,
    
 //在所有可能的线路中,找出路径最短的一条
    
  
    
 //算法:还是用回溯法,解空间结构为排列树
    
 #define NUM 100
    
 int n;      //图G的顶点个数
    
 int m;      //图G的边数
    
 int a[NUM][NUM];    //图G的邻接矩阵
    
 int x[NUM];     //当前解
    
 int bestx[NUM];     //最优解,顺序输出即可
    
 int cc;         //当前费用
    
 int bestc;      //最优费用
    
 int NoEdge=-1;      //无边标记
    
  
    
 void init()
    
 {
    
     for(int i=0;i<NUM;i++)
    
     {
    
     for(int j=0;j<NUM;j++)
    
     {
    
         a[i][j]=NoEdge;
    
     }
    
     }
    
     bestc=NoEdge;
    
     cc=0;
    
     for(int i=1;i<=n;i++)
    
     {
    
     x[i]=i;
    
     }
    
 }
    
  
    
 void BackTrack(int t)       //t从2开始
    
 {
    
     //到达第n个节点
    
     if(t==n)
    
     {
    
     if(a[x[n-1]][x[n]]!=NoEdge && (a[x[n]][1]!=NoEdge) &&
    
             (cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc ||bestc==NoEdge))
    
     {
    
          for(int i=1;i<=n;i++)
    
          {
    
             bestx[i]=x[i];
    
          }
    
          bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];
    
     }
    
     }
    
     else
    
     {
    
     for(int i=t;i<=n;i++)
    
     {
    
         //如果上一个节点和它此后的节点有边,并且费用不高于现有的最优费用(bestc==NoEdge表示第一次)
    
         if(a[x[t-1]][x[i]]!=NoEdge && (cc+a[x[t-1]][x[i]]<bestc ||bestc==NoEdge))
    
         {
    
             swap(x[t],x[i]);
    
             cc+=a[x[t-1]][x[t]];
    
             BackTrack(t+1);
    
             cc-=a[x[t-1]][x[t]];
    
             swap(x[t],x[i]);
    
         }
    
     }
    
     }
    
  
    
 }//注,此时默认x[1]==1,即从第一个节点出发