北航研究生 算法设计与分析 Assignment_2.doc

用分支定界算法求以下问题：某公司于乙城市的销售点急需一批成品，该公司成品生产基地在甲城市。甲城市与乙城市之间共有 n 座城市，互相以公路连通。甲城市、乙城市以及其它各城市之间的公路连通情况及每段公路的长度由矩阵M1 给出。每段公路均由地方政府收取不同额度的养路费等费用，具体数额由矩阵M2 给出。请给出在需付养路费总额不超过 1500 的情况下，该公司货车运送其产品从甲城市到乙城市的最短运送路线。具体数据参见文件：m1.txt: 各城市之间的公路连通情况及每段公路的长度矩阵(有向图); 甲城市为城市Num.1，乙城市为城市Num.50。m2.txt: 每段公路收取的费用矩阵（非对称）。思想：利用Floyd算法的基本方法求解。程序实现流程说明：1.将m1.txt和m2.txt的数据读入两个5050的数组。2.用Floyd算法求出所有点对之间的最短路径长度和最小费用。3.建立一个堆栈，初始化该堆栈。4.取出栈顶的结点，检查它的相邻的所有结点，确定下一个当前最优路径上的结点，被扩展的结点依次加入堆栈中。在检查的过程中，如果发现超出最短路径长度或者最小费用，则进行”剪枝”，然后回溯。5.找到一个解后，保存改解，然后重复步骤4。6.重复步骤4、5，直到堆栈为空，当前保存的解即为最优解。 时间复杂度分析：Floyd算法的时间复杂度为，N为所有城市的个数。该算法的时间复杂度等于DFS的时间复杂度，即O(N+E)。其中，E为所有城市构成的有向连通图的边的总数。但是因为采用了剪枝，会使实际运行情况的比较次数远小于E。求解结果：算法所得结果:甲乙之间最短路线长度是:464最短路线收取的费用是:1448最短路径是:1 3 8 11 15 21 23 26 32 37 39 45 47 50C源代码（注意把m1.txt与m2.txt放到与源代码相同的目录下， 下面代码可直接复制运行）：#include#include#include#include#define N 50#define MAX 52void input(int aNN,int bNN);void Floyd(int dNN);void fenzhi(int m1NN,int m2NN,int mindistNN,int mincostNN); int visitedN,bestPathN;void main()clock_t start,finish;double duration;int i,j,mindistNN,mincostNN,m1NN,m2NN; /* m1NN和m2NN分别代表题目所给的距离矩阵和代价矩阵 */ / int visitedN,bestPathN;FILE *fp,*fw;/ system(cls);time_t ttime; time(&ttime);printf(%s,ctime(&ttime);start=clock();for(i=0;iN;i+)visitedi=0;bestPathi=0;fp=fopen(m1.txt,r); /* 把文件中的距离矩阵m1读入数组mindistNN */if(fp=NULL)printf(can not open filen);return;for(i=0;iN;i+)for(j=0;jN;j+)fscanf(fp,%d,&mindistij);fclose(fp); /* 距离矩阵m1读入完毕 */fp=fopen(m2.txt,r); /* 把文件中的代价矩阵m2读入数组mincostNN */if(fp=NULL)printf(can not open filen);return;for(i=0;iN;i+)for(j=0;jN;j+)fscanf(fp,%d,&mincostij);fclose(fp); /* 代价矩阵m2读入完毕 */input(m1,mindist); /* mindistNN赋值给m1NN，m1NN代表题目中的距离矩阵 */input(m2,mincost); /* mincostNN赋值给m2NN，m2NN代表题目中的代价矩阵 */for(i=0;iN;i+) /* 把矩阵mindistii和mincostii的对角元素分别初始化，表明城市到自身不连通，代价为0 */mindistii=9999;mincostii=0;Floyd(mindist); /* 用弗洛伊德算法求任意两城市之间的最短距离，结果存储在数组mindistNN中 */*fw=fopen(1.txt,w);for(i=0;iN;i+)for(j=0;jN;j+)fprintf(fw,%4d ,mindistij);fprintf(fw,n);fclose(fw); / getchar();/*/Floyd(mincost); /* 用弗洛伊德算法求任意两城市之间的最小代价，结果存储在数组mincostNN中 */*fw=fopen(2.txt,w);for(i=0;iN;i+)for(j=0;jN;j+)fprintf(fw,%4d ,mincostij);fprintf(fw,n);fclose(fw); / getchar();/*/fenzhi(m1,m2,mindist,mincost); /* 调用分支定界的实现函数，寻找出所有的可行路径并依次输出 */ finish=clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf( %f secondsn, duration );/*/void Floyd(int dNN) /* 弗洛伊德算法的实现函数 */int v,w,u,i;for(u=0;uN;u+)for(v=0;vN;v+)for(w=0;wN;w+)if(dvu+duwdvw)/printf(v,w,u,dvu,duw,dvw %d %d %d %d %d %d,v+1,w+1,u+1,dvu,duw,dvw);getchar();dvw=dvu+duw;void input(int aNN,int bNN) /* 把矩阵b赋值给矩阵a */int i,j;for(i=0;iN;i+)for(j=0;j=0) /* 表示遍历开始和结束条件，开始时从甲城市出发，栈空，depth=0；结束时遍历完毕，所有节点均被出栈，故栈也为空，depth=0 */* 整个while（）循环体用来实现从当前的城市中寻找一个邻近的城市 */cur=stackdepth; /* 取栈顶节点赋值给cur，表示当前访问到第cur号城市 */next=stackdepth+1; /* next指向当前所处城市的上一个已经遍历的城市 */for(i=next+1;icostBound)|(currentDist+mindistcurN-1=distBound) /* 所试探的城市满足剪枝条件，进行剪枝 */printf(here1 %d %d %d %d %d %d %dn,cur,currentCost,mincostcur49,costBound,currentDist,mindistcur49,distBound); getchar();/printf(%d %d %d %d %d %d,cur,i,m1curi,currentCost,mincostcur49,costBound); getchar();continue;if(m1curi=9999) continue; /* 所试探的城市不连通 */if(visitedi=1) continue; /* 所试探的城市已被访问 */if(iN) break; /* 所试探的城市满足访问条件，找到新的可行城市，终止for循环 */if(i=N) /* 判断for循环是否是由于搜索完所有城市而终止的，如果是（i=N），进行回溯 */printf(here);getchar();depth-;currentDist-=m1stackdepthstackdepth+1;currentCost-=m2stackdepthstackdepth+1;visitedstackdepth+1=0;else /* i!=N,表示for循环的终止是由于寻找到了当前城市的一个可行的邻近城市 */printf(%d %d %d %d %d %dn,cur,i,m1stackdepthi,m2stackdepthi,currentCost,currentDist);/getchar();currentDist+=m1stackdepthi; /* 把从当前所处城市到所找到的可行城市的距离加入currentDist */currentCost+=m2stackdepthi; /* 把从当前所处城市到所找到的可行城市的代价加入currentCost */depth+; /* 所找到的可行城市进栈 */stackdepth=i; /* 更新栈顶指针，指向所找到的可行城市 */stackdepth+1=0;visitedi=1; /* 修改所找到的城市的访问标志 */if(i=N-1) /* i=N-1表示访问到了乙城市，完成了所有城市的一次搜索，找到一条通路 */printf(heren);for(j=0;j1500) continue; /* 如果当前找到的通路的代价之和大于1500，则放弃这条通路 */printf(最短路径:%3d,路径代价:%3d,所经历的节点数目:%3d,所经历的节点如下:n,shortestDist,minimumCost,bestLength+1); /* 输出找到的通路的结果 */bestPathbestLength=49;for(i=0;i=bestLength;i+) /* 输出所找到的通路所经过的具体的节点 */printf(%3d ,bestPathi+1);printf(n);depth-; /* 连续弹出栈顶的两个值，进行回溯，开始寻找新的可行的