内容发布更新时间 : 2024/12/25 13:13:09星期一 下面是文章的全部内容请认真阅读。

}

}

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 q; int low,up;

10