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

小灰灰 2023-02-13 11:03 82阅读 0赞

# 电路布线 #

## 问题分析 ##

--------------------

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

![在这里插入图片描述][20200526190950652.png]

*  我们直接拿上述这个图为例
 *  记 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
    
    1.  当 i = 1时，  
         M N S ( 1 , j ) = \{ Φ j < Π ( i ) ( 1 , Π ( 1 ) ) j ≥ Π ( i ) MNS(1,j) = \\begin\{cases\} Φ & j < Π(i) \\\\ \{(1, Π(1))\} & j ≥ Π(i) \\end\{cases\} MNS(1,j)=\{ Φ(1,Π(1))j<Π(i)j≥Π(i)
    2.  当 i > 1时，
        
        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 ) 并 不 在 集 合 内 \\color\{red\}i所对应的Π(i) 并不在集合内 i所对应的Π(i)并不在集合内，那么显然，N(i,j) = N(i-1,j)
        2.  当 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) 的最大不相交子集。
        3.  若 (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)）
    3.  综上，我们就得出下面这样一个状态转移方程
        
         *  当 i = 1时  
             S i z e ( 1 , j ) = \{ 0 j < Π ( i ) 1 j ≥ Π ( i ) Size(1,j) = \\begin\{cases\} 0 & j < Π(i) \\\\ 1 & j ≥ Π(i) \\end\{cases\} Size(1,j)=\{ 01j<Π(i)j≥Π(i)
         *  当 i > 1时

S i z e ( i , j ) = \{ S i z e ( i − 1 , j ) j < Π ( i ) m a x ( S i z e ( i − 1 , j ) , S i z e ( i − 1 , Π ( i ) − 1 ) + 1 ) j ≥ Π ( i ) Size(i,j) = \\begin\{cases\} Size(i-1, j) & j < Π(i) \\\\ max(Size(i-1, j), Size(i-1, Π(i)-1)+1) & j ≥ Π(i) \\end\{cases\} Size(i,j)=\{ Size(i−1,j)max(Size(i−1,j),Size(i−1,Π(i)−1)\+1)j<Π(i)j≥Π(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]

[20200526190950652.png]: https://img-blog.csdnimg.cn/20200526190950652.png