1、问题

给定n个圆的半径序列，将它们放到矩形框中，各圆与矩形底边相切，
求具有最小排列长度的圆排列。
例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示。其最小长度为圆的排列问题 - 图1
圆的排列问题 - 图2

2、解析

所谓圆形排列应该就是圆形的每个位置是等价的，圆形排列只考虑的是排列的元素之间的关系。
圆排列问题的主要思路是排列问题，通过建立排列树，再进行回溯剪枝，得出最优排列。
每次修改一个圆的排列位置，若修改后的排列长度变小，则在当前排列的前提下继续排列，否则回溯。
每次排列后，相切情况下圆的X坐标计算公式：x2 =(r+ri)2 + (r-ri)2,推出x = 2*sqrt(r+ri);r为自身半径，ri为相切圆半径。
使用分支限界计算，一定会遍历所有的排列情况，剪枝就是当前的排列如果比之前的排列反而长，就会去除这种情况以及他的子结点，达到了减少时间的目的，要取得最佳答案。

3、设计（伪代码）

  1. void Circle::Backtrack(int t)
  2. {
  3.     if (t > n) //计算排列长度
  4.         Compute();
  5.     else
  6.         for (int j = t; j <= n; j++) {
  7.             swap(r[t], r[j]);//确定当前第t个圆的半径
  8.             float centerx = Center(t);
  9.             if (centerx + r[t] + r[1] < min) {
  10.                 x[t] = centerx;
  11.                 Backtrack(t + 1);//开始深入到第t+1个圆
  12.             }
  13.             swap(r[t], r[j]);
  14.         }
  15. }

4、分析

最坏的情况，有n个顶点，每个顶点有m种颜色，其有n-1个子节点
O(n) = n*mn-1/m-1=O(nmn)

5、源码

https://note.youdao.com/ynoteshare1/index.html?id=162135ed88129b2280fe7126fd7c0ea6&type=notebook