最新圆排列问题PPT课件.ppt

《最新圆排列问题PPT课件.ppt》由会员分享，可在线阅读，更多相关《最新圆排列问题PPT课件.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、问题描述： 给定n个大小不等的圆 C1,C2,Cn,现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。 例如，当n=3，且所给的3 个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示。其最小长度为2+42 贪心求近似最优解无效 剪枝策略 脑海里出现多个圆 贪心求近似最优解无效 剪枝策略 由刚才的例子,明显看出贪心无效,但是却让我想到一种剪枝策略. 若在某个圆排列中有三个挨着的圆是按降序或升序排列,则此圆排列一定不是最小长度的圆排列. 先看特例:(26.9176)(266.182)(309.719) 贪心求近似最

2、优解无效 剪枝策略 求证：任何含有三个挨着的按升序或降序排列的圆的圆排列一定不是最小长度的圆排列。 证明： 用反证法。假设结论不成立，则其否命题为：存在一个含有三个挨着的按升序或降序排列的圆的圆排列是最小长度的圆排列。 (转不妨设文档)剪枝策略的效率分析 剪枝策略的效率分析：（看比较示例） 假设每个圆的半径都不相同,则剪掉的排列有:C(n,3)P(n-2) = (n(n-1)(n-2)/6)(n-2)! 又在每个当前圆处,都要进行O(2n)次计算 所以当n较大时,可以节省很多时间,即使到了离叶结点很近的地方 正确的求圆排列长度的方法 3.脑海里出现多个特殊圆 正确的求圆排列长度的方法 正确的求

3、圆排列长度的方法 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-

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

5、设有四个圆的半径分别为4,3,2,1,则所有的圆排列为: 4321 3421 2431 1432 4312 3412 2413 1423 4231 3241 2341 1342 4213 3214 2314 1324 4123 3142 2143 1243 4132 3124 2134 1234解决镜像问题 由上面的例子可以看出： 最后一棵子树可以直接砍去。 若第一子树保留，则从第二棵子树开始，凡是以该树前面的子树的根结点结尾的圆排列均会与已存在的圆排列对称。但是在本题中我们必须到叶结点才能做出判断，所以不判断，判断要付出更多代价。主程序代码 主程序代码 for(i=1;ix=new doub

6、len+1; E-r=new doublen+1; E-x1=0; E-end=1;for(int j=1;jrj=rj;E-Swap(i);E-cleng=2*E-r1;H.push(E); 主程序代码 for(int i=E-end+1;ir=new doublen+1; N-x=new doublen+1; for(int j=1;jxj=E-xj; N-rj=E-rj; N-end=E-end+1; N-Swap(i);N-Center(); N-Compute();if(confine(N) continue;H.push(N); 复杂度分析 复杂度分析 时间复杂度O(2n(n-1)+(n-1)(n-1)+(n-1)(n-1)(n-2)+(n-1)(n-1)!) 空间复杂度与时间复杂度相当谢谢观看！谢谢观看！ 欢迎提问与指导！欢迎提问与指导！ 24 结束语结束语