用回溯法解决圆排列问题

article/2025/9/20 20:10:35

教材是用的王晓东的《计算机算法设计与实现》第四版，c++版

一下是问题描述：

算法实现:

/**
*能确定一个正确的想法（即每种情况都能考虑到，然后找一个最简单而准确的方式表达出来）
*
**/ #include<iostream>//此问题没有要求相邻的圆必须相切

#include<math.h>
using namespace std;
class Circle{
friend float CirclePerm(int,float*);//找到最优排列
private:
  float Center(int t);//计算横坐标
  void Compute();//计算当前圆排列的长度
  void Backtrack(int t);
  float min,//最优值
  *x,//当前圆排列圆心横坐标
  *r; //当前元的半径
  int n;//当前待排园的个数

};
template <class T>
void Swap(T a,T b)
{
T temp;
temp = a;
a = b;
b = temp;
}
//此问题没有要求相邻的圆必须相切 ——对于计算横坐标，肯定选最大值
float Circle::Center(int t)//t代表当前选的第t个圆
{
//计算当前所选园的圆心横坐标
float temp = 0.0;//第一个圆默认为0
//j表示第t个圆之前的圆，
//x[j]这个数组第零个元素无用
for(int j=1;j<t;j++)//为什么每次都从第一个圆开始比 ——找最大值，防止前一个与之相切的圆特别小（不是，见下）
{
  float valuex = x[j]+2*sqrt(r[t]*r[j]);//疑问① 考虑特殊情况 (如果特大圆放在第二个位置，圆心距与横坐标并没有错）——核心问题不是这个，这个两个之间也是相切的
  //另一种特殊情况是第二个圆特别小而第三个圆很大，导致一三相切二三不想切，这就是for循环的原因
  //疑问二不考虑特殊情况，为什么要加x[j]? —懂了，画图就明白了，x[j]是之前圆的横坐标
  if(valuex>temp)temp = valuex;
}
return temp;
}
//负轴取绝对值最大，正轴取最大 ,n、

void Circle::Compute(void){//计算当前圆排列的长度，我的想法——（1--j）上所有圆的横坐标加上这个的圆心距取最小值（若最后一个圆特别小，这个公式根本不成立）；课本上的想法——（负轴取绝对值最大，正轴取最大）
float low = 0,
    high= 0;
    for(int i = 1;i<=n;i++)//n始终是不变的
    {
    if(x[i]-r[i]<low)low = x[i]-r[i];//为什么要积累low——也和特殊情况有关吗？             //这个算的就是第一个的半径吧，到底为什么要积累 ——不对，算的是负值的部分，若第一个特别小，第二个很大，则取最大值
    if(x[i]+r[i]>high)high = x[i]+r[i];//这个肯定要去最大值，若最后一个圆特别小，与边框根本不相切，算出来的值则不对
    }
    if(high-low<min)min = high-low;
}
void Circle::Backtrack(int t){
if(t>n)Compute();
else
{
  for(int j=t;j<=n;j++)
  {
   Swap(r[t],r[j]);
   float centerx = Center(t);
   if(centerx+r[t]+r[1]<min){//下界约束
   x[t] = centerx;
   Backtrack(t+1);
   }
   Swap(r[t],r[j]);
  }
}
}
float CirclePerm(int n,float*a)
{
Circle X;
X.n= n;
X.r= a;
X.min = 1000000;
float*x = new float[n+1];
X.x = x;
X.Backtrack(1);
delete[] x;
return X.min;
}
int main()
{
int n;
float*a = new float[n+1];
cin>>n;
for(int i=1;i<=n;i++)
{
  cin>>a[i];
}
cout<<CirclePerm(n,a)<<endl;
return 0;
}