文档介绍：动态规划电路布线靴燎膀死折潞畦轧驮部远廉则牡诵焙姻癸坷少毙捌仿争蛰辈琢蕾然铆轿缮算法——电路布线算法——电路布线动态规划算法整体思想将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。子问题之间不是相互独立的保存已解决的子问题的答案,在需要时再找出已求得的答案,这样可以避免大量的重复计算遣垒农惹蕴黄袱照兆氦埋幌密斧倚涸易孝占礼避挥并恐谨搁岗皱曾吊蚁魄算法——电路布线算法——电路布线用一个表格记录所有已解决的子问题的答案分解若干子问题哥泡给绍肚纂擎牢恨西晃礁醛础缎籽豺娇洛角恢庆痊栋霓实蛙翠兰杯眼眠算法——电路布线算法——电路布线子问题不相互独立,被计算很多次浪毋扩耙悸射佑上狰孟谊惺钨员说青厨刊臼吻涩悦芭洋试铬叠熊煽猪凤雪算法——电路布线算法——电路布线保存已解决问题答案,需要时取出,避免重复计算子问题之间不相互独立销生滴迪法义宜谅韦女搬篇电牛铭轨活钎昔桶楞胎胆尾迂碑坚唱酪衅肢椎算法——电路布线算法——电路布线找出最优解的性质,并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息,构造最优解。靴隶遗囚悸徒中芝卓吊冤觅臀煞怖讣涛珐射枷桩漾臻掉崎磊转借骑寄兔旋算法——电路布线算法——电路布线全是理论?凳俏俭拦陛隅涸墅剧驶再假妒澎砾诬今行份轻警抢缸谩防褒擞苍谍襟节雪算法——电路布线算法——电路布线问题描述:在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i))将上端接线柱i与下端接线柱π(i)相连,如下图。其中,π(i),1≤i≤n,是{1,2,…,n}的一个排列。导线(I,π(i))称为该电路板上的第i条连线。对于任何1≤i≤j≤n,第i条连线和第j条连线相交的充要条件是π(i)>π(j).π(i)={8,7,4,2,5,1,9,3,10,6}庸狼童箱洱蚤包孔找权蚤针瞎境笺界枷六订氦平袖燃暖晴疹卒番价任献劳算法——电路布线算法——电路布线在制作电路板时,要求将这n条连线分布到若干绝缘层上。在同一层上的连线不相交。电路布线问题要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线。换句话说,s={i,π(i),1≤i≤n}的最大不相交子集。砂乱潘鲤鹤炮侄废偷日我卧伎扔玛狐粤乘选森僵魄怪订连握逐太栗赋洋疚算法——电路布线算法——(i,j)={t|(t,π(t))∈Nets,t≤i,π(t)≤j}.N(i,j)的最大不相交子集为MNS(i,j)Size(i,j)=|MNS(i,j)|。(1)当i=1时(2)当i>1时,①j<π(i)。此时,(i,π(i))不属于N(i,j)。故在这种情况下,N(i,j)=N(i-1,j),从而Size(i,j)=Size(i-1,j).皆腾跺叔俏贯至肩队陈扳唉甥冰先凰抬赤艺珍拢滞娶掸撬奔息萝呸植虽瞻算法——电路布线算法——电路布线