(完整word版)北航研究生算法设计与分析Assignment_2

(完整word版)北航研究生算法设计与分析Assignment_2

用分支定界算法求以下问题：

某公司于乙城市的销售点急需一批成品，该公司成品生产基地在甲城市。甲城市与乙城市之间共有 n 座

城市，互相以公路连通。甲城市、乙城市以及其它各城市之间的公路连通情况及每段公路的长度由矩阵M1 给

出。每段公路均由地方政府收取不同额度的养路费等费用，具体数额由矩阵M2 给出。

请给出在需付养路费总额不超过 1500 的情况下，该公司货车运送其产品从甲城市到乙城市的最短运送

路线。

具体数据参见文件：

: 各城市之间的公路连通情况及每段公路的长度矩阵(有向图); 甲城市为城市Num.1，乙城市为城市

Num.50。

: 每段公路收取的费用矩阵（非对称）。

思想：利用Floyd算法的基本方法求解。

程序实现流程说明：

1.将和的数据读入两个50×50的数组。

2.用Floyd算法求出所有点对之间的最短路径长度和最小费用。

3.建立一个堆栈，初始化该堆栈。

4.取出栈顶的结点，检查它的相邻的所有结点，确定下一个当前最优路径上的结点，被扩展的结

点依次加入堆栈中。在检查的过程中，如果发现超出最短路径长度或者最小费用，则进行”剪

枝”，然后回溯。

5.找到一个解后，保存改解，然后重复步骤4。

6.重复步骤4、5，直到堆栈为空，当前保存的解即为最优解。

时间复杂度分析：

(完整word版)北航研究生算法设计与分析Assignment_2

Floyd算法的时间复杂度为，N为所有城市的个数。

O()

N

3

该算法的时间复杂度等于DFS的时间复杂度，即O(N+E)。其中，E为所有城市构成的有向连

通图的边的总数。但是因为采用了剪枝，会使实际运行情况的比较次数远小于E。

求解结果：

算法所得结果:

甲乙之间最短路线长度是:464

最短路线收取的费用是:1448

最短路径是:

1 3 8 11 15 21 23 26 32 37

39 45 47 50

C源代码（注意把与放到与源代码相同的目录下， 下面代码可直接复制运行）：

#include

#include

#include

#include

#define N 50

#define MAX 52

void input(int a[N][N],int b[N][N]);

void Floyd(int d[N][N]);

void fenzhi(int m1[N][N],int m2[N][N],int mindist[N][N],int mincost[N][N]);

int visited[N],bestPath[N];

(完整word版)北航研究生算法设计与分析Assignment_2

void main()

