《最新圆排列问题PPT课件》由会员分享，可在线阅读，更多相关《最新圆排列问题PPT课件（24页珍藏版）》请在金锄头文库上搜索。
1、圆排列问题圆排列问题问题描述：给定n个大小不等的圆 C1,C2,Cn,现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3 个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示。其最小长度为2+4 贪心求近似最优解无效 剪枝策略脑海里出现多个圆 贪心求近似最优解无效 剪枝策略由刚才的例子,明显看出贪心无效,但是却让我想到一种剪枝策略.若在某个圆排列中有三个挨着的圆是按降序或升序排列,则此圆排列一定不是最小长度的圆排列.先看特例:(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-rihigh) high
4、=xi+ri;cleng=(high-low);相同圆不必处理4相同圆不必处理因为处理也是要付出代价的.如果有相同圆,我们所做的工作只是不必执行两圆交换的动作.该动作的时间复杂度为O(1),即：如果有相同圆，我们只能节省O(1)的时间，付出的却是每组圆排列中每个圆都要进行一次比较当n较大，相同圆较小时，得不偿失猜测到老师的测试数据，就不处理 解决镜像问题5解决镜像问题我们知道根据镜像原理,有一半的圆排列与另一半刚好对称,即:以某圆开头的圆排列,一定会存在一个以该圆结尾的圆排列.那么怎么来判断当前圆排列是否与前面已经算过的某圆排列对称呢？ 解决镜像问题例：设有四个圆的半径分别为4,3,2,1,则
5、所有的圆排列为:4321 3421 2431 14324312 3412 2413 14234231 3241 2341 13424213 3214 2314 13244123 3142 2143 12434132 3124 2134 1234解决镜像问题由上面的例子可以看出：最后一棵子树可以直接砍去。若第一子树保留，则从第二棵子树开始，凡是以该树前面的子树的根结点结尾的圆排列均会与已存在的圆排列对称。但是在本题中我们必须到叶结点才能做出判断，所以不判断，判断要付出更多代价。主程序代码主程序代码for(i=1;ix=new doublen+1; E-r=new doublen+1; E-x1=
6、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
