實(shí)驗(yàn)二 電路布線問題

1、實(shí)驗(yàn)二 電路布線問題班級：計(jì)算機(jī)1405 組別：4 姓名：劉誠陽 學(xué)號：201437121. 問題定義及需求分析1.1課題目的和任務(wù)問題描述：印刷電路板將布線區(qū)域劃分為nn個方格陣列。在布線時，電路只能沿直線或直角布線。為避免線路相交，已布線的方格要做封鎖標(biāo)記。設(shè)起始位置為a，終止位置為b，求解電路布線問題。實(shí)驗(yàn)要求：設(shè)計(jì)印刷電路板的布線模擬程序。1)采用?；蜿?duì)列等數(shù)據(jù)結(jié)構(gòu)。2)采用窮舉法的回溯搜索，求a到b可能的布線線路。3)推薦采用層次優(yōu)先搜索，求a到b最優(yōu)的布線線路。1.2數(shù)據(jù)形式輸入數(shù)據(jù)形式：通過生成隨機(jī)數(shù)的函數(shù)隨機(jī)生成一個矩陣。輸入值的范圍：生成的矩陣中的數(shù)值為int型，為0或者1，

2、其中0表示死路，1表示通路。 輸出數(shù)據(jù)形式：輸出到顯示器。1.3程序功能隨機(jī)給定一個線路分布矩陣，利用窮舉法，通過棧的應(yīng)用，求出從a到b的可能布線線路；采用層次優(yōu)先搜索，通過隊(duì)列的應(yīng)用，求出a到b的最優(yōu)布線線路。1.4測試數(shù)據(jù)測試數(shù)據(jù)為隨機(jī)生成的矩陣。2. 概要設(shè)計(jì)2.1抽象數(shù)據(jù)類型需要定義一個位置類型的數(shù)據(jù)，里面包含int型的x和y坐標(biāo)，用來記錄位置信息；再定義一個SWire的通道塊數(shù)據(jù)類型，里面包含該通道塊的位置數(shù)據(jù)，在路徑上的序號和方向信息；另外還需要構(gòu)建棧和隊(duì)列的基本結(jié)構(gòu)類型。2.2主程序流程及各模塊之間的調(diào)用關(guān)系3. 詳細(xì)設(shè)計(jì)3.1存儲結(jié)構(gòu)實(shí)現(xiàn)typedef struct/位置 in

3、t x; int y;Position;typedef struct/移動標(biāo)記 int ord; Position seat; int di;SWire;typedef struct/棧 SWire* base; SWire* top; int stacksize;Stack;typedef struct QNode/隊(duì)列 Position data; struct QNode* next;QNode,*QP;typedef struct QP fron; QP rear;LinkQ;3.2負(fù)責(zé)模塊的偽碼算法（1）int WirePath(int* Board,Position start,P

4、osition finish)/尋找路徑算法/若有從電路板的入口start到出口end的通道，則求得一條存放在棧中/（從棧底到棧頂） InitStack(S); curpos=start;/設(shè)定當(dāng)前位置為入口位置 curstep=1;/探索第一步 do if(Pass(S,curpos)/當(dāng)前位置可通過，即是未曾走到的通道塊 FootPrint(curpos);/留下足跡 e=(curstep,curpos,1); Push(S,e);/加入路徑 if(curpos=finish)/到達(dá)出口（終點(diǎn)） PrintStack(S);/輸出路徑 Printf(電路板的搜尋圖) return 1;/返

5、回 NextPos(curpos,1);/下一位置是當(dāng)前位置的東鄰 curstep+;/探索下一步 else/當(dāng)前位置不能通過 Pop(S,e); if(S.top!=S.base)/棧空 while(e.di=5&&S.top!=S.base) MarkPrint(e.seat); Pop(S,e);/留下不能通過的標(biāo)記，并退回一步 if(e.di<5) e.di+; Push(S,e); /換下一個方向探索 NextPos(e.seat,e.di);/設(shè)定當(dāng)前位置是該新方向/上的相鄰塊 curpos.x=e.seat.x; curpos.y=e.seat.y; whi

6、le(S.base!=S.top);printf(沒有通路);printf(電路板的搜尋圖); return 0;（2）int FindShortWay(int* Board,Position start,Position finish)/搜尋最短布線路徑算法 if(finish=start)/到達(dá)終點(diǎn)，結(jié)束 MShortPath=0; return 1; curpos=start;/標(biāo)記當(dāng)前位置 if(Boardstart.xstart.y=0)沒有通路!return 0; Boardstart.xstart.y=2;/有通路，則令其值為2while(1)/將第一個通道塊賦值2，并將其相鄰?fù)?/p>

