求解等圆Packing问题的完全拟物算法

沿着拟物的思路进一步研究了具有NP难度的等圆Packing问题.提出了两个拟物策略,第一个是拟物下降算法,第二是让诸圆饼在某种物理定律下做剧烈运动.结合这两个策略,提出了一个统一的拟物算法.当使用N(N=1,2,3,…,100)等圆最紧布局的国际记录对此算法进行检验时,发现对于N=66,67,70,71,77,89这6个算例,本算法找到了比当前国际纪录更优的布局.

Quasi-Physical Algorithm for the Equal Circles Packing Problem

The equal circles packing problem is considered by using the quasi-physical method. Two quasi-physical strategies are presented. The first one is a quasi-physical descent algorithm, and the second is to make violent movements of the circles guided by certain physical laws. By these strategies, a unitary algorithm is given to solve the congruent circles packing problem. This algorithm is tested by the famous benchmark of packing N(N=1,2,...,100) congruent circular disks into a smallest possible circular container. This benchmark is also a clear touch stone for quality of algorithm in solving famous NP-hard problems. Comparing with previously recorded best packings, better packings for N=66,67,70,71,77,89 are found.