动态规划电路布线问题（Java 代码实现）

若尘

关注

发布于: 2021 年 06 月 11 日

电路布线

问题分析

电路布线的官方解释我就不加赘述了，通俗的讲，就是求最大不相交子集，也就是尽可能多的在线路不相交的情况下的布线情况。那么，这里再说一下，什么是相交，对于所有上端的接线柱 1<=i<j<=n, 相交即下端接线柱Π(i) > Π(j), 举个例子，比如上端接线柱 1，2, 下端接线柱对应的是 4，5 的话就不相交，对应的是 5，4 的话就相交。

我们直接拿上述这个图为例
记 N(i,j) = {t|(t, Π(t))∈ Nets，t ≤ i, Π(t) ≤ j}。 N(i, j)的最大不相交子集为 MNS(i,j)。 Size(i,j) = |MNS(i,j)|（最大不相交子集线路的条数）
N(i,j): 上端接线柱从 1 到 i，下端接线柱从 1 到 j，在这个范围内的接线情况。也就是 t ∈ (1~i), Π(t) ∈ (1~j)。比如上述图中，如果是 N(4, 6), 那么能够出现的线只有两条，即{4->2, 3->4}，那么 Size(4,6) = 1
当 i = 1 时，$ $MNS(1,j) = \begin{cases}Φ & j < Π(i) \{(1, Π(1))} & j ≥ Π(i)\end{cases}$ $
当 i > 1 时，
j < Π(i)。此时，(i, Π(i)) ∉ N(i,j)。故 N(i,j) = N(i-1,j), Size(i,j) = Size(i-1,j)。为什么是这样？因为 i->Π(i) 就是连接的那条线，既然 j < Π(i), 也就是说 $i 所对应的 Π (i) 并不在集合内$ ，那么显然，N(i,j) = N(i-1,j)
当 j ≥ Π(i), (i,Π(i)) ∈ MNS（即要这根线）(i,j)。对于任意 (t,Π(t)) ∈ MNS(i,j) 有 t < i 且 Π(t) < Π(i)。这种情况下，MNS(i,j) - {(i,Π(i))}是 N(i-1, Π(i)-1) 的最大不相交子集。
若 (i,Π(i)) ∉ N(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)。（此处叙述了这么多，无非就是不要这根线，那么 Size(i,j) = Size(i-1,j)）
综上，我们就得出下面这样一个状态转移方程
当 i = 1 时 $ $S i z e (1, j) = {0 j < Π (i) \1 j \geq Π (i)$ $
当 i > 1 时

S i z e (i, j) = {S i z e (i - 1, j) j < Π (i) max (S i z e (i - 1, j), S i z e (i - 1, Π (i) - 1) + 1) j \geq Π (i)

Java 源代码

/* * 若尘 */package wireset;
import java.util.Arrays;
/** * 动态规划电路布线问题  * @author ruochen * @version 1.0 */
public class WireSet {
  private static int size[][];  private static final int[] C = {0, 9, 7, 4, 2, 5, 1, 9, 3, 10, 6};  private static final int num = 10;
  public static void main(String[] args) {    int NET[] = new int[9];    MNS(C, 10);    Traceback(C, 10, NET);    System.out.println(Arrays.toString(NET));  }    /**   *    * @param C 导线上下接线柱对应的关系   * @param n 导线数量   */  public static void MNS(int[] C, int n) {    int i, j;    size = new int[num + 1][num + 1];        // 判断第一行， i = 1 的情况    for (j = 0; j < C[1]; j++) {      size[1][j] = 0;    }    for (j = C[1]; j <= n; j++) {      size[1][j] = 1;    }        // 2->n 的情况    for (i = 2; i < n; i++) {      for (j = 0; j < C[i]; j++) {        // i > 1 && j < Π(i) 的情况        size[i][j] = size[i-1][j];      }      for (j = C[i]; j <= n; j++) {        size[i][j] = Math.max(size[i-1][j], size[i-1][C[i]-1] + 1);      }    }    size[n][n] = Math.max(size[n-1][n], size[n-1][C[n]-1] + 1);  }    /**   * 获得一个记录可连接导线的数组   * @param C 导线上下两接线柱对应的关系   * @param n 导线数量   * @param NET 记录可连接的导线   */  public static void Traceback(int[] C, int n, int NET[]) {    int i, j = n;    int m = 0;    for (i = n; i > 1; i--) {      if (size[i][j] != size[i-1][j]) {        NET[m++] = i;        j = C[i] - 1;      }      // 第一条线      if (j >= C[1]) {        NET[m++] = 1;      }    }  }
}

复制代码

[1, 9, 1, 1, 7, 5, 3, 0, 0]

复制代码

发布于: 2021 年 06 月 11 日阅读数: 7

原文链接:【http://xie.infoq.cn/article/07c93590bf32462a9c2f3f007】。文章转载请联系作者。

若尘

关注

还未添加个人签名 2021.01.11 加入

还未添加个人简介

发布

暂无评论

创作场景

动态规划电路布线问题（Java 代码实现）

电路布线

问题分析

Java 源代码

若尘

评论