fac5_11.java

java 算法设计与分析的好资料.由王晓东先生主编.

//
//本程序取自王晓东编著“算法分析与设计”第 182 页，例
//电路板排列问题回溯解法
 
    class Board{
     static int n;         //电路板数
     static int m;         //连接块数
     static int[] x;       //当前解
     static int[] bestx;   //当前最优解
     static int[] total;   //total[j]=连接块j的电路板数
     static int[] now;     //now[j]=当前解中所含连接块j的电路板数
     static int bestd;     //当前最优密度
     static int[][] b;     //连接块数组
   public static int arrange(int[][] bb,int mm,int[] xx)
    {
    //初始化
       n=bb.length-1;
       m=mm; 
       x=new int[n+1];
       bestx=xx;
       total=new int[m+1];
       now= new  int[m+1];
       bestd=m+1;
       b=bb;
 //置x为单位排列
      for (int i=1; i<=n; i++)
        {  x[i]= i;
      for (int j=1; j<=m; j++) 
          total[j]+=b[i][j];
        }
 
//回溯搜索
        backtrack(1,0);
        return bestd;
    }
  static void swap(int[] a,int i,int j)
    {
       int temp;
       temp=a[i];
       a[i]=a[j];
       a[j]=temp;
    }
  private static void backtrack(int i,int dd)
    {
     
     if(i==n)
     {
      for(int j=1;j<=n;j++)
        bestx[j]=x[j];    
      bestd=dd;
     }
     else
      for(int j=i;j<=n;j++)
     {//选择x[j]为下一块电路板
       int d=0;
       for(int k=1;k<=m;k++)
        {
         now[k]+=b[x[j]][k];
         if(now[k]>0 && total[k]!=now[k])d++;
        }
  //更新d值
    if(dd>d)d=dd;
   //System.out.println("d="+d+" dd="+dd+"  bestd="+bestd);
    if(d<bestd)
        {//搜索子树
       swap(x,i,j);
       backtrack(i+1,d);
       swap(x,i,j);
        }
        //恢复状态

    for(int k=1;k<=m;k++)
      now[k]-=b[x[j]][k];
     }   
   }
 }
   
  
 
  public class Fac5_11{ 
    public static void main(String args[])
     {
      
       int n1=8;
       int m1=5;
       int nm=0;
       int [][]bt=new int[n1+1][m1+1];
       int []x1=new int[n1+1];
       bt[1][1]=0;bt[1][2]=0;bt[1][3]=1;bt[1][4]=0;bt[1][5]=0;
       bt[2][1]=0;bt[2][2]=1;bt[2][3]=0;bt[2][4]=0;bt[2][5]=0;
       bt[3][1]=0;bt[3][2]=1;bt[3][3]=1;bt[3][4]=1;bt[3][5]=0;
       bt[4][1]=1;bt[4][2]=0;bt[4][3]=0;bt[4][4]=0;bt[4][5]=0;
       bt[5][1]=1;bt[5][2]=0;bt[5][3]=0;bt[5][4]=0;bt[5][5]=0;
       bt[6][1]=1;bt[6][2]=0;bt[6][3]=0;bt[6][4]=1;bt[6][5]=0;
       bt[7][1]=0;bt[7][2]=0;bt[7][3]=0;bt[7][4]=0;bt[7][5]=1;
       bt[8][1]=0;bt[8][2]=0;bt[8][3]=0;bt[8][4]=0;bt[8][5]=1;
       
       Board aa=new Board();
       nm=aa.arrange(bt,m1,x1);
       System.out.println("密度  "+nm);
       System.out.println("电路板最佳排列顺序  ");
       for(int i=1;i<=n1;i++)
       System.out.print("  "+aa.bestx[i]);
       System.out.println("  ");
     }
       
 }