7、道塊從右開始，按順時/針依次入隊(duì)列，當(dāng)隊(duì)列不空時，出隊(duì)列一個通道塊，對其相鄰?fù)ǖ缐K做相/同操作，直至所有的未標(biāo)記通路通道塊都被標(biāo)記后為止。 for(i=1;i<5;i+)/對其相鄰?fù)ǖ缐K賦值 neighbour=curpos; NextPos(neighbour,i); if(Boardneighbour.xneighbour.y=1|Boardneighbour.xneighbour.y=-1|Boardneighbour.xneighbour.y=-3)/該通道塊可通過且未標(biāo)記 Boardneighbour.xneighbour.y=Boardcurpos.xcurpos.y+1;/

8、值+1 if(neighbour=finish)break;/到達(dá)終點(diǎn)，結(jié)束 EnQ(Q,neighbour);/將該通道塊入隊(duì)列 /if /for if(neighbour=finish)break;/已全部標(biāo)記，結(jié)束循環(huán) if(Q.fron=Q.rear)return 0;/沒有通路，結(jié)束 DeQ(Q,curpos);/出隊(duì)列 /while /反向搜尋最短布線路徑 MShortPath=Boardneighbour.xneighbour.y-2; pathMShortPath=(0,0);curpos=finish;/標(biāo)記當(dāng)前位置為結(jié)束位置 for(j=MShortPath-1;j>

9、=0;j-)/反向搜索最短路徑 pathj=curpos; for(i=0;i<5;i+)/在相鄰?fù)ǖ缐K中找符合的標(biāo)記值 neighbour=curpos; NextPos(neighbour,i); if(Boardneighbour.xneighbour.y=j+2)break; curpos=neighbor;/當(dāng)前位置為相鄰?fù)ǖ缐K printf(輸出最短布線路徑); printf(輸出最短路徑搜尋矩陣); return 1;4. 調(diào)試分析4.1問題分析與解決方法(1)尋找可能路徑若當(dāng)前位置可通過，則納入當(dāng)前路徑，并繼續(xù)朝著下一位置探索，即切換下一位置為當(dāng)前位置，如此重復(fù)直至到達(dá)出

10、口；若當(dāng)前位置不可通，則應(yīng)順著來向退回到前一通道塊，然后朝著除來向之外的其他方向繼續(xù)探索；若該通道塊的四周4個方塊均不可通，則應(yīng)從當(dāng)前路徑上刪除該通道塊。所謂下一位置指的是當(dāng)前位置四周4個方向（東南西北）上相鄰的方塊。假設(shè)以棧S記錄當(dāng)前路徑，則棧頂中存放的是當(dāng)前路徑上的最后一個通道塊。由此，納入路徑的操作即為當(dāng)前位置入棧；從當(dāng)前路徑上刪除前一通道塊的操作即為出棧。通過入棧和出棧操作，使得當(dāng)前位置找尋到出口位置，從而實(shí)現(xiàn)對迷宮一個可能路徑的求解。(2)尋找最優(yōu)路徑 標(biāo)記當(dāng)前位置，通過隊(duì)列，將當(dāng)前位置周圍的四個通道塊入隊(duì)列，將當(dāng)前位置標(biāo)記值m后，出隊(duì)列，對該通道塊執(zhí)行相同的操作，并標(biāo)記值m+，通過

