}
}
cin>>distance[i][j];
//生成过程矩阵
process=new int*[city_number]; for(i=0;i process[i]=new int[1<<(city_number-1)]; //动态规划法求最短路径 void Tsp::getShoretstDistance() { //对于数字x，要看它的第i位是不是1，通过判断布尔表达式 (((x >> int i,j,k; //初始化第一列 for(i=0;i //初始化剩余列 for(j=1;j<(1<<(city_number-1));j++) { for(i=0;i process[i][j]=0x7ffff;//设0x7ffff为无穷大 process[i][0]=distance[i][0]; (i - 1) ) & 1) == 1的真值来实现 if(((j>>(i-1))&1)==1) { 6 } continue; for(k=1;k //不能达到k城市 if(((j>>(k-1))&1)==0) { } if(process[i][j]>distance[i][k]+process[k][j ^ (1 << (k - continue; 1))]) { process[i][j]=distance[i][k]+process[k][j ^ (1 << (k - 1))]; } //主函数 int main(void) { int city_number; while(cin>>city_number) { //初始化城市代价矩阵 //求出最短路径 } cout< } } } Tsp tsp(city_number); tsp.getShoretstDistance(); } 7 } return 0; 3、 回溯法 #define MAX 100 using namespace std; int n; //城市个数 int a[MAX][MAX]; //城市间距离 int x[MAX]; //记录路径 int bestx[MAX] = {0}; //记录最优路径 int bestp = 63355; //最短路径长 int cp = 0; //当前路径长 void backpack(int t){ if(t>n){ if((a[x[n]][1])&&(a[x[n]][1]+cp for(int i = t;i<=n;i++){ /*约束为当前节点到下一节点的长度不为0,限界为走过的长度+当前要走的长度之和小于最优长度*/ if((a[x[t-1]][x[i]])&&(cp+a[x[t-1]][x[i]] 8 } } } int main(){ cin>>n; //顶点数 for(int i = 1;i<=n;i++){ x[i] = i; } for(int i = 1;i<=n;i++){ for(int j = 1;j<=n;j++){ } } backpack(2); cout< if(i==j){ a[i][j]=0; }else{ } cin>>a[i][j]; 4、 分支限界法 #define INF 0x3f3f3f3f int n; int mp[100][100]; void in() { scanf(\ 9 for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(i==j) { mp[i][j]=INF; continue; } scanf(\ } } } struct node { int visp[22];//标记哪些点走了 int st;//起点 int st_p;//起点的邻接点 int ed;//终点 int ed_p;//终点的邻接点 int k;//走过的点数 int sumv;//经过路径的距离 int lb;//目标函数的值 bool operator <(const node &p )const { return lb>p.lb; } }; priority_queue 10