{

clock_t start,finish;

double duration;

int i,j,mindist[N][N],mincost[N][N],m1[N][N],m2[N][N]; /* m1[N][N]和m2[N][N]分别

代表题目所给的距离矩阵和代价矩阵 */

// int visited[N],bestPath[N];

FILE *fp,*fw;

// system("cls");

time_t ttime;

time(&ttime);

printf("%s",ctime(&ttime));

start=clock();

for(i=0;i

{

visited[i]=0;

bestPath[i]=0;

}

fp=fopen("","r"); /* 把文件中的距离矩阵m1读入数组mindist[N][N] */

if(fp==NULL)

{

(完整word版)北航研究生算法设计与分析Assignment_2

printf("can not open filen");

return;

}

for(i=0;i

for(j=0;j

fscanf(fp,"%d",&mindist[i][j]);

fclo(fp); /* 距离矩阵m1读入完毕 */

fp=fopen("","r"); /* 把文件中的代价矩阵m2读入数组mincost[N][N] */

if(fp==NULL)

{

printf("can not open filen");

return;

}

for(i=0;i

for(j=0;j

fscanf(fp,"%d",&mincost[i][j]);

fclo(fp); /* 代价矩阵m2读入完毕 */

input(m1,mindist); /* mindist[N][N]赋值给m1[N][N]，m1[N][N]代表题目中

的距离矩阵 */

input(m2,mincost); /* mincost[N][N]赋值给m2[N][N]，m2[N][N]代表题目

中的代价矩阵 */

for(i=0;i /* 把矩阵mindist[i][i]和mincost[i][i]的对角元素分别初

始化，表明城市到自身不连通，代价为0 */

{

(完整word版)北航研究生算法设计与分析Assignment_2

mindist[i][i]=9999;

mincost[i][i]=0;

}

Floyd(mindist); /* 用弗洛伊德算法求任意两城市之间的最短距离，结果存储

在数组mindist[N][N]中 */

/*

fw=fopen("","w");

for(i=0;i

for(j=0;j

fprintf(fw,"%4d ",mindist[i][j]);

fprintf(fw,"n");

}

fclo(fw);

// getchar();

//*/

Floyd(mincost); /* 用弗洛伊德算法求任意两城市之间的最小代价，结果存储

在数组mincost[N][N]中 */

/*

fw=fopen("","w");

for(i=0;i

for(j=0;j

fprintf(fw,"%4d ",mincost[i][j]);

fprintf(fw,"n");

(完整word版)北航研究生算法设计与分析Assignment_2

}

fclo(fw);

// getchar();

//*/

fenzhi(m1,m2,mindist,mincost); /* 调用分支定界的实现函数，寻找出所有的可行路径并依次

输出 */

finish=clock();

duration = (double)(finish - start) / CLOCKS_PER_SEC;

printf( "%f condsn", duration );

//*/

}

void Floyd(int d[N][N]) /* 弗洛伊德算法的实现函数 */

{

int v,w,u,i;

for(u=0;u

{

for(v=0;v

for(w=0;w

if(d[v][u]+d[u][w]

{

(完整word版)北航研究生算法设计与分析Assignment_2

//printf("v,w,u,d[v][u],d[u][w],d[v][w] %d %d %d %d %d %d",v+1,w+1,u+1,d[v][u],d[u][w],d[v][

w]);getchar();

d[v][w]=d[v][u]+d[u][w];

}

}

}

}

void input(int a[N][N],int b[N][N]) /* 把矩阵b赋值给矩阵a */

{

int i,j;

for(i=0;i

for(j=0;j

a[i][j]=b[i][j];

}

void fenzhi(int m1[N][N],int m2[N][N],int mindist[N][N],int mincost[N][N])

{

int stack[MAX],depth=0,next,i,j; /* 定义栈，depth表示栈顶指针；next指向每次遍历时当前

所处城市的上一个已经遍历的城市 */

int bestLength,shortestDist,minimumCost,distBound=9999,costBound=9999;

int cur,currentDist=0,currentCost=0; /* cur指向当前所处城市，currentDist和currentCost分别

表示从甲城市到当前所处城市的最短距离和最小代价，

currentDist和currentCost初值为0表示从甲城市出发

开始深度优先搜索 */

(完整word版)北航研究生算法设计与分析Assignment_2

stack[depth]=0; /* 对栈进行初始化 */

stack[depth+1]=0;

visited[0]=1; /* visited[0]=1用来标识从甲城市开始出发进行遍历，甲城

市已被访问 */

while(depth>=0) /* 表示遍历开始和结束条件，开始时从甲城市出发，栈空，

depth=0；结束时遍历完毕，所有节点均被出栈，故栈也为空，depth=0 */

/* 整个while（）循环体用来实现从当前的城市中寻找一个邻近的城市 */

{

cur=stack[depth]; /* 取栈顶节点赋值给cur，表示当前访问到第cur号城市 */

next=stack[depth+1]; /* next指向当前所处城市的上一个已经遍历的城市 */

for(i=next+1;i /* 试探当前所处城市的每一个相邻城市 */

{

if((currentCost+mincost[cur][N-1]>costBound)||(currentDist+mindist[cur][N-1]>=distBound)){

/* 所试探的城市满足剪枝条件，进行剪枝 */

//printf("here1 %d %d %d %d %d %d %dn",cur,currentCost,mincost[cur][49],costBound,curre

ntDist,mindist[cur][49],distBound); getchar();

//

printf("%d %d %d %d %d %d",cur,i,m1[cur][i],currentCost,mincost[cur][49],costBound);

getchar();

continue;

}

if(m1[cur][i]==9999) continue; /* 所试探的城市不连通 */

(完整word版)北航研究生算法设计与分析Assignment_2

if(visited[i]==1) continue; /* 所试探的城市已被访问 */

if(i break; /* 所试探的城市满足访问条件，找到新的可行城市，终止for循环 */

}

if(i==N) /* 判断for循环是否是由于搜索完所有城市而终止的，如果是（i==N），

进行回溯 */

{

// printf("here");getchar();

depth--;

currentDist-=m1[stack[depth]][stack[depth+1]];

currentCost-=m2[stack[depth]][stack[depth+1]];

visited[stack[depth+1]]=0;

}

el /* i!=N,表示for循环的终止是由于寻找到了当前城市的一个可行的邻近城

市 */

{

//

printf("%d %d %d %d %d %dn",cur,i,m1[stack[depth]][i],m2[stack[depth]][i],currentCost,curre

ntDist);//getchar();

currentDist+=m1[stack[depth]][i]; /* 把从当前所处城市到所找到的可行城市的距离加

入currentDist */

currentCost+=m2[stack[depth]][i]; /* 把从当前所处城市到所找到的可行城市的代价加

入currentCost */

depth++; /* 所找到的可行城市进栈 */

(完整word版)北航研究生算法设计与分析Assignment_2

stack[depth]=i; /* 更新栈顶指针，指向所找到的可行城市 */

stack[depth+1]=0;

visited[i]=1; /* 修改所找到的城市的访问标志 */

if(i==N-1) /* i==N-1表示访问到了乙城市，完成了所有城市

的一次搜索，找到一条通路 */

{

// printf("heren");

for(j=0;j<=depth;j++) /* 保存当前找到的通路所经过的所有节点 */

bestPath[j]=stack[j];

bestLength=depth; /* 保存当前找到的通路所经过的所有节点的节

点数 */

shortestDist=currentDist; /* 保存当前找到的通路的距离之和 */

minimumCost=currentCost; /* 保存当前找到的通路的代价之和 */

//costBound=currentCost;

distBound=currentDist; /* 更新剪枝的路径边界，如果以后所找到的通路

路径之和大于目前通路的路径之和，就剪枝 */

if(minimumCost>1500) continue; /* 如果当前找到的通路的代价之和大于1500，

则放弃这条通路 */

printf("最短路径:%3d,路径代价:%3d,所经历的节点数目:%3d,所经历的节点如

下:n",shortestDist,minimumCost,bestLength+1); /* 输出找到的通路的结果 */

bestPath[bestLength]=49;

for(i=0;i<=bestLength;i++) /* 输出所找到的通路所经过的具体的节点 */

printf("%3d ",bestPath[i]+1);

(完整word版)北航研究生算法设计与分析Assignment_2

printf("n");

depth--; /* 连续弹出栈顶的两个值，进行回溯，开始寻找

新的可行的通路 */

currentDist-=m1[stack[depth]][stack[depth+1]];

currentCost-=m2[stack[depth]][stack[depth+1]];

visited[stack[depth+1]]=0;

depth--;

currentDist-=m1[stack[depth]][stack[depth+1]];

currentCost-=m2[stack[depth]][stack[depth+1]];

visited[stack[depth+1]]=0;

// getchar();

}

}

}

}