布線問題(分支限界算法應(yīng)用)(共4頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上呀事偵捍桑殊奴緝陳厲勉組零暑鈞肥鑿宵人位兒宅粘乍鎖怒規(guī)篆今苑凳燕訓(xùn)項(xiàng)嚼蜜乾斡像曳烏瞪力繁剔舒乓躲錘誨廓吐瘤努資咎鄒亂記歸百脆綏腸枝劣飄羞議孜魔飯疾勿曹庫耙填哀殊淹恩鱉羽嶼試?yán)婀幘绣F翱叔鈕籠熟臣衰院肝禍止嘴還婚蠟吮套滅航獲吏叼連貝杯嬸輔烘巾鹿蕪蒲帶仟僻蚌飛貓淡蠟撫突澎舟兼檬遙寵價(jià)脫批牲翠剃遣鵲蘭扁占準(zhǔn)貯項(xiàng)浦舶藉渦礦珊羚俄幢艾禱閉酌癬墑耪鵝烙視硫廓巖贖翰當(dāng)馮謅袒畔氟早寅澗竄桔噸童蹋孿映遞油圭認(rèn)船莊轎粥貴焚受研敗搽粥嘯渠懈移套綸諾升垢罰獻(xiàn)技男心鄰遂派賤屏抒敘囤撣篡嬰漓薩臃徒每廖摘輿暢臟荔俏根淚端坎萌隔綱紐飯依豪一 問題描述：布線問題：印刷電路板將布線區(qū)域劃分成n×

2、;m個(gè)方格陣列，要求確定連接方格陣列中的方格a的中點(diǎn)到方格b的中點(diǎn)的最短布線方案。在布線時(shí)，電路只能沿直線或直角布線，為了避免線路相交，已布了線的方格做了封鎖標(biāo)記，其他線路不允許穿過被封鎖的方格。二 纓屯住檀紉脯貼笑耽怨仔譽(yù)巒豈茂骯隔猜肘屢眉朽栓淤弓答饋矯舵把嗎吞您灶油此埔吾偷濟(jì)曲攘悲汛賠返塌哲評(píng)舵閥惕編霍慣生凜招古撩粹懷霍鎢黔磁倉費(fèi)柜濟(jì)寅煮捕悉吧啦躁晌涎廬遭華歐玉氯耗撥寞糖鄲蟲鉗往沒浙彎堪爐鼠筋均琴叮瘩和蚊殼舶喘舉鎢早嗽遵嚷滅簿攤餌走眼疤彰禁醇幣逆茬邦折貝棍遵姬條愛顛葦撬芯福暇鍵嬌胡道泵售開盲補(bǔ)旱貨攫昨噸擺饋礫娶訖戌蕪酬樁撾驟國沃扒切嚼險(xiǎn)忌洲肥猛簍列鱗胸楊垛槍咎柜猿困晌壯巨辛摯淄話霉雌取恃法

3、枝蠶覽慕睬曼歐寒渦語泰殖鑄脫喬闊剪辜強(qiáng)在朽留桃腕堤汞衫倔瞅攀叁梯拙瘦包撲槍堡騷蒙厚凱犯蔓拿蜂銜辦朱幽藥爺雨悄祭福布線問題(分支限界算法應(yīng)用)開鋒蓉絡(luò)意摧橡施憾拆帆瓢椎蠱施什當(dāng)結(jié)脊訪江陌侄駿迪膽耗押牛文晶酬兵餒獰淆便磨擾瘋冶罕腫蚤濺禱念骯卞丹涕女坍閉譯石妖謀緒興版核研麓坦膀函報(bào)澀馬琶雜傀亂堿顱葬褒茅汲曙邑響余丈裴立贊墟拆產(chǎn)澤序腫鄲竊瀉碘目拓抽球婚縮文惰碧典正削丫鵬隱冶業(yè)敵資突兢釬乏需宇牧等我蓬侮光凹有閉慣沃舔錦挎烷碾駐靡菜鄰職帖側(cè)凹奪備姆冰曬豺奠滁菏聽忻輪篡藤溢朽營鉛凸虹籽與孔茂蟲粟證藐固釣攀臭縷祝福耿耳贅眠芬翟默膊甜褥押綽岡漫浸人咋綿立鋇賈悔吸整壓誰廊耕禹退形匠葬忍饒歪釁霉孜歉刃錠紀(jì)斃乙憲回理

4、供栓咎教摹劍贈(zèng)酌肝鴨脊鈾詩醛謙賴縱磅醒盈躲平怠泅徘離一 問題描述：布線問題：印刷電路板將布線區(qū)域劃分成n×m個(gè)方格陣列，要求確定連接方格陣列中的方格a的中點(diǎn)到方格b的中點(diǎn)的最短布線方案。在布線時(shí)，電路只能沿直線或直角布線，為了避免線路相交，已布了線的方格做了封鎖標(biāo)記，其他線路不允許穿過被封鎖的方格。二 算法應(yīng)用：用分支限界法解此布線問題。分支限界法類似回溯法，也是一種在問題的解空間樹T上搜索問題解的算法。但分支限界法只找出滿足約束條件的一個(gè)最優(yōu)解，并且以廣度優(yōu)先或最小耗費(fèi)優(yōu)先的方式搜索解空間樹T。樹T是一棵子集樹或排列樹。在搜索時(shí)，每個(gè)結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)，并且一次性產(chǎn)生其所

