《算法电路布线》PPT课件.ppt

动态规划 电路布线 动态规划算法整体思想 将待求解问题分解成若干个子问题 先求解子问题 然后从这些子问题的解得到原问题的解 子问题之间不是相互独立的保存已解决的子问题的答案 在需要时再找出已求得的答案 这样可以避免大量的重复计算 用一个表格记录所有已解决的子问题的答案分解若干子问题 子问题不相互独立 被计算很多次 保存已解决问题答案 需要时取出 避免重复计算 子问题之间不相互独立 找出最优解的性质 并刻划其结构特征 递归地定义最优值 以自底向上的方式计算出最优值 根据计算最优值时得到的信息 构造最优解 全是理论 问题描述 在一块电路板的上 下两端分别有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条连线分布到若干绝缘层上 在同一层上的连线不相交 电路布线问题要确定将哪些连线安排在第一层上 使得该层上有尽可能多的连线 换句话说 该问题要求确定导线集Nets i i 1 i n 的最大不相交子集 1 最优子结构性质记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 j i 此时 若 i i MNS i j 则对任意 t t MNS i j 有t i且 t i 否则 t t 与 i i 相交 在这种情况下MNS i j i i 是N i 1 i 1 的最大不相交子集 否则 子集MNS i 1 i 1 i i 包含于N i j 是比MNS i j 更大的N i j 的不相交子集 这与MNS i j 的定义相矛盾 若 i i 不属于MNS i j 则对任意 t t MNS i j 有t i 从而MNS i j 包含于N i 1 j 因此 Size i j Size i 1 j 另一方面 MNS i 1 j 包含于N i j 故又有Size i j Size i 1 j 从而Size i j Size i 1 j 2 递归计算最优值电路布线问题的最优值为Size n n 由该问题的最优子结构性质可知 子问题最优值的递归关系如下 1 当i 1时 2 当i 1时 状态转移顺序 自底向上 先算上排接线柱只有1个 2个的最优布线 然后求上排接线柱有多个的最优布线 关键一步 写出递归表达式 3 根据上面递归式可以得到二维表 红色标明的就是算法选择的路径 向上优先 在斜角值改变时可以取得所求的子集 即9 10 7 9 5 5 3 4 设计动态规划算法如下 其中size i j 表示函数Size i j 的值 voidMNS C n size for j 0 j C 1 j size 1 j 0 for j C 1 j n j size 1 j 0 for i 2 i n i for j 0 j C i j size i j size i 1 j j i 的情况for j C j j n j j i 的情况size i j max size i 1 j size i 1 C i 1 1 size n n max size n 1 n size n 1 C n 1 1 4 构造最优解 voidTraceback C size n Net m intj n m 0 for inti n i 1 i if size i j s