圆排列问题.ppt
圆排列问题,040320187 石曼银,问题描述：,给定n个大小不等的圆 C1,C2,Cn,现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3 个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示。其最小长度为2+4,编程任务：,对于给定的n个圆，设计一个优先队列式分支限界法，计算n个圆的最佳排列方案，使其长度达到最小,思想历程 解题思路,1.脑海里出现三个圆和四个圆 用贪心算法先求一个近似最优解？,用贪心算法求一个最优解？,从上面的圆的情况发现,尽量让小圆靠近大圆,能够节省圆排列的长度,可以用贪心算法先求出一个近似的最优解.然后以此最优解为剪枝条件，在叶结点处剪枝程序如下:,/用贪心策略求最佳排列 double bestL=0;int end=0;if(n%2=0)bestL=r0;end=n-1;elseend=n-1;bestL=rend+aend0;-end;for(i=0;iaii+1)bestL+=aiend+aendi+1;elsebestL+=aii+1;-end;bestL+=rend+1;,用贪心算法求一个最优解？,这种方法求出的圆排列长度，在有些情况下是错误的例：76 58 1 2求出的结果是:174.011而正确结果是:266.182由此,也想到了求圆排列长度的方法有误,书上的是正确的.,贪心求近似最优解无效 剪枝策略,脑海里出现多个圆 贪心求近似最优解无效 剪枝策略由刚才的例子,明显看出贪心无效,但是却让我想到一种剪枝策略.若在某个圆排列中有三个挨着的圆是按降序或升序排列,则此圆排列一定不是最小长度的圆排列.先看特例:(26.9176)(266.182)(309.719),贪心求近似最优解无效 剪枝策略,求证：任何含有三个挨着的按升序或降序排列的圆的圆排列一定不是最小长度的圆排列。证明：用反证法。假设结论不成立，则其否命题为：存在一个含有三个挨着的按升序或降序排列的圆的圆排列是最小长度的圆排列。(转不妨设文档),剪枝策略的效率分析,剪枝策略的效率分析：（看比较示例）假设每个圆的半径都不相同,则剪掉的排列有:C(n,3)P(n-2)=(n(n-1)(n-2)/6)(n-2)!又在每个当前圆处,都要进行O(2n)次计算所以当n较大时,可以节省很多时间,即使到了离叶结点很近的地方,正确的求圆排列长度的方法,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;ihigh)high=xi+ri;cleng=(high-low);,相同圆不必处理,4相同圆不必处理因为处理也是要付出代价的.如果有相同圆,我们所做的工作只是不必执行两圆交换的动作.该动作的时间复杂度为O(1),即：如果有相同圆，我们只能节省O(1)的时间，付出的却是每组圆排列中每个圆都要进行一次比较当n较大，相同圆较小时，得不偿失猜测到老师的测试数据，就不处理,解决镜像问题,5解决镜像问题我们知道根据镜像原理,有一半的圆排列与另一半刚好对称,即:以某圆开头的圆排列,一定会存在一个以该圆结尾的圆排列.那么怎么来判断当前圆排列是否与前面已经算过的某圆排列对称呢？,解决镜像问题,例：设有四个圆的半径分别为4,3,2,1,则所有的圆排列为: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=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)!)空间复杂度与时间复杂度相当,谢谢观看！欢迎提问与指导！,
