电路布线问题算法
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开始=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, );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 89 10最大不相交连线分别为:1 87 91 89 10最大不相交连线分别为:5 51 87 91 89 10最大不相交连线分别为:3 45 51 87 91 89 10最大不相交连线数目为：:6
