#include<iostream>#include<bits/stdc++.h>using namespace std;const int noEdge=65535;class Traveling{public:void BackTrack(int i);int n;//图G的顶点数 int *x;//当前的解 int *bestx; // 当前的最优解 int **a; // 图G的临界矩阵 int cc;// 当前费用 int bestc; //当前最优花费的值 // int noEdge 无边标记 };void Traveling::BackTrack(int i){if(i == 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 j=1;j<=n;j++){bestx[j]=x[j];}bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];}}else{for(int j=i;j<=n;j++){if(a[x[i-1]][x[j]] != noEdge && (cc+a[x[i-1]][x[j]]<bestc||bestc == noEdge)){swap(x[i],x[j]);cc+=a[x[i-1]][x[i]];BackTrack(i+1);cc-=a[x[i-1]][x[i]];swap(x[i],x[j]);}}}} int TSP(int **a,int v[],int n){Traveling Y;Y.x = new int [n+1];for(int i=1;i<=n;i++){Y.x[i]=i;}Y.a= a;Y.n= n;Y.bestc = noEdge;Y.bestx = v; = 0;Y.BackTrack(2);cout<<"旅行售货员问题的最优路径：";for(int i=1;i<=n;i++){cout<<Y.bestx[i]<<" ";}cout<<1<<endl;delete []Y.x;return Y.bestc; }int main(){int n;cout<<"输入城市的个数";cin>>n;int **vector = new int *[n+1];for(int i=1;i<=n;i++){vector[i] = new int [n+1];}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){vector[i][j]= noEdge;}}int x;cout<<"输入城市间存在的通路的个数";cin>>x;cout<<"输入数据的形式为：(1 2 3)"<<endl;int index_i,index_j,value;for(int i=0;i<x;i++){cin>>index_i>>index_j>>value;vector[index_i][index_j]=value;vector[index_j][index_i]=value;}cout<<"输出临界矩阵"<<endl; for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<setw(5)<<vector[i][j]<<" ";}cout<<endl;}int *v = new int [n+1];cout<<"旅行售货员问题的最优值为:"<<TSP(vector,v,n)<<endl;}
如果觉得《算法设计与分析——回溯法——旅行售货员问题》对你有帮助，请点赞、收藏，并留下你的观点哦！
