實驗六用分支限界法求解最短布線問題學院：計算機科學與技術專業：計算機科學與技術學號：班級：姓名：(JME序在MicrosoftVisua1C++6.0蚊建建下齡W)一、實驗內容：布線問題：印刷電路板將布線區域劃分成nXm個方格陣列，要求確定連接方格陣列中的方格a的中點到方格b的中點的最短布線方案。在布線時，電路只能沿直線或直角布線，為了避免線路相交，己布了線的方格做了封鎖標記，其他線路不允許穿過被封鎖的方格。實驗要求：用分支限界法解此最短布線問題。分支限界法類似回溯法，也是一種在問題的解空間樹T上搜索問題解的算法。但分支限界法只找出滿足約束條件的一個最優解，并且以廣度優先或最小耗費優先的方式搜索解空間樹T。樹T是一棵子集樹或排列樹。在搜索時，每個結點只有一次機會成為擴展結點，并且一次性產生其所有兒子結點。從活結點表中選擇下一擴展結點有兩種方式：(1)隊列式(FIFO)(2)優先隊列式。分支限界法可廣泛應用于單源最短路徑問題，最大團問題，布線問題，電路板排列問題等。舉例說明：一個7X7方格陣列布線如下：起始位置是a=(3,2),目標位置是b=(4,6),陰影方格表示被封鎖的方格。那么一條從a到b的最短布線方案如下圖紅色路徑所示。a到b的最短距離是9。請思考：如何使得構造出的最短布線中的折角數量最少？最短布線路徑示例二、算法思想：首先從點a出發向上下左右四個方向查找到點b的路徑，并且每走一步便做增一標記,到達b點后，將路徑長度賦給一個變量，依次遞減路徑長度，由b點往回查找得到路徑。三、實驗過程：#iiiclude<iostieam>#iiiclude<iomanip>usingnamespacestd;stmctPosition{introw;intcol;};stmctTEAMintx;mty;TEAM*next;}；Positionstart,end.path[100];TEAM*team_l=NULL;inta[100][100];intm,n,path_len;voidOutputQ{mtij;cout?M\n布線區域圖\ir；fbi(i=0;i<m+2;i++)for(j=0j<n+2j++)(cout?setw(2)?a[i][j];}cout?endl;}cout?H\nH;retuin;}voidInput_data(){charyes;mtx,y;cout?"請輸入區域大小(行列的個數):二ciii?m?n;cout?"請輸入開始點坐標(x,y):”；ciii?start.iow?start.col;cout?M請輸入結束點坐標(x,y):”；ciii?end.row?end.col;cout?"區域內是否有被占用點？(y/n)”；cm?yes;while(yes=,y,)jcout?M請輸入占用點的坐標(x,y):”；cin?x?y；iRx<0||x>m+l||y<0||y>n+l||(x==start.row&&y=start.col)||(x==end.row&&y==end.col))coutvv”輸入錯誤，請重新輸入!!!\iT;contmue;)else(a[x][y]=-l;}cout?M是否還有被占用點？(y/n)cin?yes;}fbr(x=0;x<m+2;x++)a[0][x]=-l;a[m+l][x]=-l;}fbr(x=0;x<n+2;x++)fa[x][0]=-l;a[x][n+l]=-l;}retuin;}voidInq(Positionp){TEAM*t,*q;q=teanO；t=newTEAM;t->x=p.row;t->y=p.col;t->next=NULL;if(teamJ==NULL)team_l=t;return;}while(q->next!=NULL)q=q->next;}q->next=t;retuin;Positionoutq()Positionout;out.row=team_l?>x;out.col=team_l->y；teaml=teaml->next;returnout;}voidFmd_path(){Positionoffset[4];Positionhere=(stait.row,stan.col);Positionnbi-(0.0);intnumofnbrs=4;intij;offset[0].row=0;offset[0].col=1;〃右offsetf1].row=1;offset[1].col=0;〃下offset[2].row=0;offset[2].col=-l;//左offset[3].row=-1;offset[3].col=0;//上if((start.row==end.row)&&(start.col=end.col))patlijen=0;return;}wlule(l)fbr(i=0;i<num_ofLubrs;i-H-)(nbr.row—here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(a[nbLrow][nbr.col]==0)(a[nbr.row][nbr.col]=a[here.iow][here.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(teamJ=NULL)//或節點隊列是否為空cout?M\n沒有結果!!!";return;)here=outqQ;}path_len=a[end.row][end.col];here=end;for(j=path_len-lj>=0;j--)〃往回找路徑JIpath。]=here;fbr(i=0;ivnum_oflnbrs;i-H-)(nbr.row=here.row+offset[i].row;nbr.col=heie.col+offset[i].col;if(a[nbLiow][nbr.col]=j)break;)here=nbr;}retuin;}voidOut_path0{inti;cout?H\n路徑為:”;coutvv”("vvstart.rowvv-yvstart.colvv“)”；fdr(i=O;i<path_len;i++)jcout?,,(H?patli[i].row?,\li?path[i].col?H),r;}cout?endl;retuin;}voidmain(){Iiiput_data();OutputQ;Find_path();Out_path();OutputQ;)四、實驗結果:-?1：\算法分析與設計\06用分支限界法求解景短布線何袈\Debug\Cppl.exe7?93345455123123>260134y<>>>>>>>>>>>>>>>>>>>>>>>>>>::ynynynynynynynynynynynynyn/，，，，，，，，，，，w二點<x<y<x<y<x<y<xE<x<y<x<y<x<y<x<y<x<y<x<y<x<y<x<y<x<y"<x<x莊標？標？標？標？標？標？標？標？標？標？標？標？標？q虐占坐占占g坐占巫占璽占g坐占座占座占座占座占塑占座占g小坐坐用的用的用的用的用的用的用的用的用的用的用的用的K占g點有占苫占苫占苫占g占占苫占苫點占占苫占苫占苫占g占占苫占小墩葬否禺黑黑塞黑黑黑黑禺黑塞塞黑IX0^1一苫有占有占有占有占有占有占有占有占有占有占有占有占有AX-^^■入正入丕入正入不一^^入正入爪一入正入丕入迅入不一^^入^蕾富蕾富蕾富蕾蕾富蕾富蕾奇值請請區菖宙l^snlAF三-1-1-1-1-1-1-1-1-1-100-10000-1-100-1-1000-1-1RRRR-lRR-1-1000-1-100-1-10000-100-10000-10000-1-1-1-1-1-1-1-1-1-1布線區域圖路徑為"3,2〉〈4,2〉(5,2〉＜5,3〉＜5,4〉＜6,4〉＜6,5〉＜6,6〉＜5,6〉＜4,