回溯法求解旅行商问题

#include <iostream>#include <cstdlib>using namespace std;#define n 5#define ML 1000000int g[n][n]={{0,10,ML,4,12},{10,0,15,8,5},{ML,15,0,7,30},{4,8,7,0,6},{12,5,30,6,0}};int x[n]= {0,1,2,3,4},bestx[n+1]= {0},bestl=ML,cl=0;void Traveling(int t){if(t==n-1){if(g[x[n-1]][0]!=ML&&(cl+g[x[n-1]][0]<bestl)){for(int j=0;j<n;j++){bestx[j]=x[j];}bestl=cl+g[x[n-1]][0];}return;}for(int j=t+1;j<n;j++){if(g[x[t]][x[j]]!=ML&&(cl+g[x[t]][x[j]]<bestl)){swap(x[t+1],x[j]);cl+=g[x[t]][x[t+1]];Traveling(t+1);cl-=g[x[t]][x[t+1]];swap(x[t+1],x[j]);}}}int main(){Traveling(0);cout<<bestl<<endl;for(int i=0;i<n;i++){cout<<bestx[i]+1<<" ";}return 0;}