11、循環(huán)操作，直到當(dāng)前位置為出口時終止。借助隊(duì)列，通過循環(huán)操作，使每個通道塊都被賦值。然后標(biāo)記當(dāng)前位置為出口，從出口向入口尋找符合遞減值的通道塊，從而確定出最短路徑。4.2算法的時空分析（1）尋找可能路徑時間復(fù)雜度：空間復(fù)雜度：（2）尋找最優(yōu)路徑時間復(fù)雜度：空間復(fù)雜度：4.3算法的改進(jìn)設(shè)想通過對搜尋可能路徑的算法改進(jìn)，實(shí)現(xiàn)能夠同時輸出多條可能路徑的功能。而最優(yōu)路徑也有可能有多條，因此可以改進(jìn)搜索最優(yōu)路徑的算法，使其能夠輸出全部的最優(yōu)路徑。可以考慮加入多重標(biāo)記的方法實(shí)現(xiàn)。4.4經(jīng)驗(yàn)和體會 電路板布線問題實(shí)際上就是迷宮求解問題，電路板上的布線要求可以轉(zhuǎn)化成迷宮的通路和不通路的問題，當(dāng)電線可以經(jīng)過該點(diǎn)時

12、，該點(diǎn)即為通路，而當(dāng)電線不能經(jīng)過該點(diǎn)時，它即為死路，利用1,0分別表示通路和死路，就可以建立類似迷宮求解的模型，通過棧和隊(duì)列的一系列數(shù)據(jù)結(jié)構(gòu)的輔助，來求解迷宮問題。5. 使用說明運(yùn)行程序，系統(tǒng)會自動給出一個隨機(jī)電路板矩陣，自動輸出一個可能的布線路徑和最優(yōu)布線路徑，并給出搜尋路徑的標(biāo)記圖；若該電路板不存在可行路徑，則會提示沒有通路。6. 測試結(jié)果（截屏）（1）隨機(jī)生成的電路板矩陣：（2）可能布線路徑：（3）最短布線路徑：7. 附錄7.1個人負(fù)責(zé)模塊的程序代碼int WirePath(int* Board,Position start,Position finish)/尋找路徑算法 int i,j

