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

一.问题描述

给定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

代码如下:

// 圆排列问题
#include
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 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 && n)
    {
        cout<<"请输入每个圆的半径:"<>r[i];
        float ans = CirclePerm(n, r);
        cout<<"最小圆排列长度为:"<

下面做几个解释:

• 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))更加大于最优值.

运行结果:

构建出的排列树如下:(和之前的大同小异)

讲完了,应该能够看懂吧大伙.(●'?'●)

欢迎大家访问我的个人博客 --- 乔治的编程小屋,和我一起努力进步吧!