问题

给出一个若干个圆，将他们放到矩形框中，与矩形框的下底面相切，圆与圆之间不可以相交，求一个圆的排列方式使得所有圆中最左侧的点到最右侧的点距离水平距离最小

解析

计算两圆左右两侧距离

如图所示，对于现切的两个圆，他们两个圆心之间的距离可以通过勾股定理计算，设距离为 $x$ 则 $x=\sqrt{(R_1+R_2)^2-(R_1-R_2)^2}$ ，而对于如图所示的两圆最远端的水平距离为 $R_2+x+R_1$
如图所示，此时两圆的最远距离为 $2R_2$
$R_1,R_2$ 互换同理，计算新加入的圆时需要同时记录最右侧和最左侧的位置
其中右侧的距离为 $R_2$ 的圆心位置 $-R_2$
如图所示，后加入的圆可能不与相邻的圆现切，而是与前面的圆现切
新加入一个圆后的计算方式
依次计算新加入的圆与已经加入的圆的现切形成的圆心位置，容易得出新圆的圆心位置一定是最远的那个位置
将新得出的圆心位置减去圆的半径，得出最右侧距离，加上圆的半径，得出最左侧距离。分别与现有的最右最左取最小值和最大值
得出最优排列的方式
在得到上述计算宽度的方法后，只需要对所有可能的排列进行列举并一一计算其宽度，取最小值即可
不难发现这个问题满足多米洛性质，因此可以可以用回溯法，在知晓前 $n$ 个圆排列的情况下，可以求出插入第 $n+1$ 个圆后的答案

一点点分支限界：如果当前已经排列好的圆宽度超过目前的最后答案，则不必继续尝试，可以直接减枝尝试其他的排列方式

设计

minWidth = inf
Circles = the set of Circle
Search(numberOfCircle,leftMost,rightMost):
  for i in Circles:
      if not used Circle[i]:
          if it is the first Circle:
              Center of Circle = Circle.raidus;
          else
              for j in usedCircles:
                  Center of Circle = max(Center of Circle,calcute the new Center);    
          currentLeftMost = min(leftMost,Center of Circle - Circle.radius);
          currentRightMost = max(rightMost,Center of Circle + Circle.radius);
          if it is the last Circle:
             if currentRightMost-currentLeftMost<minWidth:
                  minWidth = currentRightMost-currentLeftMost
                  bestPermutation = currentPermutation
                  exit
          else
              Search(numberOfCircle,currentLeftMost,currentRightMost);

分析

在所有的运算中，计算圆圆之间的关系最为复杂，复杂度的衡量以此为标准
以 $3$ 个圆的情况为例，以下是这 $3$ 个圆排列可能出现的所有情况图片说明

复杂度的上界就是决策树上点的总个数，除第一层一个空节点外，每一层节点的个数都是上一层节点个数的 $x$ 倍，其中 $x$ 是未被选中的点的个数

$\begin{align} F(n)&=n+n\times(n-1)\times+n\times(n-1)\times(n-2)\times+……+n\times(n-1)\times(n-2)……\times2\times1\\ &=\frac{n!}{(n-1)!}+\frac{n!}{(n-2)!}+……+\frac{n!}{0!}\\ &\sim O(n!) \end{align}$
同时每个节点内要进行 $n-x$ 次计算来求出实际的圆心位置
最终复杂度 $~O((n+1)!)$

源码

传送门

算法课-圆排列问题

问题

解析

计算两圆左右两侧距离

新加入一个圆后的计算方式

得出最优排列的方式

设计

分析

源码