圆排列算法课件

1、圆排列问题 问题描述： 给定n个大小不等的圆 C1,C2,Cn,现要将这n个 圆排进一个矩形框中，且要求各圆与矩形框的底边 相切。圆排列问题要求从n个圆的所有排列中找出 有最小长度的圆排列。 例如，当n=3，且所给的3 个圆的半径分别为1，1， 2时，这3个圆的最小长度的圆排列如图所示。其最 小长度为2+42 算法任务：算法任务： 对于给定的n个圆，设计一个优先队列式分支 限界法，计算n个圆的最佳排列方案，使其长 度达到最小 思想历程 解题思路 1.实例 脑海里出现多个圆，若在某个圆排列中 有三个挨着的圆是按降序或升序排列,则此圆 排列一定不是最小长度的圆排列. 可能的解： 3.脑海里出现多个

2、特殊圆 正确的求圆排 列长度的方法 1求圆心坐标时，不能直接从倒数第二个圆 开始，必须从第一个开始，依次算过去 求当前圆排列的长度时，也是要从第一 个圆开始,依次算过去 所以，每个圆结点必须记录到该圆时的圆排 列，还得记录它的分支 /求圆心坐标 void CircleNode:Center() double temp=0; for(int i=1;itemp) temp=valuex; xend=temp; /求圆排列的长度 void CircleNode:Compute() double low=0,high=0; for(int i=1;i=end;i+) if(xi-rihigh) hi

3、gh=xi+ri; cleng=(high-low); 4相同圆不必处理 因为处理也是要付出代价的. 如果有相同圆,我们所做的工作只是不必执行 两圆交换的动作.该动作的时间复杂度为O(1), 即：如果有相同圆，我们只能节省O(1)的时 间，付出的却是每组圆排列中每个圆都要进 行一次比较当n较大，相同圆较小时，得不 偿失猜测到老师的测试数据，就不处理 5解决镜像问题 我们知道根据镜像原理,有一半的圆排列与另 一半刚好对称,即:以某圆开头的圆排列,一定 会存在一个以该圆结尾的圆排列.那么怎么来 判断当前圆排列是否与前面已经算过的某圆 排列对称呢？ 例：设有四个圆的半径分别为4,3,2,1,则所有

4、的圆排列为: 4321 3421 2431 1432 4312 3412 2413 1423 4231 3241 2341 1342 4213 3214 2314 1324 4123 3142 2143 1243 4132 3124 2134 1234 由上面的例子可以看出： 最后一棵子树可以直接砍去。 若第一子树保留，则从第二棵子树开始，凡 是以该树前面的子树的根结点结尾的圆排列 均会与已存在的圆排列对称。但是在本题中 我们必须到叶结点才能做出判断，所以不判 断，判断要付出更多代价。 主程序代码 void Circle:Backtrack ( int t ) if ( t n ) Compute ( ) ; else for ( int j = t ; j =n ; j+ ) Swap ( r t , r j ) ; cout r t r j endl ; float centerx=Center ( t ) ; if ( centerx + r t + r1 min ) x t = centerx ; Backtrack ( t + 1 ) ; Swap ( r t , r j ) ; 复杂度分析 不考虑计算圆排列长度和计算圆心很坐标的 时间，时间复