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

1、傳播優(yōu)秀Word版文檔 ，希望對(duì)您有幫助，可雙擊去除！實(shí)驗(yàn)二 電路布線問(wèn)題1. 問(wèn)題定義及需求分析1.1課題目的和任務(wù)問(wèn)題描述：印刷電路板將布線區(qū)域劃分為nn個(gè)方格陣列。在布線時(shí)，電路只能沿直線或直角布線。為避免線路相交，已布線的方格要做封鎖標(biāo)記。設(shè)起始位置為a，終止位置為b，求解電路布線問(wèn)題。實(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ù)形式：通過(guò)生成隨機(jī)數(shù)的函數(shù)隨機(jī)生成一個(gè)矩陣。輸入值的范圍：生成的矩陣中的數(shù)值為int型，為0或者1，其中0表示死路

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

3、t y;Position;typedef struct/移動(dòng)標(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,Position

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

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

6、intf(沒(méi)有通路);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)沒(méi)有通路!return 0; Boardstart.xstart.y=2;/有通路，則令其值為2while(1)/將第一個(gè)通道塊賦值2，并將其相鄰?fù)ǖ缐K從右開始，按順時(shí)/針依次入隊(duì)列，當(dāng)隊(duì)

7、列不空時(shí)，出隊(duì)列一個(gè)通道塊，對(duì)其相鄰?fù)ǖ缐K做相/同操作，直至所有的未標(biāo)記通路通道塊都被標(biāo)記后為止。 for(i=1;i=0;j-)/反向搜索最短路徑 pathj=curpos; for(i=0;i5;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問(wèn)題分析與解決方法(1)尋找

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

9、，將當(dāng)前位置周圍的四個(gè)通道塊入隊(duì)列，將當(dāng)前位置標(biāo)記值m后，出隊(duì)列，對(duì)該通道塊執(zhí)行相同的操作，并標(biāo)記值m+，通過(guò)循環(huán)操作，直到當(dāng)前位置為出口時(shí)終止。借助隊(duì)列，通過(guò)循環(huán)操作，使每個(gè)通道塊都被賦值。然后標(biāo)記當(dāng)前位置為出口，從出口向入口尋找符合遞減值的通道塊，從而確定出最短路徑。4.2算法的時(shí)空分析（1）尋找可能路徑時(shí)間復(fù)雜度：空間復(fù)雜度：（2）尋找最優(yōu)路徑時(shí)間復(fù)雜度：空間復(fù)雜度：4.3算法的改進(jìn)設(shè)想通過(guò)對(duì)搜尋可能路徑的算法改進(jìn)，實(shí)現(xiàn)能夠同時(shí)輸出多條可能路徑的功能。而最優(yōu)路徑也有可能有多條，因此可以改進(jìn)搜索最優(yōu)路徑的算法，使其能夠輸出全部的最優(yōu)路徑?？梢钥紤]加入多重標(biāo)記的方法實(shí)現(xiàn)。4.4經(jīng)驗(yàn)和體會(huì) 電

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

11、t* Board,Position start,Position finish)/尋找路徑算法 int i,j; 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)前位置可通過(guò)，即未走過(guò) FootPrint(curpos);/留下足跡 e.ord=curstep; e.seat.x=curpos.x; e.seat.y=curpos.y; e.di=

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

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

14、hortWay(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(Boardstart.xstart.y=0)printf(沒(méi)有通路!n);return 0; Boardstart.xstart

15、.y=2;while(1)/利用隊(duì)列，將每個(gè)通道塊都做上標(biāo)記，起點(diǎn)標(biāo)記為2，其余按到達(dá)步數(shù)依次累加 for(i=1;i=0;j-)/反向搜尋符合值 pathj=curpos; for(i=0;i); 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(-); printf(n); /輸出最短路徑搜尋矩陣 printf(n搜尋路徑圖：n); for(i=0;in;i+) for(j=0;jn;j+) printf(%dt,Boardij); printf

16、(n); return 1;7.2程序全部代碼#include#includeusing namespace std;#include#include#define SIZE 100#define INCH 10typedef struct/位置 int x; int y;Position;typedef struct/移動(dòng)標(biāo)記 int ord; Position seat; int di;SWire;typedef struct/棧 SWire* base; SWire* top; int stacksize;Stack;typedef struct QNode/隊(duì)列 Position da

17、ta; struct QNode* next;QNode,*QP;typedef struct QP fron; QP rear;LinkQ;int* Board;/電路板int MShortPath;/最短路徑const int n=10;/電路板大小int CreateBoard()/創(chuàng)建一個(gè)電路板 int i,j; Board=(int*)malloc(sizeof(int*)*(n); for(i=0;in;i+) Boardi=(int*)malloc(sizeof(int)*(n); i=0; srand(time(NULL); for(i=0;in;i+) for(j=0;jn;

18、j+) if(i=0|i=n-1|j=0|j=n-1) Boardij=0; else Boardij=1; if(rand()%2=0) if(rand()%2=0) Boardij=0; printf(隨機(jī)生成的10X10電路板的分布情況為（1可通，0不可通）:n); for(i=0;in;i+) for(j=0;j=S.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+=

19、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=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

20、 1;int PrintStack(Stack& S)/輸出棧內(nèi)存儲(chǔ)的布線路徑 do printf(%d,%d),S.base-seat.x,S.base-seat.y); if(S.base-seat.x=8&S.base-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

21、 curstep; InitStack(S); curpos.x=start.x; curpos.y=start.y; curstep=1; do if(Pass(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;in;i+) for(j=0;jn;j+)

22、 printf(%dt,Boardij); printf(n); 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.di5) 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(沒(méi)有通路!nn搜尋路徑圖(-3表示布線，-

23、1表示死路）：n); for(i=0;in;i+) for(j=0;jnext=NULL; return 1;int DestroyQ(LinkQ& Q)/摧毀隊(duì)列 while(Q.fron) Q.rear=Q.fron-next; 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-data; Q.fron-next=p-next; if(Q.rear=p)Q.rear=Q.fron; free(