圆形packing问题算法

《圆形packing问题算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求解NP难度问题是本世纪及下世纪计算机科学技术的瓶颈任务.然而自本世纪70年代至今的研究说明，对于NP难度问题根本就不存在经典数学所希求的那种既完整严格又不是太慢的求解算法［1，2］，亦即彻底的公理化形式化的数学方法在这里没有多大的用处.　　于是人们开始到大自然中去寻找智慧，以期得出关于NP难度问题的非绝对完整的，但是是高速度高可靠度的高效率近似求解算法.其工作路径是，到物理世界中去寻找出与原始数学问题等价的自然现象，然后观察其中物质运动的演化规律，从中受到启发以得出形式化的，对于数学问题的求解算法［3］.可以称这个工作路径为拟物方法.　　由于物理状态的演化天然地是按照使其Lagrange

2、函数的时间积分达到最小值的方式进行［4］，这就决定了拟物算法最终在数学上落实为优化问题.然而用数学方法求解优化问题，常常会碰到计算落入局部最小值陷阱的困难境地，对于如何跳出局部最小值陷阱，让计算走向前景更好的区域中去的问题，拟物方法已无能为力.但是，人类在最近几千年的共同生活中形成了丰富的社会经验，利用这些经验往往可以启发出好的“跳出陷阱”的策略［5，6］.我们可以将这种把人类的社会经验形式化为算法用以求解某些特殊困难的数学问题的方式称为拟人途径.　　拟物拟人算法的效率通常比生物遗传算法、神经网络方法、淬火法［7］要高，其原因是它有针对性地为具体问题找到了非常贴切的物理世界，而不是像在遗传

3、、神经网络、淬火方法中那样依赖于一个唯一的始终不变的因而往往是不太贴切的物理体系.另外，拟人方法是向人学习，而人比起遗传、神经网络、淬火世界里的那些蛋白质单个的神经元及晶体显然有高得多的智慧.当然，这里的关键在于合适的数学形式化前夜的艺术和手段，要得到它们也不是一件很容易的事情，需要长期艰苦细心的工作.这种得出算法的过程的艰苦性，可以说是拟物拟人途径的一个缺点.1　问题的提法［1，3］　　假设已知一个圆形的空盒子(容器)，另外又已知一些不同的圆饼，问能否将这些圆饼互不重叠地放进空盒子中去(图1).此问题更形式的表达如下.图1　　对于任意给定的正整数M和任意给定的M+1个正实数R0,R1,…

4、,RM.问是否存在2M个实数x1,y1,…,xM,yM使得对于｛1,2,…,M｝中任意的正整数i有对于｛1,2,…,M｝中任意两个不同的正整数i,j有如果存在，则请具体给出一组合乎条件的实数.2　拟物与拟人的思路2.1　拟物的思路［3，8～10］　　我们在二维Euclid空间中考虑问题.将这M个圆饼都想象为光滑的弹性实体；将这个容器想象为整个的二维无穷弹性实体，在因挖去了半径为R0的一个圆饼之后而剩下的无穷部分.　　设想这M个圆饼被挤缩在这个容器中.由于各个物体都有要恢复自己形状大小的趋势，它们之间产生了挤压弹性力的相互作用.在这种挤压弹性力的驱使之下，各物体会产生一系列的运动.作为这种运

5、动的结果，可能就是问题的解的确立——各物体到达某种相互合适的位置，两两互不嵌入.　　如果我们能用某种数学方法将这一系列运动加以模拟，则事实上就得到了一种求解圆形packing问题的算法.2.2　拟物算法　　将二维笛卡儿坐标的原点取在容器的中心上(见图1).记第i(i=1,2,…,M)个圆饼的圆心坐标为xi,yi，则第i个圆饼与圆盘之间的嵌入深度为：第i与第j两个不同的圆饼之间的嵌入深度为　　显然，dij与doj恒非负.dij>0表示第i与第j二物体之间互有嵌入，doi>0表示第o与第i两个物体之间互有嵌入.dij=0表示第i与第j二物体之间没有嵌入，doi=0表示第o与第i二物体之间没有嵌

6、入.根据弹性力学，二光滑弹性物体之间的挤压弹性势能正比于它们之间互相嵌入深度的平方.因此可以用d2λμ来表征第λ与第μ个物体之间的挤压弹性势能：可以认为第i个圆饼具有的挤压弹性势能Ui为：整个体系的势能为：　　由(2.1)～(2.5)式，整个体系的势能U是全部圆饼的坐标x1,y1,…,xM,yM的已知函数：显然我们有：(ⅰ)U(x1,y1,…,xM,yM)在整个(-∞,+∞)2M上有定义，非负；(ⅱ)若U(x1,y1,…,xM,yM)>0，则(x1,y1,…,xM,yM)不是圆形packing问题的解；若U(x1,y1,…,xM,yM)=0，则(x1,y1,…,xM,yM)是圆形packi

7、ng问题的解.因此，圆形packing问题被转化成了对于已知函数(2.6)式的优化问题，即求出函数的最小值点(x*1,y*1,…,x*M,y*M)，若U(x*1,y*1,…,x*M,y*M)=0，则x*1,y*1,…,x*M,y*M即是问题的解，若U(x*1,y*1,…,x*M,y*M)>0，则问题无解.　　对此优化问题，我们有现成的求解算法，梯度法或称最陡下降法.可以指出，在按梯度法求解的过程中(x1,y1,…,xM,