参考资料

https://blog.csdn.net/liufeng_king/article/details/8890603
https://blog.csdn.net/qq_32400847/article/details/51474105
https://blog.csdn.net/yzmck/article/details/4302554 原理解释的很赞
http://www.doc88.com/p-079198350775.html
http://www.docin.com/p-802993408.html 看算法效率部分

问题描述

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

问题大方向分析

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

1. center计算圆在当前圆排列中的横坐标，由x^2 = sqrt((r1+r2)^2-(r1-r2)^2)推导出x = 2*sqrt(r1*r2)。

2.Compute计算当前圆排列的长度。变量lenmin记录当前最小圆排列长度。数组r存储所有圆的半径。数组x则记录当前圆排列中各圆的圆心横坐标。

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

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;const int N=4;
double minlen=10000,x[N],r[N];//分别为最小圆排列长度，每个圆心横坐标，每个圆半径
double bestr[N];//最小圆排列的半径顺序double center(int t)//得到每个圆的圆心坐标
{double temp=0;for(int j=1;j<t;++j)//因为目标圆有可能与排在它之前的任一圆相切，故需一一判断{double xvalue=x[j]+2.0*sqrt(r[t]*r[j]);//不是r[j],是x[j],要被自己蠢哭了if(xvalue>temp)temp=xvalue;}return temp;
}
void compute()
{double low=0,high=0;for(int i=1;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<minlen){minlen=high-low;for(int i=1;i<N;++i)bestr[i]=r[i];}
}
void backtrack(int t)
{if(t==N){compute();}else{for(int j=t;j<N;++j){swap(r[t],r[j]);double centerx=center(t);if(centerx+r[t]+r[1]<minlen){x[t]=centerx;backtrack(t+1);}swap(r[t],r[j]);}}
}
int main()
{r[1]=1,r[2]=1,r[3]=2;cout<<"每个圆的半径分别为：";for(int i=1;i<N;++i)cout<<r[i]<<' ';cout<<endl;backtrack(1);cout<<"最小圆排列长度为："<<minlen<<endl;cout<<"最优圆排列的顺序对应的半径分别为：";for(int i=1;i<N;++i)cout<<bestr[i]<<' ';cout<<endl;return 0;
}

详解上诉代码

定义数组那几个就不讲了，看看注释就行了。下面来重点讲解一下三个功能函数。

1.首先是center函数，center计算圆在当前圆排列中的横坐标，由x^2 = sqrt((r1+r2)^2-(r1-r2)^2)推导出x = 2*sqrt(r1*r2)，这个很容易理解吧。下面有人就会有疑惑了，为啥要把计算圆心坐标的公式放在一个for循环里面呢，我们很容易会有一个先入为主的思想，那就是后一个圆必然与排在它前一个位置的圆相切，其实排在任意位置的圆与其前或后的任意一个圆都有可能相切的，画个图就很清晰了。

大致就是这个意思，只要大小合适，目标圆就有可能与排列中的任意一个圆相切，搞明白了这个问题，那让我们顺着计算机的思维继续往下走，假设我们现在要求x[3]的坐标，只能从前往后的一一比较（此时x[1]和x[2]是已知的），先得到x[1]+a的值(即x[3]的可能坐标)，再得到x[2]+b的值（与上一次的可能值相比较，若距离更大则更新，否则不做处理），后面依次类推。

有人可能会问为啥x[2]+b不能作为x[3]的值？很简单，圆2与圆3不相切，得到的b比实际的大，结果就偏大了。

友情提醒：for(int j=1;j<t;++j)，因为for循环在初始化后是紧接着进行判断的，故当t=1时，j<1不成立直接跳过本次循环，直接返回temp=0，

故x[1]=0.

2.接下来说下backtrack函数，这里用到的核心方法就是回溯法，回溯法最重要的就是求出界限函数.按问题性质,可画出子集树或排列树.

if(centerx+r[t]+r[1]<minlen)的作用是剪枝，先判断当前层是否在范围内，是则继续搜索下一层，否则直接回溯。下图是不进行剪枝时，六种可能性都搜索一遍的过程。

3.最后我们来解释一下compute函数，这个其实弄明白了上面的相切的概念，这就so easy 了，夸张一点，我们可以想象其中任意的一个圆无限大或无限小，无限大的话那其余的圆就可以统统忽略了。因为已知所有圆的x[]和r[],很容易求出每个圆的左右坐标，通过比较找出最小的左部坐标和最大的右部坐标，一减就是该圆排列的长度，然后把每次不同的排列长度相比较，找到更小的minlen就更新。