(完整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();

}

}

}

}