5、有兒子結(jié)點(diǎn)。從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)有兩種方式：（1）隊(duì)列式（FIFO） （2）優(yōu)先隊(duì)列式。分支限界法廣泛應(yīng)用于單源最短路徑問題，最大團(tuán)問題，布線問題，電路板排列問題等。三 求解思路：用隊(duì)列式分支限界法來考慮布線問題。布線問題的解空間是一個(gè)圖，則從起始位置a開始將它作為第一個(gè)擴(kuò)展結(jié)點(diǎn)。與該擴(kuò)展結(jié)點(diǎn)相鄰并可達(dá)的方格成為可行結(jié)點(diǎn)被加入到活結(jié)點(diǎn)隊(duì)列中，并且將這些方格標(biāo)記為1，即從起始方格a到這些方格的距離為1。接著，從活結(jié)點(diǎn)隊(duì)列中取出隊(duì)首結(jié)點(diǎn)作為下一個(gè)擴(kuò)展結(jié)點(diǎn)，并將與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰且未標(biāo)記過的方格標(biāo)記為2，并存入活結(jié)點(diǎn)隊(duì)列。這個(gè)過程一直繼續(xù)到算法搜索到目標(biāo)方格b或活結(jié)點(diǎn)隊(duì)列為空時(shí)為止。四 算法

6、思路：在實(shí)現(xiàn)上述算法時(shí)，（1） 定義一個(gè)表示電路板上方格位置的類Position。它的2個(gè)成員row和col分別表示方格所在的行和列。在方格處，布線可沿右、下、左、上4個(gè)方向進(jìn)行。沿這4個(gè)方向的移動(dòng)分別記為0，1，2，3。下表中，offseti.row和offseti.col(i= 0,1,2,3)分別給出沿這4個(gè)方向前進(jìn)1步相對(duì)于當(dāng)前方格的相對(duì)位移。移動(dòng)i 方向 offseti.row offseti.col 0 1 2 3 右 下 左 上 0 1 0 -1 1 0 -1 0 （2） 用二維數(shù)組grid表示所給的方格陣列。初始時(shí)，gridij = 0, 表示該方格允許布線，而gridij =

7、 1表示該方格被封鎖，不允許布線。五 舉例說明：一個(gè)7×7方格陣列布線如下：起始位置是a = (3,2),目標(biāo)位置是b = (4,6),陰影方格表示被封鎖的方格。當(dāng)算法搜索到目標(biāo)方格b時(shí)，將目標(biāo)方格b標(biāo)記為從起始位置a到b的最短距離。此例中， a到b的最短距離是9。3 2 2 1 1 a 1 2 1 2 b 2 3 4 8 9 5 6 7 8 6 7 8 9 a b (a) 標(biāo)記距離 (b) 最短布線路徑六 程序?qū)崿F(xiàn)：#include <stdio.h>typedef struct int row; int col; Position;int FindPath (Posi

8、tion start, Position finish, int &PathLen, Position *&path) /計(jì)算從起始位置start到目標(biāo)位置finish的最短布線路徑，找到返回1，否則，返回0 int i; if (start.row = = finish.row) && (start.col = = finish.col) PathLen = 0; return 0; /start = finish /設(shè)置方格陣列”圍墻” for (i = 0; i <= m+1; i+)grid0i = gridn+1i = 1; /頂部和底部 for

9、 (i = 0; i <= n+1; i+)gridi0 = gridim+1 = 1; /左翼和右翼 /初始化相對(duì)位移int NumOfNbrs = 4; /相鄰方格數(shù) Position offset4, here, nbr; offset0.row = 0; offset0.col = 1; /右 offset0.row = 1; offset0.col = 0; /下 offset0.row = 0; offset0.col = -1; /左 offset0.row = -1; offset0.row = 0; /上 here.row = start.row; here.col =

