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

教育資料教育資料實(shí)驗(yàn)二電路布線問題問題定義及需求分析1.課1題目的和任務(wù)問題描述：印刷電路板將布線區(qū)域劃分為X個(gè)方格陣列。在布線時(shí)，電路只能沿直線或直角布線。為避免線路相交，已布線的方格要做封鎖標(biāo)記。設(shè)起始位置為，終止位置為，求解電路布線問題。實(shí)驗(yàn)要求：設(shè)計(jì)印刷電路板的布線模擬程序。1采）用?；蜿?duì)列等數(shù)據(jù)結(jié)構(gòu)。采用窮舉法的回溯搜索，求到可能的布線線路。推薦采用層次優(yōu)先搜索，求到最優(yōu)的布線線路。.數(shù)2據(jù)形式輸入數(shù)據(jù)形式：通過生成隨機(jī)數(shù)的函數(shù)隨機(jī)生成一個(gè)矩陣。輸入值的范圍：生成的矩陣中的數(shù)值為 型，為或者，其中表示死路，1表示通路。輸出數(shù)據(jù)形式：輸出到顯示器。.程3序功能隨機(jī)給定一個(gè)線路分布矩陣，利用窮舉法，通過棧的應(yīng)用，求出從到的可能布線線路；采用層次優(yōu)先搜索，通過隊(duì)列的應(yīng)用，求出到的最優(yōu)布線線路。.測4試數(shù)據(jù)測試數(shù)據(jù)為隨機(jī)生成的矩陣。概要設(shè)計(jì).抽1象數(shù)據(jù)類型需要定義一個(gè)位置類型的數(shù)據(jù)，里面包含型的和坐標(biāo)，用來記錄位置信息；再定義一個(gè) 的通道塊數(shù)據(jù)類型，里面包含該通道塊的位置數(shù)據(jù)，在路徑上的序號(hào)和方向信息；另外還需要構(gòu)建棧和隊(duì)列的基本結(jié)構(gòu)類型。主2程序流程及各模塊之間的調(diào)用關(guān)系［開始)隨機(jī)生成電路板矩

陣CreateBoard()利用棧搜索可能路

徑WirePath()/輸出可能路/ 徑和搜索圖利用隊(duì)列搜索最短

路徑FindShortway()/輸出可能路徑和搜索圖詳細(xì)設(shè)計(jì)3.存1儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)位置移動(dòng)標(biāo)記隊(duì)列負(fù)2責(zé)模塊的偽碼算法尋/找路徑算法若有從電路板的入口到出口 的通道，則求得一條存放在棧中(/從棧底到棧頂)InitStack(S);設(shè)定當(dāng)前位置為入口位置探索第一步do{當(dāng)前位置可通過，即是未曾走到的通道塊留下足跡e=(curstep,curpos,1);加入路徑到達(dá)出口(終點(diǎn))輸出路徑電路板的搜尋圖}返回return1;若若}下一位置是當(dāng)前位置的東鄰探索下一步}當(dāng)前位置不能通過Pop(S,e);?？樟粝虏荒芡ㄟ^的標(biāo)記，并退回一步換下一個(gè)方向探索設(shè)定當(dāng)前位置是該新方向/上/的相鄰塊沒有通路電路板的搜尋圖/搜尋最短布線路徑算法到達(dá)終點(diǎn)，結(jié)束標(biāo)記當(dāng)前位置沒有通路有通路，則令其值為將第一個(gè)通道塊賦值2并將其相鄰?fù)ǖ缐K從右開始，按順時(shí)/針依次入隊(duì)列，當(dāng)隊(duì)列不空時(shí)，出隊(duì)列一個(gè)通道塊，對(duì)其相鄰?fù)ǖ缐K做相/同操作，直至所有的未標(biāo)記通路通道塊都被標(biāo)記后為止。對(duì)其相鄰?fù)ǖ缐K賦值該通道塊可通過且未標(biāo)記到達(dá)終點(diǎn)，結(jié)束將該通道塊入隊(duì)列已全部標(biāo)記，結(jié)束循環(huán)沒有通路，結(jié)束出隊(duì)列反/向/搜尋最短布線路徑標(biāo)記當(dāng)前位置為結(jié)束位置反向搜索最短路徑th[j]=curpos;在相鄰?fù)ǖ缐K中找符合的標(biāo)記值當(dāng)前位置為相鄰?fù)ǖ缐K輸出最短布線路徑輸出最短路徑搜尋矩陣調(diào)試分析4.問1題分析與解決方法（1尋）找可能路徑若當(dāng)前位置可通過，則納入當(dāng)前路徑，并繼續(xù)朝著下一位置探索，即切換下一位置為當(dāng)前位置，如此重復(fù)直至到達(dá)出口；若當(dāng)前位置不可通，則應(yīng)順著來向退回到前一通道塊，然后朝著除來向之外的其他方向繼續(xù)探索；若該通道塊的四周4個(gè)方塊均不可通，則應(yīng)從當(dāng)前路徑上刪除該通道塊。所謂下一位置指的是當(dāng)前位置四周4個(gè)方向（東南西北）上相鄰的方塊。假設(shè)以棧記錄當(dāng)前路徑，則棧頂中存放的是當(dāng)前路徑上的最后一個(gè)通道塊。由此，納入路徑的操作即為當(dāng)前位置入棧；從當(dāng)前路徑上刪除前一通道塊的操作即為出棧。通過入棧和出棧操作，使得當(dāng)前位置找尋到出口位置，從而實(shí)現(xiàn)對(duì)迷宮一個(gè)可能路徑的求解。（2尋）找最優(yōu)路徑標(biāo)記當(dāng)前位置，通過隊(duì)列，將當(dāng)前位置周圍的四個(gè)通道塊入隊(duì)列，將當(dāng)前位置標(biāo)記值后，出隊(duì)列，對(duì)該通道塊執(zhí)行相同的操作，并標(biāo)記值 ,通過循環(huán)操作，直到當(dāng)前位置為出口時(shí)終止。借助隊(duì)列，通過循環(huán)操作，使每個(gè)通道塊都被賦值。然后標(biāo)記當(dāng)前位置為出口，從出口向入口尋找符合遞減值的通道塊，從而確定出最短路徑。.算2法的時(shí)空分析（1）尋找可能路徑時(shí)間復(fù)雜度：O（n2）空間復(fù)雜度：O（1）（2）尋找最優(yōu)路徑時(shí)間復(fù)雜度：O（n2）空間復(fù)雜度：O（D4.算3法的改進(jìn)設(shè)想通過對(duì)搜尋可能路徑的算法改進(jìn)，實(shí)現(xiàn)能夠同時(shí)輸出多條可能路徑的功能。而最優(yōu)路徑也有可能有多條，因此可以改進(jìn)搜索最優(yōu)路徑的算法，使其能夠輸出全部的最優(yōu)路徑?？梢钥紤]加入多重標(biāo)記的方法實(shí)現(xiàn)。4.經(jīng)4驗(yàn)和體會(huì)電路板布線問題實(shí)際上就是迷宮求解問題，電路板上的布線要求可以轉(zhuǎn)化成迷宮的通路和不通路的問題，當(dāng)電線可以經(jīng)過該點(diǎn)時(shí)，該點(diǎn)即為通路，而當(dāng)電線不能經(jīng)過該點(diǎn)時(shí)，它即為死路，利用1,分0別表示通路和死路，就可以建立類似迷宮求解的模型，通過棧和隊(duì)列的一系列數(shù)據(jù)結(jié)構(gòu)的輔助，來求解迷宮問題。使用說明運(yùn)行程序，系統(tǒng)會(huì)自動(dòng)給出一個(gè)隨機(jī)電路板矩陣，自動(dòng)輸出一個(gè)可能的布線路徑和最優(yōu)布線路徑，并給出搜尋路徑的標(biāo)記圖；若該電路板不存在可行路徑，則會(huì)提示沒有通路。.測試結(jié)果（截屏）（1）隨機(jī)生成的電路板矩陣：一-If國勝成的1DX1口電路板的分布情況為（可通,口不口J通）:) 0D000000D)11111010D)11011001D)11111101D)11111101D)1D101111D) 01011110D)1D111111D)111101110) 0D000000D（2）可能布線路徑：

