16基于回溯法的圆排列问题

1. 问题

圆排列问题：给定n个圆的半径序列，将它们放到矩形框中，各圆与矩形底边相切，求具有最小排列长度的圆排列。

2. 解析

首先，对于n个圆的半径序列，我们将其全排列，并以树的形式展现。
这个树是多叉树，它满足：根节点的子结点数即为圆的个数，其后，随着树层数的增加，每后移一层，该层每个结点的子节点数会比前一层每个结点的子节点数减1，直至层结点的子结点数为0，问题的多叉树即构造完毕。

如下图，展现的是半径序列为{1,1,2}的排列多叉树：
在这里插入图片描述
由图很容易看出，根节点到每一个叶结点的追溯即是一种圆排列方式，因此当算法确定叶结点的位置后，我们就可以得出该叶结点所在的圆排列长度，经比较，便可以得到全局最短的圆排列长度及它的序列。
但是，我们都知道，当n稍大的时候，这棵树就会很庞大，算法效率也会很低。因此，我们采用了回溯法的思想，减少遍历情况，设立了一个界限函数——在前k(k<n)个结点排列都确定的情况下，计算加上第k个结点的排列长度，倘若该长度比已经计算得到的圆排列的最小长度还要长，就剪断分支，回溯父结点，不再遍历这第k个结点的子结点（因为k个圆的排列就已经比别的序列n个圆的排列长了，再继续下去到叶结点，肯定也不是全局最短圆排列长度）；否则，继续。

基本思路已经理清了，倘若得到了一个完整排列，如何计算其长度呢？

计算该排列每个圆的圆心坐标
若排列满足最短，则对于排列中的每一个圆，存在另外至少一个圆与之相切。（n>=2） （理解这句话非常重要）由于在该圆前面的圆序列及圆心坐标已经确定，我们就可以从中找到一个与所求圆相切的圆，并根据如下相切圆圆心横坐标距离公式，得到所求圆圆心在当前排列的横坐标位置。

因为所求圆不一定与排它前一个的圆相切（如下图所示），所以在getCenterX()中得到使其横坐标最右的坐标位置即可。注意，第一个圆的圆心横坐标为0.
分别计算该排列左边界、右边界坐标，相减得到圆排列长度
圆序列确定好了（叶结点确定），各圆心横坐标也计算好了，根据每个圆心横坐标及其半径计算它的左（右）边界坐标，众多圆中起始（末尾）位置最左（右）的就是该排列的左（右）边界横坐标，将左右边界横坐标相减，即为该排列的长度。
将得到的圆排列长度与界函数值minlength比较，比它小则更新minlength和最佳排列半径数组bestOrder[n].

举个栗子

给定n为4的圆半径序列为{1,1,2,4}，其最短圆排列为{2,1,4,1}.
在这里插入图片描述

3. 设计

void traceBack(int k,int num) {if (k == num) then//抵达叶子，得到当前排列方式的排列长度getLength(num);else for (j = k to num-1)swap(radius[k], radius[j]);//得到圆k的圆心坐标nowX ← getCenterX(k,num);//剪枝条件if (nowX + radius[k] + radius[0] < minlength) thencenterX[k] ← nowX;traceBack(k + 1,num);end if//回溯结点swap(radius[k], radius[j]);end forend if
}

4. 分析

该算法在最坏情况下可能需要O(n!)次计算当前圆排列长度，也就是将每种情况都考虑了一遍（全排列），而每次又需要 O(n) 的计算时间，从而整个算法的计算时间复杂度为traceBack(0,n)=O((n+1)!).
如果圆半径呈镜像排列，traceBack(0,n)=O((n+1)!/2).
若圆半径一样，traceBack(0,n)=O(1).

5. 源码

点击前往Git

在这里插入图片描述

#include<iostream>
#include<cmath>
#define N 200using namespace std;
//半径	圆心横坐标	最短圆排列
double radius[N], centerX[N],bestOrder[N];
//最短圆排列长度
double minlength = 0xffffff;//得到每个圆的圆心位置
double getCenterX(int k,int num) {double tmp = 0;//排列最短必定存在一个圆与该圆相切，找到一个与之相切的圆即可得到该圆坐标for (int i = 0; i < k; i++) {//相切圆圆心横坐标距求法double value = centerX[i] + 2.0 * sqrt(radius[k] * radius[i]);if (value > tmp) {tmp = value;}}return tmp;
}//得到当前圆排列长度
void getLength(int num) {double left = 0xffff, right = -0xffff;for (int i = 0; i < num; i++) {//众多圆中起始位置最左的就是该排列的左边界if (centerX[i] - radius[i] < left) {left = centerX[i] - radius[i];}//众多圆中末尾位置最右的就是该排列的右边界if (centerX[i] + radius[i] > right) {right= centerX[i] + radius[i];}}//判断该排列是否为已计算排列中长度最小的，是则更新最小排列长度if (right - left < minlength) {minlength = right - left;//并更新最小圆排列顺序for (int i = 0; i < num; i++) {bestOrder[i] = radius[i];}}
}void traceBack(int k,int num) {//全部圆都已参与排列，计算该排列长度if (k == num) {getLength(num);}else {for (int j = k; j < num; ++j){swap(radius[k], radius[j]);double nowX = getCenterX(k,num);//剪枝条件if (nowX + radius[k] + radius[0] < minlength){centerX[k] = nowX;traceBack(k + 1,num);}//回溯swap(radius[k], radius[j]);}}
}int main() {int n;while (1) {minlength = 0xffffff;cout << "请输入圆的数量:";cin >> n;if (n == 0) {break;}cout << "请分别输入"<<n<<"个圆的半径:";for (int i = 0; i < n; i++) {cin >> radius[i];}traceBack(0,n);cout <<"最小圆排列长度为：" << minlength << endl;cout << "最优圆排列的顺序对应的半径分别为：";for (int i = 0; i < n; ++i)cout << bestOrder[i] << ' ';cout << endl<<endl;}return 0;
}