精华内容
下载资源
问答
  • 动态规划电路布线

    2013-10-04 13:11:34
    动态规划法求解电路布线问题 为确定导线集Nets = {i,π(i),1 ≤ i ≤ n}的最大不想交子集,将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。现分析最优子结构性质。 记N...
  • 动态规划电路布线问题,Java代码实现

    电路布线

    问题分析


    • 电路布线的官方解释我就不加赘述了,通俗的讲,就是求最大不相交子集,也就是尽可能多的在线路不相交的情况下的布线情况。那么,这里再说一下,什么是相交,对于所有上端的接线柱 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
      1. 当 i = 1时,
        MNS(1,j)={Φj<Π(i)(1,Π(1))jΠ(i)MNS(1,j) = \begin{cases} Φ & j < Π(i) \\ {(1, Π(1))} & j ≥ Π(i) \end{cases}
      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) 并不在集合内,那么显然,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时
          Size(1,j)={0j<Π(i)1jΠ(i)Size(1,j) = \begin{cases} 0 & j < Π(i) \\ 1 & j ≥ Π(i) \end{cases}
        • 当 i > 1时

    Size(i,j)={Size(i1,j)j<Π(i)max(Size(i1,j),Size(i1,Π(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}


    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]
    
    展开全文
  • &nbsp;&nbsp;&...根据电路设计,要求用导线(i,π(i)) 将上端接线柱i与下端接线柱π(i)相连,如下图。其中,π(i),1≤ i ≤n,是{1,2,…,n}的一个排列。导线(I, π(i...
    展开全文
  • 算法分析-动态规划电路布线问题

    千次阅读 2019-06-18 21:54:52
    在一块电路板的上、下两端分别有 nnn 个接线柱。根据电路设计,要求用导线 (i,π(i))(i,π(i))(i,π(i)) 将上端接线柱 iii 与下端接线柱 π(i)π(i)π(i) 相连。如下图所示,其中,π(i),1≤i≤nπ(i),1≤ i ≤nπ(i...

    一、问题描述
    \quad \quad在一块电路板的上、下两端分别有 nn 个接线柱。根据电路设计,要求用导线 (i,π(i))(i,π(i)) 将上端接线柱 ii 与下端接线柱 π(i)π(i) 相连。如下图所示,其中,π(i),1inπ(i),1≤ i ≤n, 是{1,2,…,n}的一个排列。导线 (I,π(i))(I, π(i)) 称为该电路板上的第 ii 条连线。对于任何 1ijn1 ≤ i ≤ j ≤n, 第i条连线和第j条连线相交的充要条件是 π(i)&gt;π(j)π(i)&gt; π(j).
    在这里插入图片描述
    πi=87425193106 π(i)={8,7,4,2,5,1,9,3,10,6} \quad \quad在制作电路板时,要求将这 nn 条连线分布到若干绝缘层上。在同一层上的连线不相交。电路布线问题要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线。换句话说,该问题要求确定导线集 Nets=(iπ(i))1in}Nets = {(i,π(i)),1 ≤ i ≤ n \} 的最大不相交子集。
    1)同一层电路布线可以如下
    在这里插入图片描述
    2)同一层电路布线不可能如下
    在这里插入图片描述
    二、最优子结构性质
    \quad \quadN(i,j)={t(t,π(t))Netsti,π(t)j}N(i,j) = \{t|(t,π(t))∈Nets,t \leq i,π(t) \leq j\}N(i,j)N(i,j)的最大不相交子集为 MNS(i,j)MNS(i,j)Size(i,j)=MNS(i,j)Size(i,j) = | MNS(i,j)|

    (1) 当 i=1i = 1,
    MNS(1,j)=N(1,j)={0,j&lt;π(1)1,jπ(1) MNS(1,j)=N(1,j) = \begin{cases} 0 ,j &lt; π(1) \\ 1 ,j \geq π(1) \end{cases}

    (2) 当 i&gt;1i &gt; 1时,
    1)j&lt;π(i)j &lt; π(i) 时,(i,π(i))N(i,j)(i, π(i)) \notin N(i,j),在这种情况下,N(i,j)=N(i1,j)N(i,j) = N(i-1,j), 从而 Size(i,j)=Size(i1,j)Size(i,j) = Size(i-1,j)
    2)jπ(i)j \geq π(i),此时,若 (i,π(i))N(i,j)(i, π(i)) \in N(i,j),则对于任意的 (t,π(t))MNS(i,j)(t, π(t)) \in MNS(i,j),有 t&lt;it&lt;iπ(t)&lt;π(i)π(t)&lt;π(i),否则,(i,π(i))(i, π(i))(t,π(t))(t, π(t)) 相交。在这种情况下 MNS(i,j){(i,π(i))}MNS(i,j)-\{(i,π(i)) \}N(i1,π(i)1)N(i-1,π(i)-1) 的最大不相交子集。

    三、递归计数最优值
    电路布线的最优值 Size(n,n)Size(n,n),由该问题的最优子结构性质可知:
    (1) 当 i=1i = 1,
    Size(1,j)={0,j&lt;π(1)1,jπ(1) Size(1,j) = \begin{cases} 0 ,j &lt; π(1) \\ 1 ,j \geq π(1) \end{cases}
    (2) 当 i&gt;1i &gt; 1 时,
    Size(i,j)={Size(i1,j),j&lt;π(i)max{Size(i1,j),Size(i1,π(i))+1},jπ(i) Size(i,j)=\begin{cases} Size(i-1,j),j &lt; π(i) \\ max\{ Size(i-1,j) , Size(i-1,π(i))+1\},j \geq π(i) \end{cases}
    四、自顶向下计算最优值
    在这里插入图片描述
    在斜角值改变时可以取得所求的子集。即(9,10),(7,9),(5,5)(3,4)

    展开全文
  • #include <iostream> using namespace std; const int N=10; void MNS(int c[],int n,int **size); void Traceback(int c[],int **size,int n,int net[],int &m); int main() { ...i<
    #include <iostream>
    
    using namespace std;
    const int N=10;
    void MNS(int c[],int n,int **size);
    void Traceback(int c[],int **size,int n,int net[],int &m);
    
    int main()
    {
    	int c[]={0,8,7,4,2,5,1,9,3,10,6};
    	int **size=new int*[N+1];
    	for(int i=0;i<=N;i++){
    		size[i]=new int[N+1];
    	}
    	MNS(c,N,size);
    	cout<<"最大不相交连接数目为"<<size[N][N]<<endl;
    	int net[N],m;
    	Traceback(c,size,N,net,m);
    	cout<<"最大不相交连接线分别为:"<<endl;
    	for(int i=m-1;i>=0;i--){
    		cout<<"("<<net[i]<<","<<c[net[i]]<<")";
    		
    	} 
    	cout<<endl;
    	
    }
    
    void MNS(int c[],int n,int **size)
    {
    	for(int j=0;j<c[1];j++)
    		size[1][j]=0;
    	for(int j=c[1];j<=n;j++){
    		size[1][j]=1;	
    	} 
    	for(int i=2;i<n;i++){
    		for(int j=0;j<c[i];j++){
    			size[i][j]=size[i-1][j];
    		}
    		for(int j=c[i];j<=n;j++){
    			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);
    }
    	 
    void Traceback(int c[],int **size,int n,int net[],int &m)
    {
    	int j=n;
    	m=0;
    	for(int 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;
    	}
    }
    
    展开全文
  • 动态规划——电路布线 问题描述 在一块电路板的上、下两端分别有 n 个接线柱。根据电路设计,要求用导线 (i,π(i)) 将上端接线柱 i 与下端接线柱 π(i) 相连。如下图所示,其中,π(i),1≤i≤n, 是{1,2,…,n}的一...
  • 动态规划-电路布线代码(算法分析与设计实验) 用c++语言编写的动态规划算法中电路布线的程序,此程序用于计算每层可布线的最大条数和最优布线方式,可用于多层次的布线,用MFC编写,每层的布线用不同颜色表示出
  • 动态规划——电路布线问题 问题: 在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i))将上端接线柱与下端接线柱相连,其中π(i)是{1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的第...
  • 动态规划电路布线问题

    千次阅读 2018-04-18 17:07:00
    算法笔记——【动态规划电路布线问题 原创 2013年03月14日 09:18:27 标签: 电路布线 / 算法笔记 / 动态规划 / 最优子结构 12785  1、问题描述:  在一块电路板的上、下两端分别有n个接线柱。根据...
  • 问题描述:在一块电路板的上、下2端分别有n个接线柱。根据电路设计,要求用导线(i,π(i))将上端接线柱与下端接线柱...电路布线问题要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线。换句话说,该问题要...
  • 动态规划算法基本思想: 动态规划算法与分治法类似,...电路布线问题描述 : 在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i)) 将上端接线柱i与下端接线柱π(i)相连,如下图。其中,π
  • 通过动态规划的思想解决电路布线问题。 主要分为两个部分:1.求size[i][j]. 2.根据求得的size[i][j]导出最大不相交连线集。
  • 动态规划电路布线

    千次阅读 2019-01-20 18:42:20
     在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i)) 将上端接线柱i与下端接线柱π(i)相连,如下图。其中,π(i),1≤ i ≤n,是{1,2,…,n}的一个排列。导线(I, π(i))称为该电路板上的...
  • 需要ppt讲解 动态规划-dp(电路布线问题)
  • 简单动态规划——电路布线

    千次阅读 2012-07-25 01:33:56
    电路布线 【问题描述】 在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i))将上端接线柱i与下端接线柱π(i)相连,如图所示。 其中,π(i),1 在制作电路板时,要求...
  • public class MNset { public static void mnset(int[] c, int[][] size) { int n = c.length - 1; for (int j = 0; j < c[1]; j++) { size[1][j] = 0; // 下面没有接线柱的时候,都为0 ...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 144
精华内容 57
关键字:

动态规划电路布线