回溯算法 --- 例题9.圆排列问题

时间：2021-12-21 作者：pgokc13

一.问题描述

给定n个大小不等的圆c1,c2,…,cn, 现要将这n个圆排进一个矩形框中, 且要求各圆与矩形框的底边相切。
圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。
例如, 当n=3, 且所给的3个圆的半径分别为1, 1, 2时, 这3个圆的最小长度的圆排列如图所示。其最小长度为2+4√2 .

二.解题思路

圆排列问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架, 设开始时a=[r1,r2,……rn]是所给的n个圆的半径, 则相应的排列树由a[1:n]的所有排列构成。

解圆排列问题的回溯算法中, CirclePerm(n,a)返回找到的最小的圆排列长度。初始时, 数组a是输入的n个圆的半径, 计算结束后返回相应于最优解的圆排列。
Center函数计算圆在当前圆排列中的横坐标, 由x^2 = sqrt((r1+r2)^2-(r1-r2)2)推导出x = 2*sqrt(r1*r2)。
Compoute计算当前圆排列的长度。变量min记录当前最小圆排列长度。数组r表示当前圆排列。数组x则记录当前圆排列中各圆的圆心横坐标。数组ID记录当前圆排列的编号

在递归算法Backtrack中:
当i>n时, 算法搜索至叶节点, 得到新的圆排列方案。此时算法调用Compute计算当前圆排列的长度, 适时更新当前最优值.
当i<n时, 当前扩展节点位于排列树的i-1层。此时算法选择下一个要排列的圆, 并计算相应的下界函数。

代码如下:

// 圆排列问题
#include<bits/stdc++.h>
using namespace std;
class Circle
{
    friend float CirclePerm(int, float *);
    private:
        float Center(int t);    //计算圆心所在位置
        void Compute();         //计算当前圆排列的长度
        void Backtrack(int i);
        float min,      //当前最优值
              *x,       //当前圆排列圆心横坐标
              *r;       //当前圆排列
        int n;          //待排列圆的个数
        int *ID;        //初始圆数组的编号
};
float Circle::Center(int i)     //计算当前所选择圆的圆心横坐标(1~i-1层每一个圆都要计算,找出一个最大的横坐标,与之相切,具体情况可以参考之后的图)
{
    float temp = 0;
    for(int j=1; j<i; j++)  //注意!!! i==1时,也就是选择第一个圆时,得到的x[1] = 0
    {
        float valuex = x[j] + 2.0*sqrt(r[i]*r[j]);
        if(valuex > temp)   temp = valuex;
    }
    return temp;
}
void Circle::Compute()      //计算当前圆排列的长度
{
    float low = 0, high = 0;
    for(int i=1; i<=n; i++)
    {
        if(x[i]-r[i] < low)     //找出一个最左的坐标(x[i]表示圆心横坐标,r[i]表示圆的半径)
            low = x[i] - r[i];
        if(x[i]+r[i] > high)    //找出一个最右的坐标
            high = x[i] + r[i];
    }
    if(high-low < min) min = high - low;  //如果找到更优解,那么更新它
}
void Circle::Backtrack(int i)
{
    static int k = 1;
    if(i > n)
    {
        Compute();
        cout<<"到达第"<<n+1<<"层,得到第"<<k++<<"个可行解:";
        for(int i=1; i<=n; i++) cout<<r[i]<<" ";
        cout<<endl<<"所得最小圆排列值为:"<<min<<endl;
        cout<<"圆排列的编号数组为:";
        for(int i=1; i<=n; i++) cout<<ID[i]<<" ";
        cout<<endl;
    }
    else
    {
        for(int j=i; j<=n; j++)
        {
            swap(r[i], r[j]);
            swap(ID[i], ID[j]);
            float centerx = Center(i);
            cout<<"当前第"<<i<<"层"<<",选择圆的编号为:"<<ID[i]<<",计算得到圆心横坐标centerx:"<<centerx<<" r[i]:"<<r[i]<<" r[1]:"<<r[1]<<" 总和为:"<<centerx+r[i]+r[1]<<"  当前min值为:"<<min<<endl;
            if(centerx + r[i] + r[1] < min) //下界约束(centerx+r[i]+r[1]这个值比实际值还要小,因为centerx+r[i]
            {
                cout<<"满足剪枝函数,递归深入一层,将到达第"<<i+1<<"层"<<endl;
                x[i] = centerx;
                Backtrack(i+1);
                cout<<"当前第"<<i+1<<"层,递归回退一层,将到达第"<<i<<"层"<<endl;
            }
            else cout<<"不满足剪枝函数,对应子树被剪枝"<<endl;
            swap(r[i], r[j]);
            swap(ID[i], ID[j]);
            if(j==n) cout<<"当前层所有情况遍历完,回退"<<endl;
        }
    }
}
float CirclePerm(int n, float *r)
{
    Circle X;
    X.n = n;
    X.r = r;
    域名 = 100000;
    float *x = new float[n+1];
    X.x = x;
    int *ID = new int[n+1];
    for(int i=1; i<=n; i++) ID[i] = i;
    域名 = ID;
    域名track(1);
    delete[] x;
    delete[] ID;
    return 域名;
}
int main()
{
    cout<<"请输入圆的个数:";
    int n;
    while(cin>>n && n)
    {
        cout<<"请输入每个圆的半径:"<<endl;
        float *r = new float[n+1];
        for(int i=1; i<=n; i++) cin>>r[i];
        float ans = CirclePerm(n, r);
        cout<<"最小圆排列长度为:"<<ans<<endl;
        delete[] r;
        cout<<"请输入圆的个数:";
    }
    system("pause");
    return 0;
}