卜能布線踣徑為1(1,D-Xl, 4)-XL5)->(2, 5)->(3,G)->(4, 6)->(5,T)->(6,7)->(T,7)->(.7,3)->(8,8)［搜尋路徑圖（■裱示布線,T表不死路）：0 0000000000 -3-3-3-3-30100Q 11D1-30-10 1111-3-3?-110 11111-3i"-1■-I0 L01U1-3-3-100 010111-300； L01111-3-300 1111011-3.1Q UDD0000（3）最短布線路徑：信能布線踣徑為?(Ln D->t3nD-X4,l)->(4n2)-)(4,3)->(4>4”>〔蟲5)->(5n5)->(6,5)->(7,5)->(?n6)->(8,G]-J(Sn7)->(E,S)搜尋路徑圖.0 D000000000 2a45601000 34067001600 4567B901500 57891001400 60801011121300 D1121112L30001014131213L41500 111514014L51600 00ii0iiiaProcessreturosc10go：BxscutinntlDDUB：0.798Pres2anykeytc\cantinue.附錄.個(gè)1人負(fù)責(zé)模塊的程序代碼尋找路徑算法設(shè)定當(dāng)前位置為入口位置探索第一步當(dāng)前位置可通過，即未走過

留下足跡加入路徑到達(dá)終點(diǎn)PrintStack(S);搜尋路徑圖 表示布線，表示死路)：下一個(gè)位置是當(dāng)前位置的東鄰探索下一步}當(dāng)前位置不能通過留下不能通過標(biāo)記退一步Pop(S,e)換下一個(gè)方向探索設(shè)定當(dāng)前位置是該新方向上的相鄰塊沒有通路 搜尋路徑圖 表示布線，表示死路):路徑算法搜尋最短布線起點(diǎn)為終點(diǎn)，結(jié)束設(shè)定起始位置為當(dāng)前位置沒有通路/利用隊(duì)列，將每個(gè)通道塊都做上標(biāo)記，起點(diǎn)標(biāo)記為2，其余按到達(dá)步數(shù)依次累加當(dāng)前通道塊可探索標(biāo)記如/果鄰接通道塊為終點(diǎn)，則結(jié)束循環(huán)該通道塊入隊(duì)列沒有通路所有通道塊均被沒有通路標(biāo)記，結(jié)束出隊(duì)列反/向搜/尋最短布線路徑輸出/最/短布線路徑輸出/最/短路徑搜尋矩陣搜尋路徑圖：程2序全部代碼反向搜尋符合值符合即結(jié)束記位置移動(dòng)標(biāo)記隊(duì)列電路板最短路徑電路板大小創(chuàng)建一個(gè)電路板隨機(jī)生成的 電路板的分布情況為（可通，不可通）摧毀電路板創(chuàng)建空棧電線通過判定布線入棧出棧嘗試相鄰位置留下不可布線的標(biāo)志輸出棧內(nèi)