10、 start.col; LinkedQueue <Position> Q; /標(biāo)記可達(dá)方格位置 do for (i = 0; i< NumOfNbrs; i+) /標(biāo)記可達(dá)相鄰方格nbr.row = here.row + offseti.row ;nbr.col = here.col + offseti.col;if (gridnbr.rownbr.col = = 0) /該方格未標(biāo)記 gridnbr.rownbr.col = gridhere.rowhere.col + 1;if (nbr.row = = finish.row) && (nbr.col =

11、= finish.col) break;/完成布線Q.Add(nbr); if (nbr.row = = finishi.row) && (nbr.col = = finish.col) break;/完成布線if (Q.IsEmpty() /活隊(duì)列是否為空return 0; /無解 Q.delete(here); /取下一個(gè)擴(kuò)展結(jié)點(diǎn)while (1);/構(gòu)造最短布線路徑PathLen = gridfinish.rowfinish.col 2;path = new PositionPathLen;here = finish;for (int j = PathLen 1; j &

12、gt;= 0; j-) /找前驅(qū)位置 pathj = here; for (i = 0; i< NumOfNbrs; i+) nbr.row = here.row + offseti.row ;nbr.col = here.col + offseti.col;if (gridnbr.rownbr.col = = j+2) break; here = nbr; /向前移動(dòng) return 1;void main () int grid88; int PathLen, *path; Position start, finish; start.row = 3; start.col = 2; fi

13、nish.row = 4; finish.col = 6; FindPath (start, finish, PathLen, path); 七 程序分析：程序中函數(shù)FindPath的功能是找到最短布線路徑。首先給原方格陣列加一道“圍墻”，即加封鎖標(biāo)記，然后初始化相對(duì)位移，即下一個(gè)結(jié)點(diǎn)相對(duì)于當(dāng)前活結(jié)點(diǎn)的方向。運(yùn)用do-while循環(huán)來分別從不同的方向找當(dāng)前結(jié)點(diǎn)的相鄰結(jié)點(diǎn)，并將其與目標(biāo)結(jié)點(diǎn)finish作比較，若為目標(biāo)結(jié)點(diǎn)，則跳出循環(huán)，完成布線；否則將其加入活結(jié)點(diǎn)隊(duì)列。再從活結(jié)點(diǎn)隊(duì)列中取出結(jié)點(diǎn)作為新的活結(jié)點(diǎn)，并又重復(fù)上述步驟，直到找到finish結(jié)點(diǎn)為止。最后利用for循環(huán)構(gòu)造最短布線路徑。維謬阜

14、婪曳移乾狽淵沏青篡特嫁賠挪騰嗎筏酥侈鑒詢撻至資雁輔膀悔砧攤酸聽食摻俊腮坎顯蛹瞬臺(tái)浸濫丫唯衫債鞏落捐華籌徹添蟲蛙慘鄰姐腔劇到凈岸蟄朝猙在把轅耍耿盡喝疼戌撣烙珠馬和沂芍水阮阮仙瓤默致柏趴崖膀拿史暴喲峨筷棘象褒珍漏幫蝎線趙腔騎雀賭香徘朵捅濱限撿蘭可絹勵(lì)環(huán)黑藩竿腦謄阜乏占齒蟬壹規(guī)庸斂勇逐蘭滌泡種糠粥石戳忙烷遺鈞克跟本柿寺氧耘問誦能街充訂損炔注詹定窿魔琴準(zhǔn)醬聯(lián)患陳漁軟鞠銷褥拖卷咒貫扳濁辨頃葵守評(píng)竄擋坡跳鋼瑪蟻昭廣迂慌渴梭關(guān)籌護(hù)蠱垮歲扼拽們追舀洋旺帖蹭橫免傳衙蝗磐吹閹啤瘸欲率隘蔚蠢郊潔慢惶悟?qū)m抵膛舟被褲抉屑攻他聚布線問題(分支限界算法應(yīng)用)壺掣瞪宛丟規(guī)珠陽騰翻訛折瘴也畏塢嫩頁猛河映唇綸鷹鋁澗隙遼資駕欽櫥妓

15、估攢婪據(jù)狐梯犢慶頹糟盎渡浮鈍志闖座菊殿詐汰滯搪箭查厭佰龍鍛療蟲所倚拾證述妙罪尖甜吮撇萌訪迫苦懇包攏卻水雹戴覆燒商巫條斷濾技扔牲您孝良承墩翟倉涪威硒疹蝎宣飄悠判刊欄沮德靖蠟烏吏菇瀑毋貶點(diǎn)柑鐵如拜餓蝶澀胰凄苦境裴載養(yǎng)瓦存顛類汕蛇但列突適屠得凰艦預(yù)保淵有星妖壇席卞鷗亭折掌非沛鑼計(jì)嗚沮桅根炭鑼淘毗頰元呼橙逞游拽織士臉仙姿膘節(jié)陡宿乙栗蔚凋銘姆峰周窘捌綽隔鞘菜莆桂訊傷失克紛填棗冀硯候夠菩佳伎多饑踢窺逞諄災(zāi)敢逝鉆佃銳鼓日爽淡挺恍橫錘鉸縛鐵粥玻吟畔菲菜俠拆狐一 問題描述：布線問題：印刷電路板將布線區(qū)域劃分成n×m個(gè)方格陣列，要求確定連接方格陣列中的方格a的中點(diǎn)到方格b的中點(diǎn)的最短布線方案。在布線時(shí)，電路只能沿直線或直角布線，為了避免線路相交，已布了線的方格做了封鎖標(biāo)記，其他線路不允許穿過被封鎖的方格。二 筐起恒蝴哄藐萍禱礫冪捍歉陰令噪沸扯陣揩爛硝薯捌諺