13、; Stack S; SWire e; Position curpos; int curstep; InitStack(S);/設(shè)定當(dāng)前位置為入口位置 curpos.x=start.x; curpos.y=start.y; curstep=1;/探索第一步 do if(Pass(S,curpos)/當(dāng)前位置可通過，即未走過 FootPrint(curpos);/留下足跡 e.ord=curstep; e.seat.x=curpos.x; e.seat.y=curpos.y; e.di=1; Push(S,e);/加入路徑 if(curpos.x=finish.x&&curpos

14、.y=finish.y)/到達(dá)終點(diǎn) PrintStack(S); printf("n搜尋路徑圖(-3表示布線，-1表示死路）：n"); for(i=0;i<n;i+) for(j=0;j<n;j+) printf("%dt",Boardij); printf("n"); return 1; NextPos(curpos,1);/下一個位置是當(dāng)前位置的東鄰 curstep+;/探索下一步 else/當(dāng)前位置不能通過 Pop(S,e); if(S.top!=S.base) while(e.di=5&&S.top

15、!=S.base) MarkPrint(e.seat);/留下不能通過標(biāo)記 Pop(S,e);/退一步 if(e.di<5) e.di+; Push(S,e);/換下一個方向探索 NextPos(e.seat,e.di);/設(shè)定當(dāng)前位置是該新方向上的相鄰塊 curpos.x=e.seat.x; curpos.y=e.seat.y; while(S.base!=S.top); printf("沒有通路!nn搜尋路徑圖(-3表示布線，-1表示死路）：n"); for(i=0;i<n;i+) for(j=0;j<n;j+) printf("%dt&qu

16、ot;,Boardij); printf("n"); return 0;int FindShortWay(int* Board,Position start,Position finish)/搜尋最短布線路徑算法 if(finish.x=start.x&&finish.y=start.y)/起點(diǎn)為終點(diǎn)，結(jié)束 MShortPath=0; return 1; LinkQ Q; InitQ(Q); int i; Position curpos,neighbour; curpos.x=start.x;curpos.y=start.y;/設(shè)定起始位置為當(dāng)前位置 if(

17、Boardstart.xstart.y=0)printf("沒有通路!n");return 0; Boardstart.xstart.y=2;while(1)/利用隊(duì)列，將每個通道塊都做上標(biāo)記，起點(diǎn)標(biāo)記為2，其余按到達(dá)步數(shù)依次累加 for(i=1;i<5;i+) neighbour.x=curpos.x; neighbour.y=curpos.y; NextPos(neighbour,i); if(Boardneighbour.xneighbour.y=1|Boardneighbour.xneighbour.y=-1|Boardneighbour.xneighbour

18、.y=-3)/當(dāng)前通道塊可探索 Boardneighbour.xneighbour.y=Boardcurpos.xcurpos.y+1;/標(biāo)記 if(neighbour.x=finish.x&&neighbour.y=finish.y)break;/如果鄰接通道塊為終點(diǎn)，則結(jié)束循環(huán) EnQ(Q,neighbour);/該通道塊入隊(duì)列 /if /for if(neighbour.x=finish.x&&neighbour.y=finish.y)break; if(Q.fron=Q.rear)printf("沒有通路!n");return 0;/

19、所有通道塊均被標(biāo)記，結(jié)束 DeQ(Q,curpos);/出隊(duì)列 /while /反向搜尋最短布線路徑 MShortPath=Boardneighbour.xneighbour.y-2; Position pathMShortPath+1; pathMShortPath.x=0; pathMShortPath.y=0; curpos.x=finish.x; curpos.y=finish.y; int j; for(j=MShortPath-1;j>=0;j-)/反向搜尋符合值 pathj=curpos; for(i=0;i<5;i+) neighbour.x=curpos.x; n

20、eighbour.y=curpos.y; NextPos(neighbour,i); if(Boardneighbour.xneighbour.y=j+2)break;/符合即結(jié)束記錄 curpos.x=neighbour.x; curpos.y=neighbour.y; /輸出最短布線路徑 printf("(1,1)->"); for(i=0;pathi.x!=0&&pathi.y!=0;i+) printf("(%d,%d)",pathi.x,pathi.y); if(pathi.x!=8|pathi.y!=8)printf(&

21、quot;->"); printf("n"); /輸出最短路徑搜尋矩陣 printf("n搜尋路徑圖：n"); for(i=0;i<n;i+) for(j=0;j<n;j+) printf("%dt",Boardij); printf("n"); return 1;7.2程序全部代碼#include<stdio.h>#include<iostream>using namespace std;#include<stdlib.h>#include<t

22、ime.h>#define SIZE 100#define INCH 10typedef struct/位置 int x; int y;Position;typedef struct/移動標(biāo)記 int ord; Position seat; int di;SWire;typedef struct/棧 SWire* base; SWire* top; int stacksize;Stack;typedef struct QNode/隊(duì)列 Position data; struct QNode* next;QNode,*QP;typedef struct QP fron; QP rear;L

23、inkQ;int* Board;/電路板int MShortPath;/最短路徑const int n=10;/電路板大小int CreateBoard()/創(chuàng)建一個電路板 int i,j; Board=(int*)malloc(sizeof(int*)*(n); for(i=0;i<n;i+) Boardi=(int*)malloc(sizeof(int)*(n); i=0; srand(time(NULL); for(i=0;i<n;i+) for(j=0;j<n;j+) if(i=0|i=n-1|j=0|j=n-1) Boardij=0; else Boardij=1;

24、 if(rand()%2=0) if(rand()%2=0) Boardij=0; printf("隨機(jī)生成的10X10電路板的分布情況為（1可通，0不可通）:n"); for(i=0;i<n;i+) for(j=0;j<n;j+) printf("%dt",Boardij); printf("n"); return 1;int DestroyBoard()/摧毀電路板 free(Board); return 0;int InitStack(Stack &S)/創(chuàng)建空棧 S.base=(SWire*)malloc(

25、SIZE*sizeof(SWire); if(!S.base)return(0); S.top=S.base; S.stacksize=SIZE; return 1;int Pass(Stack& S,Position f)/電線通過判定 if(Boardf.xf.y=0|Boardf.xf.y=-3|Boardf.xf.y=-1)return 0; return 1;int FootPrint(Position f)/布線 Boardf.xf.y=-3; return 1;int Push(Stack &S,SWire e)/入棧 if(S.top-S.base>=S.

26、stacksize) S.base=(SWire*)realloc(S.base,(S.stacksize+INCH)*sizeof(SWire); if(!S.base)return(0); S.top=S.base+S.stacksize; S.stacksize+=INCH; *S.top=e; S.top+; return 1;int Pop(Stack &S,SWire &e)/出棧 if(S.base=S.top)return(0); e=*(-S.top); return 1;int NextPos(Position& f,int i)/1=EAST,2=

27、SOURTH,3=WEST,4=NORTH/嘗試相鄰位置 if(i=1)f.y+; if(i=2)f.x+; if(i=3)f.y-; if(i=4)f.x-; return 1;int MarkPrint(Position f)/留下不可布線的標(biāo)志 Boardf.xf.y=-1; return 1;int PrintStack(Stack& S)/輸出棧內(nèi)存儲的布線路徑 do printf("(%d,%d)",S.base->seat.x,S.base->seat.y); if(S.base->seat.x=8&&S.base-&

28、gt;seat.y=8) else printf("->"); S.base+; while(S.top!=S.base); printf("n"); return 1;int WirePath(int* Board,Position start,Position finish)/尋找路徑算法 int i,j; Stack S; SWire e; Position curpos; int curstep; InitStack(S); curpos.x=start.x; curpos.y=start.y; curstep=1; do if(Pass(

29、S,curpos) FootPrint(curpos); e.ord=curstep; e.seat.x=curpos.x; e.seat.y=curpos.y; e.di=1; Push(S,e); if(curpos.x=finish.x&&curpos.y=finish.y) PrintStack(S); printf("n搜尋路徑圖(-3表示布線，-1表示死路）：n"); for(i=0;i<n;i+) for(j=0;j<n;j+) printf("%dt",Boardij); printf("n"

30、;); return 1; NextPos(curpos,1); curstep+; else Pop(S,e); if(S.top!=S.base) while(e.di=5&&S.top!=S.base) MarkPrint(e.seat); Pop(S,e); if(e.di<5) e.di+; Push(S,e); NextPos(e.seat,e.di); curpos.x=e.seat.x; curpos.y=e.seat.y; while(S.base!=S.top); printf("沒有通路!nn搜尋路徑圖(-3表示布線，-1表示死路）：n&q

31、uot;); for(i=0;i<n;i+) for(j=0;j<n;j+) printf("%dt",Boardij); printf("n"); return 0;/隊(duì)列int InitQ(LinkQ& Q)/創(chuàng)建空隊(duì)列 Q.fron=Q.rear=(QP)malloc(sizeof(QNode); if(!Q.fron)return 0; Q.fron->next=NULL; return 1;int DestroyQ(LinkQ& Q)/摧毀隊(duì)列 while(Q.fron) Q.rear=Q.fron->n

32、ext; free(Q.fron); Q.fron=Q.rear; return 1;int EnQ(LinkQ& Q,Position e)/入隊(duì)列 QP p; p=(QP)malloc(sizeof(QNode); if(!p)return 0; p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return 1;int DeQ(LinkQ& Q,Position& e)/出隊(duì)列 if(Q.fron=Q.rear)return 0; QP p; p=Q.fron->next; e=p->

33、;data; Q.fron->next=p->next; if(Q.rear=p)Q.rear=Q.fron; free(p); return 1;int FindShortWay(int* Board,Position start,Position finish)/搜尋最短布線路徑算法 if(finish.x=start.x&&finish.y=start.y) MShortPath=0; return 1; LinkQ Q; InitQ(Q); int i; Position curpos,neighbour; curpos.x=start.x;curpos.y

34、=start.y; if(Boardstart.xstart.y=0)printf("沒有通路!n");return 0; Boardstart.xstart.y=2; while(1) for(i=1;i<5;i+) neighbour.x=curpos.x; neighbour.y=curpos.y; NextPos(neighbour,i); if(Boardneighbour.xneighbour.y=1|Boardneighbour.xneighbour.y=-1|Boardneighbour.xneighbour.y=-3) Boardneighbour.xneighbour.y=Boardcurpos.xcurpos.y+1; if(neighbour.x=finish.x&&neighbour.y=fini