这一讲我们介绍一个圆排列的例子。圆排列问题呢是这样一个问题。 有n个圆,已知它们的半径,把这些圆排列到一个 每个圆和底线相切, 假定每个圆至少占有大于1的一个长度, 求具有最小长度的ln的这样一个圆的排序顺序。 我们先看个例子。这是三个圆, 我们可以这样来排列,这三个圆都和这个底线相切,那么 它占有的排列长度就是到这个地方截止, 如果采用下面这种排列方式,它占有的排列长度要长一些,到这个地方 截止。我们希望找一个好的排列顺序,使得 所占有的这个排列长度达到一个最小值, 因此这个问题的解呢是一个排列,1,2,3,4...n的一个排列, 在这个解下使得这个长度值达到最小, 这是问题的要求。下边我们看一下算法的设计。 这个算法还是采用分支限界的方法。解是一个排列 i1,i2,in是1,2,3,4,...n的一个排列,搜索空间是一棵排列树, 部分的解向量i1,i2,...ik 表示前k个圆已经选好了,就是半径是多少都知道了, 然后把这选好的k个圆的标号放到B集合里面, 那么下一个圆的选择的时候, 就不能用这些已经用过的标号了。所以下一个圆的ik+1个选择 必须从全体标号中减掉已用过的标号, 从剩下 当前得到的最小圆排列的长度是界, 这是关于界的规定。下边我们看一看 为了给出它的代价函数,需要一些公式,我们 先把这些公式中的符号简单介绍一下。 k表示算法已经考察到 就是前k个圆都考察完了。那么rk代表第k个圆的半径。dk 是圆心的水平距离。xk呢是第k个圆的圆心的坐标, 那么第一个圆呢它的坐标是0,横坐标是0。lk 是1到k这k个圆放好以后,它已经占有的排列长度。 大Lk表示把这前k个圆放好以后, 对应的这个结点它的代价函数值用大Lk来表示。 那么大Lk是一个下界,它比真正后面,把后序的圆 都放好以后的真正的排列长度,应该是小于等于这个真正的排列长度。 下边我们看一下这个公式。 现在假定考察到第k个圆已经都排好了, 这是第k个圆的 圆心的水平位置,那么这就是xk,就是这个点的坐标,就是这点就是xk, 也就代表了这段长度,因为第一个圆的圆心坐标是在0,所以这段长度呢就是第 k个圆的圆心坐标位置。那么第k-1个圆心坐标呢在这个位置, 它们两的之间的这段距离就是圆心的 水平距离,因此我们拿 第k-1个圆的这个坐标位置加上 刚好是第k个圆的 然后部分的排列长度 是现在为止,前k个圆已经放好了, 它究竟占有多少个排列长度呢?可以这样计算, 这个是坐标原点0,这个是坐标点xk,所以 xk呢正好代表了第一个圆的圆心到第k个圆的圆心的水平距离, 然后我们加上这一段第k个圆的半径,再加上这个第一个圆的半径, 正好就是它占有的这个排列长度,就是这个公式。xk是那个水平距离, 加上第k个圆的半径,加上第一个圆的半径,这个就是部分的排列长度。 那就是说,我们从第一个圆开始,从这个地方开始,到这个位置,这个 长度就是这个lk。那么后面还有n-k个圆要放呢? 当把这些个圆放好以后, 你看xk是到这个第k个圆的 这个圆心的位置,这个就是xk了。然后我加上 下一个距离,就是 再加上第k+1个圆到第k+2个圆的圆心的水平距离,一直加下去, 加到第n个圆的这个距离,也就是说加上 n-1号圆到第n个圆的这个距离,因此到这个dn为止,已经是到这个 位置了,把这个位置算到以后,我再加上最后一个圆的半径,加上这段距离, 再加上第一个圆的半径,因为刚才是从圆点算的,所以把左边这个半径 再加上,这样都加上以后呢,正好是这n个圆所占有的 长度值,就是这个公式。这就是真正的排列长度。 你要计算这个长度的话,这些个d必须都得知道才行,你要知道 这些个d必须知道后边的圆是哪个标号的圆放在哪个位置, 我才能够算出这个连续的这些个两个圆的圆心的水平距离。 所以关键要知道这个排列长度,必须知道这些个d。 下边我们看一下这些d应该怎么计算。比如说 这是k-1号圆,这是第k个圆, 那么这是它的圆心的水平距离dk。 这个dk,这正好是一个直角三角形,这个斜边长度是两个半径的和, 就是这两个半径的和,这条直角边的长度正好是这两个圆半径的差, 因此根据勾股定理,斜边的平方减掉这条直角边的平方再开方,就是 这个水平距离。因此就是这个公式。 把这个公式里边的项 得到的是4倍的rk-1乘以rk,然后那个4可以开方拿到外边去,得到这个结果。 因此我们看到这两个圆圆心的 水平距离应该怎么计算呢?就是根据 由这个公式可以算出来,这是它的计算公式。 我们把这个公式代到刚才的那个整个的距离公式里边去, 这是刚才得到的这个公式,就是 第k-1个圆到第k个圆的圆心的水平距离是这个公式。 那代到那个排列长度里边去呢, xk已经知道了,然后加上第k个圆到第k+1个圆的圆心的水平距离, 再加上k+1圆到k+2个圆的圆心的水平距离,一直加到 到第n个圆的圆心的水平距离,再加上第n个圆的半径,再加上 第一个圆的半径,这正好就是那个排列长度的公式。 那这个公式是真正的知道了后面圆的 排列顺序以后,就可以按照这个公式来计算出排列长度。 我们现在是需要代价函数,就是能不能对这个值做一个估计。 从r1到rk都知道了,而后边的这些个rk+1,rk+2不知道, 因为你后边的排列顺序还不知道呢。所以这些个半径的值也不知道。 那我们需要的是对这个值能够估计出一个下界出来。 这个下界怎么估计呢?我们就用第k个圆的半径 加上后边没有出现过的那些个圆,它的半径值 把这些个半径都放到一块 最小值拿来,把那个最小值叫做r, 我们把这里边所有的从rk+1到rk+2,一直到rn 全部用r来替换,那这就变成两个r了,两个r一开方,就变成2倍的r。 这个也是,这是r²,一开方出来2倍的r,所以第一项 开方以后2r,这项开方以后2r,一直到最后这一项开方以后2r。 一共有多少个2倍的r? 所以n-k乘以2倍的r,就是所有这些项 的下界,然后加上rn,rn我也用一个 小于等于它的r替换,这个没有问题,r1是已知的, 把它抄过来就行了,所以这样得到的这个 公式正好是上面这个大的真正排列长度的 一个下界。这就是它的下界的公式。 所以这个是真正的排列长度,而这一项呢 是一个下界,这是关于它的这个 估计。那么这一项就可以作为代价函数了。 我们 看一下这个真正的这个表示。代价函数的值是Lk, 它等于xk 那么这里边的r 这些个半径它里边最小的那个拿来, 作为它们估计的下界就可以了。这就是它的这个代价函数的公式。 那么关于这个公式呢我们可以 代到这个算法里边去,来做裁剪, 整个搜索树的树叶片数是n阶乘片, 每条路径的代价函数的计算应该是O(n)的时间, 因此算法在最坏情况的复杂度应该是 O(n n!),大概是(n+1)!的量级, 是这样的一个结果。是一个 阶乘这样时间的一个复杂度,所以最坏情况的复杂度跟蛮力算法没有区别。 我们看一个具体的例子。一共是 半径的集合是这样一些参数, 如果是1,2,3,4,5,6这6个圆, 它的半径正好就是按照这个排列, 给出的半径 2号圆半径是1,3号、4号、5号、6号,这是原始的输入, 下面我们看一下它的 就是只考虑第一个圆,就是1号圆,我们现在的排列就是这个顺序了,1号圆被选进来了, 选进来以后,它的这个距离这个是0,因为它是放在圆心的位置, 因此它的圆心的坐标是0, 它占有的长度是2,因为这个圆的半径是1了,就是这个1, 1的话它占有的长度是2。这个估计值是怎么估计的呢? 后边还有5个圆没放呢,那5个圆至少有10的长度, 已经占有的2个长度,因此这个估计值是12,就是无论你怎么放,这个圆排列 的长度不会小于12。下边 我们考虑第2个圆,第 是1的圆,考虑 放了2个圆,这个圆的圆心是放在2, 它到第1个圆的圆心距离是2,它的 圆心的位置坐标是2,两个圆的排列长度是4,还有4个圆没放, 那么对这4个圆放的排列长度怎么估计呢? 我们看到这个时候是2,3,4,5,6 1号半径值,作为估计的下界。因为这个半径值是1, 所以后边4个圆的长度下界是8,加上已经有的4,还是12。 下边我们看看假定考虑第3个圆, 第3个圆是什么情况呢?就是这个时候它的半径已经变成2了,第3个圆的半径是2了, 第2个圆到第3个圆的距离根据勾股定理算出来是2.8, 你刚才第2个圆的位置是2,加上这2.8,所以第3个圆的 圆心的位置是4.8的坐标, 它占有的距离,就是3个圆占有的距离 4.8,再加上 2,6.8,再加上第1个圆的半径1,所以是7.8,真正占有的 这个长度是7.8。这个估计值是19.8, 这个估计值怎么估计的呢?我们看到, 7.8是这个地方已经4.8加上这个2, 加上这个1,已经得到了7.8的长度的估计值, 就是说已经占有的长度的值是7.8, 然后后边的还有3个圆没有放, 那么那3个圆跟这个圆的半径加在一起的最小值,半径值是2, 半径值是2的话,那么剩下的那几个圆 一共是还有3个圆没放, 每个圆半径值都是2,直径就要占有4的长度,三四十二,所以12 加上7.8得到19.8,这个是它的估计值。就是后边你无论再怎么放, 至少要占有19.8的长度,这就是代价函数的估计值。 那么跟这个相同的方法我们可以接着向下来估计, 当把第4号圆放好了以后,可以计算出它的半径是, 第4号圆的半径还是2,它的圆心距离是8.8,然后 真正4个圆占有的长度是11.8, 估计出来的后边几个圆都进来 19.8,这是一个下界。然后我们还可以接着再来往下做。 5号圆放上去,这个时候5号圆的半径 变成3了,更大了,因此这个估计值就更精确了, 最后估计的所有圆的 我们当把第6个圆放上去以后, 就可以来同样地计算。 第6个圆放上去以后呢,它的半径已经达到了5, 这个时候它的圆心位置是21.4, 整个占有的长度是27.4,这是一个精确的长度了, 真正的这个下界跟它完全相等,这是我们看到的这个计算过程, 就是按照刚才的代价函数对这6个圆的一个计算过程。 当然这个解并不是最好的解,就是这个27.4的这个长度。 那么我们看到如果你的排列顺序改变一下, 1,3,5.6,4,2的顺序来排列, 这样排列以后呢,它的最短的长度是26.5, 就是比你27.4的值还要好。 而这个排列长度呢,就是刚才那个27.4的排列,就是 两个半径是1的,两个半径是2的,一个半径是3的,一个半径是5的, 刚才这个计算到这个地方是26.4,再加上第一个圆的 半径是1,所以得到27.4的值, 这个不是一个 把这一讲小结一下。 我们先看看圆排列问题的定义, 它是给定了n个圆的半径, 求一种排列,使得在这个排列下,它占有的排列长度达到最小。 那么怎么设计代价函数呢? 它是把已有的排列长度加上后续圆排列长度的一个下界, 通过这个公式来定义这个代价函数, 这个算法的复杂度它是达到了阶乘量级的函数, 它是一个复杂度比较高的算法,这是最坏情况下, 但是在通过裁剪的时候,刚才的代价函数就会 起作用,使得它的平均运行时间会得到改善。 关于这个圆排列问题呢就介绍到这里。