1、實驗六 用分支限界法求解最短布線問題學院： 計算機科學與技術 專業：計算機科學與技術學號： 班級： 姓名： （本程序在的環境下實現）一、實驗內容：布線問題：印刷電路板將布線區域劃分成n×m個方格陣列，要求確定連接方格陣列中的方格a的中點到方格b的中點的最短布線方案。在布線時，電路只能沿直線或直角布線，為了避免線路相交，已布了線的方格做了封鎖標記，其他線路不允許穿過被封鎖的方格。實驗要求：用分支限界法解此最短布線問題。分支限界法類似回溯法，也是一種在問題的解空間樹T上搜索問題解的算法。但分支限界法只找出滿足約束條件的一個最優解，并且以廣度優先或最小耗費優先的方式搜索解空間樹T。樹T是一

2、棵子集樹或排列樹。在搜索時，每個結點只有一次機會成為擴展結點，并且一次性產生其所有兒子結點。從活結點表中選擇下一擴展結點有兩種方式：（1）隊列式（FIFO） （2）優先隊列式。分支限界法可廣泛應用于單源最短路徑問題，最大團問題，布線問題，電路板排列問題等。舉例說明：一個7×7方格陣列布線如下：起始位置是a = (3,2)，目標位置是b = (4,6)，陰影方格表示被封鎖的方格。那么一條從a到b的最短布線方案如下圖紅色路徑所示。a到b的最短距離是9。請思考：如何使得構造出的最短布線中的折角數量最少？ a b 最短布線路徑示例二、算法思想： 首先從點a出發向上下左右四個方向查找到點b的路

3、徑，并且每走一步便做增一標記，到達b點后，將路徑長度賦給一個變量，依次遞減路徑長度，由b點往回查找得到路徑。三、實驗過程：#include<iostream>#include<iomanip>using namespace std;struct Positionint row;int col;struct TEAMint x;int y;TEAM *next;Position start,end,path100;TEAM *team_l=NULL;int a100100;int m,n,path_len;void Output()int i,j;cout<<

4、"n-布線區域圖-n"for(i=0;i<m+2;i+)for(j=0;j<n+2;j+)cout<<setw(2)<<aij;cout<<endl;cout<<"-n"return;void Input_data()char yes;int x,y;cout<<"請輸入區域大小(行列的個數): "cin>>m>>n;cout<<"請輸入開始點坐標(x,y): "cin>>start.row>

5、;>start.col;cout<<"請輸入結束點坐標(x,y): "cin>>end.row>>end.col;cout<<"區域內是否有被占用點? (y/n) "cin>>yes;while(yes='y')cout<<"請輸入占用點的坐標(x,y): "cin>>x>>y;if(x<0 | x>m+1 | y<0 | y>n+1 | (x=start.row && y=st

6、art.col) | (x=end.row && y=end.col) cout<<"輸入錯誤,請重新輸入!n"continue;elseaxy=-1;cout<<"是否還有被占用點? (y/n) "cin>>yes;for(x=0;x<m+2;x+)a0x=-1;am+1x=-1;for(x=0;x<n+2;x+)ax0=-1;axn+1=-1;return;void Inq(Position p)TEAM *t,*q;q=team_l;t=new TEAM;t->x=p.row;t

7、->y=p.col;t->next=NULL;if(team_l=NULL)team_l=t;return ;while(q->next!=NULL)q=q->next;q->next=t;return;Position outq()Position out;out.row=team_l->x;out.col=team_l->y;team_l=team_l->next;return out;void Find_path()Position offset4;Position here=start.row,start.col;Position nbr

8、=0,0;int num_of_nbrs=4;int i,j;offset0.row=0;offset0.col=1; /右offset1.row=1;offset1.col=0; /下offset2.row=0;offset2.col=-1;/左offset3.row=-1;offset3.col=0;/上if(start.row = end.row)&&(start.col = end.col)path_len = 0;return;while(1)for(i=0;i<num_of_nbrs;i+)nbr.row=here.row+offseti.row;nbr.co

9、l=here.col+offseti.col;if(anbr.rownbr.col=0)anbr.rownbr.col=ahere.rowhere.col + 1;if(nbr.row = end.row) && (nbr.col = end.col)break;Inq(nbr); /nbr入隊if(nbr.row = end.row) && (nbr.col = end.col)/是否到達目標位置finishbreak;if(team_l=NULL)/或節點隊列是否為空 cout<<"n沒有結果!n"return ;here=o

10、utq();path_len=aend.rowend.col;here=end;for(j=path_len-1;j>=0;j-)/往回找路徑pathj = here;for(i = 0;i < num_of_nbrs;i+)nbr.row = here.row + offseti.row;nbr.col = here.col + offseti.col;if(anbr.rownbr.col = j) break;here=nbr;return;void Out_path()int i;cout<<"n路徑為:"cout<<"("<<start.row<<","<<start.col<<")"for(i=0;i<path_len;i+)cout<<"("<<pathi.row<<","<<pathi.col<&l