精华内容
下载资源
问答
  • 动态规划算法-求解电路布线问题

    千次阅读 2019-09-04 16:19:24
    1、动态规划算法 动态规划算法(Dynamic Programming,简称DP)通常用于求解具有某种最优性质的问题,其基本思想是将待求解问题...2、电路布线问题 1)问题描述 2)最优子结构性质 记N(i,j) = {t|(t, π(t)) ∈ Ne...

    1、动态规划算法
    动态规划算法(Dynamic Programming,简称DP)通常用于求解具有某种最优性质的问题,其基本思想是将待求解问题分解成若干个子问题,先求解子问题,然后由这些子问题的解再得到原问题的解。
    动态规划是精确求解问题的算法,当问题规模较大时,所需要的时间和内存非常巨大
    2、电路布线问题
    1)问题描述
    在这里插入图片描述
    2)最优子结构性质
    记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)。
    在这里插入图片描述
    3)递推关系
    在这里插入图片描述

    package com.chb.DP;
    
    public class dianlubuxian {
    	int[]c;
    	int[][]size;//最大不相交子集
    	int[]net;
    	
    	public dianlubuxian(int[] c) {
    		super();
    		this.c = c;
    		this.size=new int[c.length][c.length];//下标从1开始
    		this.net=new int[c.length];
    	}
    	
    	public void mnset(int[]c,int[][]size) {
    		int n=c.length-1;
    		//i=1时,分两种情况,分别等于0,1
    		for (int j = 0; j < c[1]; j++) {
    			size[1][j]=0;
    		}
    		for (int j = c[1]; j <=n; j++) {
    			size[1][j]=1;
    		}
    		//i大于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]=Math.max(size[i-1][j], size[i-1][c[i]-1]+1);
    			}
    		}
    		//i=n时单独计算
    		size[n][n]=Math.max(size[n-1][n], size[n-1][c[n-1]-1]+1);
    	}
    	//构造最优解
    	public int traceback(int[]c,int[][]size,int[]net) {
    		int n=c.length-1;
    		int j=n;
    		int 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;
    		}
    		System.out.println("最大不相交连线分别为:");
    		for (int t = m-1; t >=0; t--) {
    			System.out.println(net[t]+" "+c[net[t]]);
    		}
    		return m;
    	}
    	public static void main(String[] args) {
    		int[]c={0,8,7,4,2,5,1,9,3,10,6};//下标从1开始,0不算
    		dianlubuxian d=new dianlubuxian(c);
    		d.mnset(d.c, d.size);
    		int x=d.traceback(d.c, d.size, d.net);
    		System.out.println("最大不相交连线数目为"+x);
    	}
    }
    

    运行结果:
    在这里插入图片描述
    本文装载自
    https://blog.csdn.net/liufeng_king/article/details/8671407
    https://blog.csdn.net/lican19911221/article/details/24454891

    展开全文
  • 电路布线问题的几种动态规划算法

    千次阅读 2017-04-01 09:10:03
    在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i))将上端接线柱i与下端接线柱π(i)相连。 其中,π(i),1<=i<=n是{1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的...
    /*
      Name: 电路布线
      Author:巧若拙 
      Description: 电路布线
    【问题描述】
    在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i))将上端接线柱i与下端接线柱π(i)相连。
    其中,π(i),1<=i<=n是{1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的第i条连线。对于任何1<=i π(j)。
    在制作电路板时,要求将这n条连线分布到若干绝缘层上。在同一层上的连线不相交。
    你的任务是要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线。
    换句话说,就是确定导线集Nets={ i,π(i),1<=i<=n}的最大不相交子集。
    【输入形式】
    输入文件第一行为整数n;第二行为用一个空格隔开的n个整数,表示π(i)。
    【输出形式】
    输出文件第一行为最多的连线数m,第2行到第m+1行输出这m条连线(i,π(i))。
    【输入样例】
    10
    1 8
    2 7
    3 4
    4 2
    5 5
    6 1
    7 9
    8 3
    9 10
    10 6
    【输出样例】
    4
    
    算法1:int MNS(int i, int j);//自顶向下的备忘录算法
    设置一个备忘录数组s[N+1][N+1],s[i][j]表示从上接线柱1-i发出的导线连接到下接线柱1-j,能生成的不相交导线的最大条数。 
    利用原问题的递归关系,使用递归函数来求解。
    状态方程:当i=1时,s[1][j] = (j<c[1]) ? 0 : 1;
    当i>1时,若j<c[i],则s[i][j] = s[i-1][j]; 否则s[i][j] = max(s[i-1][c[i]-1]+1, s[i-1][j]);
    
    算法2:int MNS_2(int n);//自底向上的动态规划算法 
    从i=1开始,依次记录每一个s[i][j],最后获得最优解s[N][N]。
    
    算法3:int MNS_3(int n);//优化的动态规划算法 
    是对算法2的优化,算法2中用到的备忘录数组s[N+1][N+1]占空间较大,实际上下一行数据是利用上一行的数据生成的,
    与更早的数据没有关系,于是可以用两个一维数组pre[N+1]和cur[N+1]代替s[N+1][N+1]。
    
    算法32:int MNS_32(int n);//优化的动态规划算法 
    是对算法3的优化,算法3中用两个一维数组pre[N+1]和cur[N+1]分别表示利用前(i-1)和i个上接线柱所能生成的最好结果,
    仔细观察我们可以发现,cur[j]只与pre[c[i]-1]+1和pre[j]有关,故可以只用一个一维数组F[i]记录结果,
    其中赋值前后的F[i]分别相当于pre[i]和cur[i]。 这样可以减少很多计算。 
    
    最后写了一个函数void Traceback(int n); //输出满足条件的导线 
    该函数需要用到备忘录数组s[N+1][N+1],故只能对算法1和算法2产生的结果有效。 
    
    算法4:与算法2相似,但思路更清晰明了的一种算法。算法的逻辑,与最长公共子序列很相似。 
    设a[i][j]为上端接线柱i与下端接线柱j前的最大不相交子集,则:
    若i与j相连,则a[i][j] = a[i-1][j-1] + 1 
    若i与j不相连,则a[i][j] = max(a[i][j-1], a[i-1][j])
    说明:算法2虽然代码更复杂,但是它做了分类判断,减少了很多不必要的计算,效率更高。  
    
    算法5:对算法4的改进:分阶段讨论,避免不必要的计算。
    与算法2相类似,对下端的接线柱j进行了分段讨论:分成j<c[i], j==c[i]和j>c[i]三个区间,分别求a[i][j]的值,效率更高。 
    
    算法6:int MNS_4(int n);//将问题转化为求最长不下降序列
    注意到电线上端的接线柱已经按顺序排列,问题可以转化为求数组c[N+1]的最长不下降序列 
    */
    #include<iostream>
    #include<string>
    
    using namespace std;
    
    int MNS(int i, int j);//自顶向下的备忘录算法
    int MNS_2(int n);//自底向上的动态规划算法 
    void Traceback_1(int n); //输出满足条件的导线 
    void Traceback_2(int n); //输出满足条件的导线 
    void Traceback_3(int n); //输出满足条件的导线 
    int MNS_3(int n);//优化的动态规划算法 
    int MNS_32(int n);//优化的动态规划算法 
    int MNS_4(int n);//另一种思路的动态规划算法 
    int MNS_5(int n);//对算法4的改进:分阶段讨论,避免不必要的计算 
    int MNS_6(int n);//将问题转化为求最长不下降序列
    
    const int N = 10;
    //int c[N+1] = {0,8,7,4,2,5,1,9,3,10,6};
    int c[N+1] = {0,2,8,1,9,3,5,10,6,7,4};
    int s[N+1][N+1];
    int a[N+1][N+1];
    int b[N+1][N+1];
    int pre[N+1]; //上一行记录
    int cur[N+1]; //当前行记录 
    int F[N+1];//表示从上接线柱1-i发出的导线生成的最好结果 
    int S[N+1]; //记录到元素i为止的最长上升子序列的长度 
    
    int main()
    {  
        cout << MNS(N, N) << endl;
        cout << MNS_2(N) << endl;
        cout << MNS_3(N) << endl;
        cout << MNS_32(N) << endl;
        cout << MNS_4(N) << endl;
        cout << MNS_5(N) << endl;
        cout << MNS_6(N) << endl;
        Traceback_1(N);
        Traceback_2(N);
        Traceback_3(N);
        
        return 0;  
    }  
    
    int MNS(int i, int j)//自顶向下的备忘录算法 
    {
     	if (s[i][j] > 0)
     	   return s[i][j];
     	   
        if (i == 1) //处理第一根导线 
        {
            s[i][j] = (j < c[i]) ? 0 : 1;
        }
        else
        {
    	 	s[i][j] = MNS(i-1, j);
    	 	if (j >= c[i] && MNS(i-1, c[i]-1)+1 > s[i][j])
    	 	   s[i][j] = s[i-1][c[i]-1] + 1; //s[i-1][c[i]-1]在if语句中记录过了 
    	}
    
    	return s[i][j];
    }
    
    int MNS_2(int n)//自底向上的动态规划算法 
    {
     	//先处理第一根导线
     	for (int j=1; j<c[1]; j++)
     		s[1][j] = 0;
        for (int j=c[1]; j<=n; j++)
     		s[1][j] = 1;
     	//然后处理中间的导线	
        for (int i=2; i<n; i++)
        {
    	 	for (int j=1; j<c[i]; j++)
    	 	{
     			s[i][j] = s[i-1][j];
    		}
    		for (int j=c[i]; j<=n; j++)
    		{
     			s[i][j] = (s[i-1][c[i]-1]+1 > s[i-1][j]) ? s[i-1][c[i]-1]+1 : s[i-1][j]; 
    		}
    		
    	}
    	
    	//再处理最后一根导线
    	s[n][n] = (s[n-1][c[n]-1]+1 > s[n-1][n]) ? s[n-1][c[n]-1]+1 : s[n-1][n]; 
    	return s[n][n];
    }
    
    void Traceback_1(int n) //输出满足条件的导线 
    {
        int j = n;
        for (int i=n; i>1; i--)
        {
    	 	if (s[i][j] > s[i-1][j])
    	 	{
    			cout << i << " - " << c[i] << endl;
                j = c[i] - 1;
            }
    	}
    	if (j >= c[1])
    	{
            cout << 1 << " - " << c[1] << endl;
        }
    }
    
    void Traceback_2(int n) //输出满足条件的导线 
    {
        int j = n;
        for (int i=n; i>1; i--)
        {
    	 	if (a[i][j] > a[i-1][j])
    	 	{
    			cout << i << " - " << c[i] << endl;
                j = c[i] - 1;
            }
    	}
    	if (j >= c[1])
    	{
            cout << 1 << " - " << c[1] << endl;
        }
    }
    
    void Traceback_3(int n) //输出满足条件的导线 
    {
        int j = n;
        for (int i=n; i>1; i--)
        {
    	 	if (b[i][j] > b[i-1][j])
    	 	{
    			cout << i << " - " << c[i] << endl;
                j = c[i] - 1;
            }
    	}
    	if (j >= c[1])
    	{
            cout << 1 << " - " << c[1] << endl;
        }
    }
    
    int MNS_3(int n)//优化的动态规划算法 
    {
     	//先处理第一根导线
     	for (int j=1; j<c[1]; j++)
     		pre[j] = 0;
        for (int j=c[1]; j<=n; j++)
     		pre[j] = 1;
     	//然后处理中间的导线	
        for (int i=2; i<n; i++)
        {   //处理当前行cur 
    	 	for (int j=1; j<c[i]; j++)
    	 	{
     			cur[j] = pre[j];
    		}
    		for (int j=c[i]; j<=n; j++)
    		{
     			cur[j] = (pre[c[i]-1]+1 > pre[j]) ? pre[c[i]-1]+1 : pre[j];
    		}
    		//复制当前行信息cur到pre 
    		for (int j=1; j<=n; j++)
    	 	{
     			pre[j] = cur[j];
    		} 
    	} 
    	//再处理最后一根导线
    	cur[n] = (pre[c[n]-1]+1 > pre[n]) ? pre[c[n]-1]+1 : pre[n];
    	return cur[n];
    }
    
    int MNS_32(int n)//优化的动态规划算法,使用一个一维数组来记录结果 
    {
     	//先处理第一根导线(F[i]默认均为0) 
        for (int j=c[1]; j<=n; j++)
     		F[j] = 1;
     	//然后处理中间的导线	
        for (int i=2; i<n; i++)
        {   //处理当前行,赋值前后的F[i]分别相当于pre[i]和cur[i]
    		for (int j=c[i]; j<=n; j++)
    		{
    			if (F[j] < F[c[i]-1]+1)
     				F[j] = F[c[i]-1]+1;
    		}
    	} 
    	//再处理最后一根导线
    	if (F[n] < F[c[n]-1]+1)
     		F[n] = F[c[n]-1]+1;
    	return F[n];
    }
    
    int MNS_4(int n)//另一种思路的动态规划算法,与最长公共子序列很相似 
    {
        for (int i=1; i<=n; i++)
        {
    	 	for (int j=1; j<=n; j++)
    	 	{
    			if (j == c[i])
     				a[i][j] = a[i-1][j-1] + 1;
     			else
     				a[i][j] = max(a[i-1][j], a[i][j-1]);
    		}
    	}
    	
    	return a[n][n];
    }
    
    int MNS_5(int n)//对算法4的改进:分阶段讨论,避免不必要的计算 
    {
        for (int i=1; i<=n; i++)
        {
    		for (int j=1; j<c[i]; j++)//在接线柱c[i]的左侧区域,最优解与不包含接线柱i的一致 
    	 	{
    			b[i][j] = b[i-1][j];
    		}
    		
    		b[i][c[i]] = b[i-1][c[i]-1] + 1;
    		
    	 	for (int j=c[i]+1; j<=n; j++)//在接线柱c[i]的右侧区域,最优解可能包含接线柱i,也可能不包含i 
    	 	{
    			b[i][j] = max(b[i-1][j], b[i][j-1]);
    		}
    	}
    	
    	return a[n][n];
    }
    
    int MNS_6(int n)//将问题转化为求最长不下降序列
    {
    	S[1] = 1; //默认到元素i为止的最长上升子序列的长度为1 
    	for (int i=2; i<=n; i++)
    	{
    		int m = 0;
    		for (int j=i-1; j>0; j--)//逆序查找不大于A[i],且最长的元素
    		{
    			if (c[i] > c[j] && S[j] > m)
    			{
    				m = S[j];
    			}
    		}
    		S[i] = m + 1;
    	}
    	int len = S[n]; 
    	for (int i=n-1; i>0; i--)
    	{
    		if (S[i] > len)
    		{
    			len = S[i];
    		}
    	}
    	
    	return len;
    }

    展开全文
  • 算法设计——电路布线问题动态规划

    千次阅读 多人点赞 2020-04-15 17:07:52
    问题 在一块电路板的上、下2端分别有n个接线柱。根据电路设计,要求用导 线(i,π(i))将上端接线柱与下端接线柱相连,如图所示。... 电路布线问题要确定将哪些连线安排在第一层上,使得该层上有尽可能 多的连...

    问题

    在一块电路板的上、下2端分别有n个接线柱。根据电路设计,要求用导 线(i,π(i))将上端接线柱与下端接线柱相连,如图所示。其中π(i)是 {1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的第i条连线。对于任 何1≤i<j≤n,第i条连线和第j条连线相交的充分且必要的条件是π(i)>π(j)。 电路布线问题要确定将哪些连线安排在第一层上,使得该层上有尽可能 多的连线。换句话说,该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最 大不相交子集。
    在这里插入图片描述

    分析

    刚开始我不理解最大不相交子集的意思
    其实就是求这些布线中最多选几条线使其不相交
    我们可用一个二维数组储存上端点到下端点的最大不相交子集
    如dp[7][5]代表从上端点7到下端点5这条线左边有几条不相交线路
    a[i]表示上端点i对应的下端点坐标
    我们可以知道
    上端点为1时,dp[1][j],当j<a[1](上端点1对应的下端点a[1])时,dp[1][j]=0,当j>=a[1]时,dp[1][j]=1
    在这里插入图片描述
    上端点i大于1时
    若j小于a[i]时,因为不包括i到a[i]这条线,就是说删除i点对结果没有影响,所以就有dp[i][j]=dp[i-1][j],而dp[i-1]的所有值已算出
    在这里插入图片描述

    若j大于等于a[i],说明包括了i到a[i]这条线,此时需要比较dp[i-1][a[i]-1]+1与dp[i-1][j]的关系,dp[i][j]=max{dp[i-1][a[i]-1]+1,dp[i-1][j]}

    为什么是比较dp[i-1][a[i]-1]+1,dp[i-1][j]呢?
    当i与a[i]这条线与已知的最大不相交子集中的其他线路都不相交时,那么此时去掉此条线路的集合就等于dp[i-1][a[i]-1],所以dp[i][j]=dp[i-1][a[i]]-1]+1
    在这里插入图片描述
    当i与a[i]这条线与已知的最大不相交子集中的其他线路相交时,那么此时将上端点左移一个点不影响,所以dp[i][j]=dp[i-1][j]
    在这里插入图片描述
    所以我们可以直接比较得到dp[i][j]的最大值并保存。

    代码并不复杂,难在理解

    代码实现

    #include<stdio.h>
    #include<string.h>
    #define N 100
    int main()
    {
    	int i,j,n;
    	int a[N],dp[N][N];
    	printf("请输入端点个数:");
    	scanf("%d",&n);
    	printf("请输入各端点对应的下端点:");
    	for(i=1;i<=n;i++){
    		scanf("%d",&a[i]);
    	} 
    	for(i=1;i<=n;i++){//上端点为1的情况 
    		if(i<a[1]) dp[1][i]=0;
    		else dp[1][i]=1;
    	}
    	for(i=2;i<=n;i++){//其他情况 
    		for(j=1;j<=n;j++){
    			if(j<a[i]){//小于対应线的坐标 
    				dp[i][j]=dp[i-1][j];
    			}else{//大于等于 
    				if(dp[i-1][j]>dp[i-1][a[i]-1]+1){//更新dp最大值 
    					dp[i][j]=dp[i-1][j];
    				}else
    					dp[i][j]=dp[i-1][a[i]-1]+1;
    			}
    		}
    	}
    	printf("%d\n",dp[n][n]);
    	return 0;
     } 
    
    展开全文
  • 电路布线问题算法

    2014-01-05 14:15:36
    本文档详细叙述了电路布线问题的各种算法,包括动态规划 最长递增子序列算法 分支限界算法 DNA算法
  • 算法分析-动态规划电路布线问题

    千次阅读 2019-06-18 21:54:52
    一、问题描述 在一块电路板的上、下两端分别有 nnn 个接线柱。根据电路设计,要求用导线 (i,π(i))(i,π(i))(i,π(i)) 将上端接线柱 iii 与下端接线柱 π(i)π(i)π(i) 相连。如下图所示,其中,π(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)

    展开全文
  • 电路布线算法的java实现 具体问题描述以及
  • 动态规划电路布线问题

    千次阅读 2018-04-18 17:07:00
    算法笔记——【动态规划电路布线问题 原创 2013年03月14日 09:18:27 标签: 电路布线 / 算法笔记 / 动态规划 / 最优子结构 12785  1、问题描述:  在一块电路板的上、下两端分别有n个接线柱。根据...
  • 个人觉得比较好的动态规划算法PPT,与王晓东老师教材匹配,包括矩阵连乘问题、电路布线问题、0-1背包问题等都有详解。
  • 动态规划算法基本思想: 动态规划算法与分治法类似,...电路布线问题描述 : 在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i)) 将上端接线柱i与下端接线柱π(i)相连,如下图。其中,π
  • 1、问题描述:  在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i)) 将上端接线柱i与下端接线柱π(i)相连,如下图。其中,π(i),1≤ i ≤n,是{1,2,…,n}的一个排列。导线(I, π(i))...
  • 提出了一种推广的电路布线问题,对此问题分别设计了基于动态规划和偏序关系的算法,并分析了其算法的复杂性。
  • 电路布线问题就是要确定怎样在第一层中尽可能多地布设导线, 即确定导线集Nets={(i,π(i)),1≤i≤n} 的最大不相交子集。 记N(i,j)={t|(t,π(t))∈Nets, t≤i, π(t)≤j}, N(i, j)的最大不相交子集为MNS(i, j), ...

空空如也

空空如也

1 2 3 4
收藏数 80
精华内容 32
关键字:

电路布线问题动态规划算法