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

QUASI-PHYSICAL ALGORITHM FOR THE EQUAL CIRCLES PACKING PROBLEM

作　　者：黄文奇[1] 叶涛[1] 

机构地区：[1]华中科技大学计算机学院,武汉430074

出　　处：《系统科学与数学》2008年第8期993-1001,共9页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(60773194);国家973项目基金(2004CB318000)资助课题

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

关 键 词：等圆PACKING问题 NP难度 拟物方法 启发式算法. 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]