售货员问题 c语言,回溯法求旅行售货员问题

售货员问题 c语言,回溯法求旅行售货员问题"/>

售货员问题 c语言,回溯法求旅行售货员问题

#include

using namespace std;

const int INF = 10000000;

int n, cc = 0, bestc = INF;//n表示几个点，cc表示当前的距离bestc表示最优的距离，bests

//开始时赋值最大值

int **g;//二维数组g中存储各点间距离

int *x, *bestx;//x数组中存储点的信息

void travel(int t){

if(t == n){

if (g[x[t - 1]][x[t]] != INF && g[x[t]][1] != INF &&

(cc + g[x[t - 1]][x[t]] + g[x[t]][1] 

bestc=cc + g[x[t - 1]][x[t]] + g[x[t]][1];

for(int i = 0; i 

bestx[i] = x[i];

}

}

return ;

}

else{

for(int i = t; i 

if(g[x[t-1]][x[i]] != INF && g[x[t-1]][x[i]]+cc 

swap(x[i],x[t]);

cc += g[x[t-1]][x[t]];

travel(t+1);

cc -= g[x[t-1]][x[t]];

swap(x[i],x[t]);

}

}

}

}

void output(){

cout <

cout <

for(int i=2; i 

cout <

}

cout <

}

int main() {

n = 4;

g = new int*[n + 1];

x = new int[n + 1];

bestx = new int[n + 1];

for (int i = 0; i 

g[i] = new int[n + 1];

x[i] = i;

for (int j = 0; j 

g[i][j] = INF;

}

g[1][2] = g[2][1] = 30;

g[1][3] = g[3][1] = 6;

g[1][4] = g[4][1] = 4;

g[2][3] = g[3][2] = 5;

g[2][4] = g[4][2] = 10;

g[3][4] = g[4][3] = 20;

travel(2);//从第二层开始判断

output();

return 0;

}