精华内容
下载资源
问答
  • 电路布线问题

    千次阅读 2017-01-01 20:31:39
    电路布线问题  制作电路板时,将n条连线分布到若干绝缘层上。在同一层的连线不相交。电路布线问题就是要确定将哪些连线安排到第一层上,使该层上有尽可能多的连线。  输入一个整数n代表接线柱的数量,输入n个...

    电路布线问题

       制作电路板时,将n条连线分布到若干绝缘层上。在同一层的连线不相交。电路布线问题就是要确定将哪些连线安排到第一层上,使该层上有尽可能多的连线。

      输入一个整数n代表接线柱的数量,输入n个数代表与上接线柱连接的下接线柱编号

    样例输入

    10
    8 7 4 2 5 1 9 3 10 6

    样例输出

    4

    解:

    例如,给定如图的电路板。从10条连线中,选取不相交的最大连线集合。用a(i)=j表示要求上排的第i个接线柱要求接到下排的第 j 个接线柱。

      在图中,a(1)=8 , a(2)=7, a(1)=4, a(1)=2, a(1)=5, a(1)=1, a(1)=9, a(1)=3, a(1)=10, a(1)=6。


      如果使得(i , a[i])与(j , a[j])不相交,假设 j>I 则两条线不相交的充分必要条件为 a[j]>a[i]。在制作电路板时,要求将这n条连线分布到若干绝缘层上。在同一层上的连线不相交。电路布线问题要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线。换句话说,该问题要求确定所有导线集的最大不相交子集。

      记N(i,j){(t,a(t)) |  t<=i,a(t)<=j }代表上接线柱小于等于i并且下接线柱小于等于j的连线的集合。N(i,j)的最大不相交子集为MNS(i,j),假设MNS(i,j)中的连线数目为dp[i][j];
    下面对MNS(i,j)进行判断区分:


    (1) 当i = 1时

    ①如果j>=a[i],为了考虑更多的连线,则(i,a[i])应当在集合MNS(i,j) 中,即dp(i,j)=1;

    ②如果j<a[i],此时则(i,a[i])不应放在集合MNS(i,j) 中,即dp(i,j)=0


    (2)当i >1时

    j<ai)。

    此时,(iai))不属于MNSij)。故在这时,MNSij =MNSi-1j),从而dpij=dpi-1j)。

    j >=a(i)

      若(i, a(i))MNS(i,j),则对任意(t, a(t))MNS(i,j)t <ia(t)<a(i);否则,(t,a(t))(i,a(i))相交。在这种情况下MNS(i,j)-{(i,a(i))}N(i-1,a(i)-1)的最大不相交子集。否则,子集MNS(i-1,a(i)-1){(i,a(i))}包含于N(i,j)是比MNS(i,j)更大的N(i,j)的不相交子集。这与MNS(i,j)的定义相矛盾。

      (i, a(i))不属于MNS(i,j),则对任意(t, a(t))MNS(i,j),有t<i。从而MNS(i,j)包含于N(i-1,j),因此,dp(i,j)≤dp(i-1,j)另一方面,MNS(i-1,j)包含于N(i,j),故又有dp(i,j)≥dp(i-1,j),从而Sizei,j=Size(i-1,j)

    ia[i])属于MNS(i,j),则dp(i,j)=dp(i-1,a[i])+1;


    ia[i])不属于MNS(i,j),则dp(i,j)=dp(i-1,j);



    所以递推公式:

    1)当i=1时

    (2)当i>1时

    #include <stdio.h>
    #include <string.h>
    
    #define MAX(a, b) ((a)>(b)?(a):(b)) 
    
    int main()
    {
    	int n;
    	int a[100],dp[100][100];
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",&a[i]);
    	} 
    	memset(dp,0,sizeof(dp));
    	for(int j=1;j<=n;j++) 
    	{
    		if(j<a[1])
    			dp[1][j]=0;
    		else
    			dp[1][j]=1;
    	}
    	for(int i=2;i<=n;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    			if(j<a[i])
    				dp[i][j]=dp[i-1][j];
    			else
    				dp[i][j]=MAX(dp[i-1][j],dp[i-1][a[i]-1]+1);
    		}
    	}
    	
    	printf("%d\n",dp[n][n]);
    	return 0; 
    } 


    展开全文
  • 通过动态规划的思想解决电路布线问题。 主要分为两个部分:1.求size[i][j]. 2.根据求得的size[i][j]导出最大不相交连线集。
  • 算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题
  • 电路布线问题算法

    2019-12-04 22:28:40
    电路布线问题算法 public class Dianlu { public int[] c; public int[][] size; public int[] net; public Dianlu(int[] b){ this.c=b; this.size=new int[b.length][b.length]; //下标从1开始 this.net=...

    电路布线问题算法

    public class Dianlu {
    	public int[] c;
    	public int[][] size;
    	public int[] net;
    	public Dianlu(int[] b){
    		this.c=b;
    		this.size=new int[b.length][b.length];
    //下标从1开始
    		this.net=new int[b.length];
    	}
    	public static void main(String[] args) {
    		int[] c = {0,8,7,4,2,5,1,9,3,10,6};
    //下标从1开始,第一个数,0不算,总共10个数
    	Dianlu d = new Dianlu(c);
    	mnset(d.c, d.size);
    	int x = traceback(d.c, d.size, d.net);
    	System.out.println("最大不相交连线数目为::"+x);
    	}
    			//递归计算最优值
    	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;
    		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++)//j<π(i)的情况
    				size[i][j]=size[i-1][j];
    			for(int j=c[i];j<=n;j++)//j>=π(i)的情况
    	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);
    	}
    	//构造最优解
    	public static 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]){     //此时(i,c[i])是最大不相交子集
    				net[m++]=i;
    				j=c[i]-1;   //更新扩展连线柱区间
    				if(j>=c[1])
    					net[m++]=1;    //处理i=1的情形
    				System.out.println("最大不相交连线分别为:");
    				for(int t=m-1;t>=0;t--){
    					System.out.println(net[t]+"  "+c[net[t]]);
    				}
    			}
    		return m;
    	}
    
    }
    

    执行结果

    最大不相交连线分别为:
    1  8
    9  10
    最大不相交连线分别为:
    1  8
    7  9
    1  8
    9  10
    最大不相交连线分别为:
    5  5
    1  8
    7  9
    1  8
    9  10
    最大不相交连线分别为:
    3  4
    5  5
    1  8
    7  9
    1  8
    9  10
    最大不相交连线数目为::6
    
    展开全文
  • 电路布线问题的算法

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

    2020-06-26 21:35:39
    7、实验六电路布线问题 实验内容 内容:在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,a(i))将上端接线柱与下端接线柱相连,其中a(i)表示上端点i对应的下端点的值,如图所示。 ...

    7、实验六电路布线问题

    实验内容

    内容:在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,a(i))将上端接线柱与下端接线柱相连,其中a(i)表示上端点i对应的下端点的值,如图所示。
    在这里插入图片描述
    题目要求是在给定的连线中,选取不相交连线的最大子集,即不相交连线的最大数目。并把最大不相交子集的情况给列举处理

    解题思路

    在制作电路板时,要求将这n条连线分布到若干绝缘层上。在同一层上的连线不相交。电路布线问题要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线。换句话说,该问题要求确定导线集Nets = {i,π(i),1 ≤ i ≤ n}的最大不相交子集。
    在这里插入图片描述

    源代码

    package f电路布线问题;
    
    import java.util.Scanner;
    
    public class CircuitWiring {
    
    	public static void main(String[] args) {
    
    		Scanner scanner = new Scanner(System.in);
    		System.out.println("输入一共有几个接线柱:");
    		int i = scanner.nextInt();
    		// 定义数组jxz
    		int[] jxz = new int[i + 1];
    		System.out.println("依次输入这" + i + "个接线柱的下端接线柱号:");
    		String all = scanner.next();
    		// 对字符串进行操作
    		String[] str = all.split(",");
    		// 给数组c赋值
    		jxz[0] = 0;// 给数组c的第一个赋值为0
    		int q = 0;// 定义str数组的循环开始
    		for (int a = 1; a < i; a++) {
    			jxz[a] = Integer.parseInt(str[q]);
    			q++;
    		}
    		jxz[i] = Integer.parseInt(str[i - 1]);// 给数组c的最后一位赋值
    		// 显示数组c
    //		for(int b=0;b<c.length;b++) {
    //			System.out.print(c[b]+" ");
    //		}
    
    		CircuitWiring cW = new CircuitWiring(jxz);
    		cW.getER(cW.jxz, cW.ER);
    		int x = cW.shortPath(cW.jxz, cW.ER, cW.route);
    		System.out.println("最大不相交连的线数目为:" + x);
    	}
    
    	public int[] jxz;// 接线柱数组
    	public int[][] ER;// 最大不相交子集
    	public int[] route;// 最短路径
    
    	/**
    	 * 	构造方法,进行初始化
    	 * 
    	 * @param jxz 接线柱数组
    	 */
    	public CircuitWiring(int[] jxz) {
    		this.jxz = jxz;
    		this.ER = new int[jxz.length][jxz.length];// 下标从1开始
    		this.route = new int[jxz.length];
    	}
    
    	/**
    	 * @see 输出最大不相交子集的二维数组
    	 * @param jxz 接线柱数组
    	 * @param ER  输入原始的二维数组
    	 */
    	public void getER(int[] jxz, int[][] ER) {
    		int n = jxz.length - 1;
    		for (int j = 0; j < jxz[1]; j++) {// i=1时,分了两种情况,分别等于0,1
    			ER[1][j] = 0;
    		}
    		for (int j = jxz[1]; j <= n; j++) {
    			ER[1][j] = 1;
    		}
    		for (int i = 2; i <= n; i++) {// i大于1时,同样分了两种情况(当i=n时单独计算,即此方法最后一行)
    			for (int j = 0; j < jxz[i]; j++) {// 第一种
    				ER[i][j] = ER[i - 1][j];
    			}
    			for (int j = jxz[i]; j <= n; j++) {// 第二种
    				ER[i][j] = Math.max(ER[i - 1][j], ER[i - 1][jxz[i] - 1] + 1);
    			}
    		}
    		ER[n][n] = Math.max(ER[n - 1][n], ER[n - 1][jxz[n] - 1] + 1);
    
    		System.out.println();
    		// 输出电路布线问题的矩阵
    		for (int i = 1; i <= n; i++) {
    			for (int j = 0; j <= n; j++) {
    				System.out.print(ER[i][j] + " ");
    			}
    			System.out.println();
    		}
    		System.out.println();
    
    	}
    
    	/**
    	 * @see 构造最优解
    	 * @param jxz   接线柱数组
    	 * @param ER    不相交连线的最大数目【二维数组】
    	 * @param route 最短路径
    	 * @return 最大不相交连的线数目
    	 */
    	public int shortPath(int[] jxz, int[][] ER, int[] route) {
    		int n = jxz.length - 1;
    		int j = n;
    		int m = 0;
    		for (int i = n; i > 1; i--) {
    			if (ER[i][j] != ER[i - 1][j]) {
    				route[m++] = i;
    				j = jxz[i] - 1;
    			}
    
    		}
    		if (j >= jxz[1])
    			route[m++] = 1;
    		System.out.println("最大不相交连线为:");
    		int num = 0;
    		for (int t = m - 1; t >= 0; t--) {
    			System.out.print("【" + route[t] + "," + jxz[route[t]] + "】");
    			num++;
    			if (num <= m - 1) {
    				System.out.print(",");
    			}
    
    		}
    		System.out.println();
    		return m;
    	}
    
    }
    

    运行截图

    在这里插入图片描述

    展开全文
  • 电路布线问题要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线。换句话说,该问题要求确定导线集Nets = {i,π(i),1 ≤ i ≤ n}的最大不相交子集。 2、最优子结构性质: 记N(i,j) = {t|(t, π(t)) ...
  • C++程序 电路布线问题

    2011-05-22 17:29:20
    本文详细介绍了 电路布线问题的详细方法,有详细的源程序代码
  • 动态规划——电路布线问题 问题: 在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i))将上端接线柱与下端接线柱相连,其中π(i)是{1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的第...

    动态规划——电路布线问题

    问题:

    在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i))将上端接线柱与下端接线柱相连,其中π(i)是{1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的第i条连线。对于任何1≤i<j≤n,第i条连线和第j条连线相交的充分且必要的条件是π(i)>π(j)。

    电路布线问题要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线。换句话说,该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。

    分析:

    该问题和最长公共子序列问题属于同一类问题,同样需要关注序列的末端,不同的是由于本题的序列元素间已经存在了某种映射关系,所以在递推时跨的步长更大。

    ——最优子结构:设s[i][j]为序列[1,i],[1,j]的最大不相交子集,那么若i对应的接线柱π(i)>j,说明接线柱i已经不可能再被选中了,那么s[i][j]=s[i-1][j];若i对应的接线柱π(i)<=j,说明接线柱i可能被选中,那么就有两种情况,选与不选,假如选了,那i就去掉,同时π(i)以及序号大于它的接线柱也不可能被选中了,因为假如被选了,那就有相交了,所以s[i][j]=s[i-1][π(i)-1]+1,假如不选,那就是s[i][j]=s[i-1][j],子结构满足最优子结构性质。

    ——确定递推关系:s[i][j]=s[i-1][j],π(i)>j;s[i][j]=max(s[i-1][π(i)-1]+1,s[i-1][j]),π(i)<=j。

    ——计算最优值:初始化最小子问题,第1行的所有值可计算。按照行逐行求解,每一个元素取决于其上一行的某一个元素。

    ——确定最优解:开辟一个二维数组b,记录s的每个状态对应的最优选择,然后重走革命路。

    代码:

    #include <bits/stdc++.h>
    
    using namespace std;
    
    #define MAXN 105
    
    // 求最优值,即各个子问题最大不相交子集的大小
    // 输入:序列pi,子问题最优值记录矩阵s,最优解记录矩阵b,pi长度n
    void MNS(int pi[],int s[][MAXN],int b[][MAXN],int n){
        // 初始化最小子问题
        for(int i = 1;i <= n;i++){
            if(pi[0]<=i){
                s[1][i] = 1;
                b[1][i] = 2;
            }
            else{
                s[1][i] = 0;
                b[1][i] = 1;
            }
        }
        // 根据递推公式计算解空间
        for(int i = 2;i <= n;i++){
            for(int j = 1;j <= n;j++){
                if(pi[i-1] > j){
                    s[i][j] = s[i-1][j];
                    b[i][j] = 1;
                }else{// 没选
                    if(s[i-1][j] > s[i-1][pi[i-1]-1]+1){
                        s[i][j] = s[i-1][j];
                        b[i][j] = 1;
                    }else{// 选了
                        s[i][j] = s[i-1][pi[i-1]-1]+1;
                        b[i][j] = 2;
                    }
                    
                }
            }
        }
    }
    
    // 根据记录矩阵b还原最优解
    void traceback(int b[][MAXN],int pi[],int i,int j){
        if(i==0 || j==0){// 这里一定要到最小子问题也处理完才返回
            return;
        }
        if(b[i][j] == 1){// 行为1,没选这个下层接线柱
            traceback(b, pi, i-1, j);
        }
        if(b[i][j] == 2){// 行为2,选这个下层接线柱
            traceback(b, pi, i-1, pi[i-1]-1);
            cout<<i<<" "<<pi[i-1]<<endl;
        }
    }
    
    int main(){
        int pi[8] = {1,4,2,3,6,8,5,7};
        int s[MAXN][MAXN];
        int b[MAXN][MAXN];
        MNS(pi, s, b, 8);
        cout<<s[8][8]<<endl;
        traceback(b, pi, 8, 8);
    }
    

    时间复杂度和空间复杂度都是O(n2)

    展开全文
  • 问题描述:在一块电路板的上、下2端分别有n个接线柱。根据电路设计,要求用导线(i,π(i))将上端接线柱与下端接线柱...电路布线问题要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线。换句话说,该问题要...
  • 动态规划电路布线问题,Java代码实现
  • 电路布线问题(分支限界法)

    千次阅读 2020-05-25 11:29:08
    精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。 在布线时,电路只能沿直线或直角布线。 为了避免线路相交,已布了线的方格做了封锁标记,其他线路不允许穿过被封锁的方格。 二.算法...
  • 在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线将上端接线柱与下端接线柱相连, 如上图所示,每个节点有且只连有一条线。在制作电路板时,要求将这n条连线分布到若干绝缘层上。在同一层上的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,084
精华内容 433
关键字:

电路布线问题