TSP.rar_tsp

#include <iostream> #include <stdlib.h> using namespace std; #define NoEdge -1 int n; int ad[13][13];//邻接矩阵 int* x = NULL;//到当前节点的路径的数组 int* bestx = NULL;//目前发现的最优旅行的整型数足 int cc;//当前节点的局部旅行的耗费 int bestc;//目前最优解的耗费 //交换两个整数的值 void swap(int& a, int& b) { int tmp = a; a = b; b = tmp; } void travel(int i) { if(i == n)//到达叶结点 { if(ad[x[n-1]][x[n]] != NoEdge && ad[x[n]][1] != NoEdge && (cc + ad[x[n-1]][x[n]] + ad[x[n]][1] < bestc || bestc == NoEdge)) {//找到更优的旅行，更新最优路径和最优耗费 for(int j = 1; j <= n; ++j) bestx[j] = x[j]; bestc = cc + ad[x[n-1]][x[n]] + ad[x[n]][1]; } } else//不是叶结点，尝试子树 { for(int j = i; j <= n; ++j) if(ad[x[i-1]][x[j]] != NoEdge && (cc + ad[x[i-1]][x[j]] < bestc || bestc == NoEdge)) {//可以移动到子树，则搜索该子树 swap(x[i], x[j]); cc += ad[x[i-1]][x[i]]; travel(i+1); cc -= ad[x[i-1]][x[i]]; swap(x[i], x[j]); } } } int main() { int i,j; scanf("%d",&n); //随机生成邻接矩阵 for(i = 1; i <= n; ++i) for(j = 1; j <= n; ++j) { scanf("%d",&ad[i][j]); if(ad[i][j] == 0) ad[i][j] = NoEdge; } //初始化变量 // for(i = 1; i <= n; ++i) // for(j =1; j <= n; ++j) // if(ad[i][j] == 0) // ad[i][j] = NoEdge; x = new int[n+1]; for(int k = 1; k <= n; ++k) x[k] = k; bestc = NoEdge; bestx = new int[n+1]; cc = 0; //搜索最优旅行 travel(2); //输出结果 cout<<"The best travel path is : "; for(j = 1; j <= n; ++j) cout<<bestx[j]<<'>'; cout<<bestx[1]<<endl; cout<<bestc<<endl; //释放空间 delete [] x; delete [] bestx; return 0; } //结束后，cc为0；