實驗二 電路布線問題.doc

精品文檔實驗二 電路布線問題1. 問題定義及需求分析1.1課題目的和任務(wù)問題描述：印刷電路板將布線區(qū)域劃分為nn個方格陣列。在布線時，電路只能沿直線或直角布線。為避免線路相交，已布線的方格要做封鎖標記。設(shè)起始位置為a，終止位置為b，求解電路布線問題。實驗要求：設(shè)計印刷電路板的布線模擬程序。1)采用棧或隊列等數(shù)據(jù)結(jié)構(gòu)。2)采用窮舉法的回溯搜索，求a到b可能的布線線路。3)推薦采用層次優(yōu)先搜索，求a到b最優(yōu)的布線線路。1.2數(shù)據(jù)形式輸入數(shù)據(jù)形式：通過生成隨機數(shù)的函數(shù)隨機生成一個矩陣。輸入值的范圍：生成的矩陣中的數(shù)值為int型，為0或者1，其中0表示死路，1表示通路。 輸出數(shù)據(jù)形式：輸出到顯示器。1.3程序功能隨機給定一個線路分布矩陣，利用窮舉法，通過棧的應(yīng)用，求出從a到b的可能布線線路；采用層次優(yōu)先搜索，通過隊列的應(yīng)用，求出a到b的最優(yōu)布線線路。1.4測試數(shù)據(jù)測試數(shù)據(jù)為隨機生成的矩陣。2. 概要設(shè)計2.1抽象數(shù)據(jù)類型需要定義一個位置類型的數(shù)據(jù)，里面包含int型的x和y坐標，用來記錄位置信息；再定義一個SWire的通道塊數(shù)據(jù)類型，里面包含該通道塊的位置數(shù)據(jù)，在路徑上的序號和方向信息；另外還需要構(gòu)建棧和隊列的基本結(jié)構(gòu)類型。2.2主程序流程及各模塊之間的調(diào)用關(guān)系3. 詳細設(shè)計3.1存儲結(jié)構(gòu)實現(xiàn)typedef struct/位置 int x; int y;Position;typedef struct/移動標記 int ord; Position seat; int di;SWire;typedef struct/棧 SWire* base; SWire* top; int stacksize;Stack;typedef struct QNode/隊列 Position data; struct QNode* next;QNode,*QP;typedef struct QP fron; QP rear;LinkQ;3.2負責(zé)模塊的偽碼算法（1）int WirePath(int* Board,Position start,Position 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)/到達出口（終點） PrintStack(S);/輸出路徑 Printf(電路板的搜尋圖) 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!=S.base) MarkPrint(e.seat); Pop(S,e);/留下不能通過的標記，并退回一步 if(e.di5) 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(沒有通路);printf(電路板的搜尋圖); return 0;（2）int FindShortWay(int* Board,Position start,Position finish)/搜尋最短布線路徑算法 if(finish=start)/到達終點，結(jié)束 MShortPath=0; return 1; curpos=start;/標記當(dāng)前位置 if(Boardstart.xstart.y=0)沒有通路!return 0; Boardstart.xstart.y=2;/有通路，則令其值為2while(1)/將第一個通道塊賦值2，并將其相鄰?fù)ǖ缐K從右開始，按順時/針依次入隊列，當(dāng)隊列不空時，出隊列一個通道塊，對其相鄰?fù)ǖ缐K做相/同操作，直至所有的未標記通路通道塊都被標記后為止。 for(i=1;i=0;j-)/反向搜索最短路徑 pathj=curpos; for(i=0;i5;i+)/在相鄰?fù)ǖ缐K中找符合的標記值 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āng)前位置不可通，則應(yīng)順著來向退回到前一通道塊，然后朝著除來向之外的其他方向繼續(xù)探索；若該通道塊的四周4個方塊均不可通，則應(yīng)從當(dāng)前路徑上刪除該通道塊。所謂下一位置指的是當(dāng)前位置四周4個方向（東南西北）上相鄰的方塊。假設(shè)以棧S記錄當(dāng)前路徑，則棧頂中存放的是當(dāng)前路徑上的最后一個通道塊。由此，納入路徑的操作即為當(dāng)前位置入棧；從當(dāng)前路徑上刪除前一通道塊的操作即為出棧。通過入棧和出棧操作，使得當(dāng)前位置找尋到出口位置，從而實現(xiàn)對迷宮一個可能路徑的求解。(2)尋找最優(yōu)路徑 標記當(dāng)前位置，通過隊列，將當(dāng)前位置周圍的四個通道塊入隊列，將當(dāng)前位置標記值m后，出隊列，對該通道塊執(zhí)行相同的操作，并標記值m+，通過循環(huán)操作，直到當(dāng)前位置為出口時終止。借助隊列，通過循環(huán)操作，使每個通道塊都被賦值。然后標記當(dāng)前位置為出口，從出口向入口尋找符合遞減值的通道塊，從而確定出最短路徑。4.2算法的時空分析（1）尋找可能路徑時間復(fù)雜度：空間復(fù)雜度：（2）尋找最優(yōu)路徑時間復(fù)雜度：空間復(fù)雜度：4.3算法的改進設(shè)想通過對搜尋可能路徑的算法改進，實現(xiàn)能夠同時輸出多條可能路徑的功能。而最優(yōu)路徑也有可能有多條，因此可以改進搜索最優(yōu)路徑的算法，使其能夠輸出全部的最優(yōu)路徑?？梢钥紤]加入多重標記的方法實現(xiàn)。4.4經(jīng)驗和體會 電路板布線問題實際上就是迷宮求解問題，電路板上的布線要求可以轉(zhuǎn)化成迷宮的通路和不通路的問題，當(dāng)電線可以經(jīng)過該點時，該點即為通路，而當(dāng)電線不能經(jīng)過該點時，它即為死路，利用1,0分別表示通路和死路，就可以建立類似迷宮求解的模型，通過棧和隊列的一系列數(shù)據(jù)結(jié)構(gòu)的輔助，來求解迷宮問題。5. 使用說明運行程序，系統(tǒng)會自動給出一個隨機電路板矩陣，自動輸出一個可能的布線路徑和最優(yōu)布線路徑，并給出搜尋路徑的標記圖；若該電路板不存在可行路徑，則會提示沒有通路。6. 測試結(jié)果（截屏）（1）隨機生成的電路板矩陣：（2）可能布線路徑：（3）最短布線路徑：7. 附錄7.1個人負責(zé)模塊的程序代碼int WirePath(int* 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)前位置可通過，即未走過 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+) 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!=S.base) MarkPrint(e.seat);/留下不能通過標記 Pop(S,e);/退一步 if(e.di5) 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;in;i+) for(j=0;jn;j+) printf(%dt,Boardij); printf(n); return 0;int FindShortWay(int* Board,Position start,Position finish)/搜尋最短布線路徑算法 if(finish.x=start.x&finish.y=start.y)/起點為終點，結(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(沒有通路!n);return 0; Boardstart.xstart.y=2;while(1)/利用隊列，將每個通道塊都做上標記，起點標記為2，其余按到達步數(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(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/移動標記 int ord; Position seat; int di;SWire;typedef struct/棧 SWire* base; SWire* top; int stacksize;Stack;typedef struct QNode/隊列 Position data; struct QNode* next;QNode,*QP;typedef struct QP fron; QP rear;LinkQ;int* Board;/電路板int MShortPath;/最短路徑const int n=10;/電路板大小int CreateBoard()/創(chuàng)建一個電路板 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;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(隨機生成的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+=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)/留下不可布線的標志 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-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(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+) 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(沒有通路!nn搜尋路徑圖(-3表示布線，-1表示死路）：n); for(i=0;in;i+) for(j=0;jnext=NULL; return 1;int DestroyQ(LinkQ& Q)/摧毀隊列 while(Q.fron) Q.rear=Q.fron-next; free(Q.fron); Q.fron=Q.rear; return 1;int EnQ(LinkQ& Q,Position e)/入隊列 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)/出隊列 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(p); return 1;int FindShortWay(int* Board,Position start