/***********************************************************
* 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;
}
}
联系客服