下面做几个解释:

Center函数.
Center计算圆在当前圆排列中的横坐标，由x^2 = sqrt((r1+r2)^2-(r1-r2)2)推导出x = 2*sqrt(r1 * r2)，但是为什么我们要用一个for循环遍历1到i-1个已经确立好的圆呢?
这是因为我们很容易会有一个先入为主的思想，那就是后一个圆必然与排在它前一个位置的圆相切，其实排在任意位置的圆与其前或后的任意一个圆都有可能相切的，画个图就很清晰了。

在这个图中,可以看到,只要大小合适，目标圆就有可能与排列中的任意一个圆相切,不一定就是和前一个相切.所以我们需要遍历之前已经确定好的i-1个圆,找出计算后最大的横坐标,来作为下一个圆圆心的横坐标.
如果不这样做的话会发生什么呢?很明显,这样的话就不满足题目条件了,试想一下如果我们上面的x3这个圆和x2相切了,那么势必x3会与x1这个圆出现相交!
剪枝函数if(centerx + r[i] + r[1] < min)
这个问题,我想这个条件其实想了好一会.
我认为centerx + r[i] + r[1]这个式子的值是要比真实的圆排列长度要小的,通过计算圆排列长度的函数Compute()我们知道,我们是需要找到一个最左的坐标以及一个最右的坐标,二者相减从而得到我们需要的长度.
用式子表述就是: min = x[k]+r[k] - (x[m]-r[m]) = x[k]+r[k] + r[m]-x[m] , (其中的k和m分别使得一个坐标最大,一个坐标最小)

这里的centerx并不一定是最右的坐标,所以说centerx + r[i] <= x[k] + r[k], (k使得x[k]+r[k]在所有圆中是最大的一个)
同样的,0也不是最左的坐标(当r[m] - x[m] = r[1]时,就是选定了第一个圆,则x[1]=0).
例如下图:

所以说呢,我们两边都缩小了一点,是比实际的圆排列长度要小的,如果说按照这个算法你都还大于了目前的最小值,那么按照实际长度来计算岂不是更加大于了!
就好比实际最左边的横坐标为-4,最右边的为8, 现在我假设最左边为0,最右边为6,如果连(6-0)>min了,那么(8-(-4))更加大于最优值.