算法设计与分析 5.10 圆排列问题

/***********************************************************
 *                  5.10 圆排列问题
 * 1.问题描述
 * 给定 n 个大小不等的圆 c1, c2, c3, ..., cn, 现在要将这 n 个圆排进
 * 一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从 n 个圆的
 * 所有排列中找出有最小长度的圆排列。
 *
 * 2.算法设计
 * 圆排列问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，设开始
 * 时 a = [r1, r2, ..., rn] 是所给的 n 个圆的半径，则相应的排列树由
 * a[1, .., n] 的所有排列构成。
 *
 * 3.复杂度
 * O(n!)
 */
public class Circles {
 static int n;   //待排列的圆的个数
 static float min;  //当前最优值
 static float[] x;  //当前圆排列圆心横坐标
 static float[] r;  //当前圆排列
 
 public static float circlePerm(int nn, float[] rr) {
  n = nn;
  min = Float.MAX_VALUE;
  x = new float[n];
  r = rr;
  trackback(0);
  return min;
 }

 private static void trackback(int t) {
  if (t == n - 1) {
   compute();
  } else {
   for (int j = t; j < n; j++) {
    swap(r, t, j);
    float centerx = center(t);
    if (centerx + r[t] + r[0] < min) { //下界约束
     x[t] = centerx;
     trackback(t + 1);
    }
    swap(r, t, j);
   }
  }
  
 }

 private static float center(int t) {
  //计算当前所选择圆的圆心横坐标
  float temp = 0;
  for (int j = 1; j < t; j++) {
   float valuex = (float)(x[j] + 2.0 * Math.sqrt(r[t] * r[j]));
   if (valuex > temp) {
    temp = valuex;
   }
  }
  return temp;
 }

 private static void compute() {
  // 计算当前圆排列的长度
  float low = 0;
  float high = 0;
  for (int i = 0; i < n; i++) {
   if (x[i] - r[i] < low)
    low = x[i] - r[i];
   if (x[i] + r[i] > high)
    high = x[i] + r[i];
  }
  if (high - low < min)
   min = high - low;  
 }
 
 private static void swap(float[] array, int i, int j) {
  float temp = array[i];
  array[i] = array[j];
  array[j] = temp;
 }
}