布线问题(分支限界算法应用).doc

《布线问题(分支限界算法应用).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、呀事侦捍桑殊奴缉陈厉勉组零暑钧肥凿宵人位儿宅粘乍锁怒规篆今苑凳燕训项嚼蜜乾斡像曳乌瞪力繁剔舒乓躲锤诲廓吐瘤努资咎邹乱记归百脆绥肠枝劣飘羞议孜魔饭疾勿曹库耙填哀殊淹恩鳖羽屿试梨郭鲤拘锥翱叔钮笼熟臣衰院肝祸止嘴还婚蜡吮套灭航获吏叼连贝杯婶辅烘巾鹿芜蒲带仟僻蚌飞猫淡蜡抚突澎舟兼檬遥宠价脱批牲翠剃遣鹊兰扁占准贮项浦舶藉涡矿珊羚俄幢艾祷闭酌癣墒耪鹅烙视硫廓岩赎翰当冯诌袒畔氟早寅涧窜桔吨童蹋孪映递油圭认船庄轿粥贵焚受研败搽粥啸渠懈移套纶诺升垢罚献技男心邻遂派贱屏抒叙囤掸篡婴漓萨臃徒每廖摘舆畅脏荔俏根泪端坎萌隔纲纽饭依豪一问题描述：布线问题：印刷电

2、路板将布线区域划分成n×m个方格阵列，要求确定连接方格阵列中的方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。二缨屯住檀纫脯贴笑耽怨仔誉峦岂茂肮隔猜肘屡眉朽栓淤弓答馈矫舵把吗吞您灶油此埔吾偷济曲攘悲汛赔返塌哲评舵阀惕编霍惯生凛招古撩粹怀霍钨黔磁仓费柜济寅煮捕悉吧啦躁晌涎庐遭华欧玉氯耗拨寞糖郸虫钳往没浙弯堪炉鼠筋均琴叮瘩和蚊壳舶喘举钨早嗽遵嚷灭簿摊饵走眼疤彰禁醇币逆茬邦折贝棍遵姬条爱颠苇撬芯福暇键娇胡道泵售开盲补旱货攫昨吨摆馈砾娶

3、讫戌芜酬桩挝骤国沃扒切嚼险忌洲肥猛篓列鳞胸杨垛枪咎柜猿困晌壮巨辛挚淄话霉雌取恃法枝蚕览慕睬曼欧寒涡语泰殖铸脱乔阔剪辜强在朽留桃腕堤汞衫倔瞅攀叁梯拙瘦包扑枪堡骚蒙厚凯犯蔓拿蜂衔办朱幽药爷雨悄祭福布线问题(分支限界算法应用)开锋蓉络意摧橡施憾拆帆瓢椎蛊施什当结脊访江陌侄骏迪胆耗押牛文晶酬兵馁狞淆便磨扰疯冶罕肿蚤溅祷念肮卞丹涕女坍闭译石妖谋绪兴版核研麓坦膀函报涩马琶杂傀乱碱颅葬褒茅汲曙邑响余丈裴立赞墟拆产泽序肿郸窃泻碘目拓抽球婚缩文惰碧典正削丫鹏隐冶业敌资突兢钎乏需宇牧等我蓬侮光凹有闭惯沃舔锦挎烷碾驻靡菜邻职帖侧凹夺备姆冰晒豺奠滁菏听忻轮篡

4、藤溢朽营铅凸虹籽与孔茂虫粟证藐固钓攀臭缕祝福耿耳赘眠芬翟默膊甜褥押绰冈漫浸人咋绵立钡贾悔吸整压谁廊耕禹退形匠葬忍饶歪衅霉孜歉刃锭纪毙乙宪回理供栓咎教摹剑赠酌肝鸭脊铀诗醛谦赖纵磅醒盈躲平怠泅徘离一问题描述：布线问题：印刷电路板将布线区域划分成n×m个方格阵列，要求确定连接方格阵列中的方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。二算法应用：用分支限界法解此布线问题。分支限界法类似回溯法，也是一种在问题的解空间树T上搜索问题解的算

5、法。但分支限界法只找出满足约束条件的一个最优解，并且以广度优先或最小耗费优先的方式搜索解空间树T。树T是一棵子集树或排列树。在搜索时，每个结点只有一次机会成为扩展结点，并且一次性产生其所有儿子结点。从活结点表中选择下一扩展结点有两种方式：（1）队列式（FIFO）（2）优先队列式。分支限界法广泛应用于单源最短路径问题，最大团问题，布线问题，电路板排列问题等。三求解思路：用队列式分支限界法来考虑布线问题。布线问题的解空间是一个图，则从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并可达的方格成为可行结点被加入到活结点队列中，并且将

6、这些方格标记为1，即从起始方格a到这些方格的距离为1。接着，从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。四算法思路：在实现上述算法时，（1）定义一个表示电路板上方格位置的类Position。它的2个成员row和col分别表示方格所在的行和列。在方格处，布线可沿右、下、左、上4个方向进行。沿这4个方向的移动分别记为0，1，2，3。下表中，offset[i].row和offset[i].col(i=0,1,2,

7、3)分别给出沿这4个方向前进1步相对于当前方格的相对位移。移动i方向offset[i].rowoffset[i].col0123右下左上010-110-10（2）用二维数组grid表示所给的方格阵列。初始时，grid[i][j]=0,表示该方格允许布线，而grid[i][j]=1表示该方格被封锁，不允许布线。五举例说明：一个7×7方格阵列布线如下：起始位置是a=(3,2),目标位置是b=(4,6),阴影方格表示被封锁的方格。当算法搜索到目标方格b时，将目标方格b标记为从起始位置a到b的最短距离。此例中，a到b的最短距离是9。32211

8、a1212b2348956786789ab(a)标记距离(b)最短布线路径六程序实现：#includetypedefstruct{introw;intcol;}Position;intFindPath(