求解等球packing问题的两个策略  

Two Strategies for Solving the Equal Sphere Packing Problem

作　　者：余亮[1] 黄文奇[1] 

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

出　　处：《软件学报》2012年第9期2285-2296,共12页Journal of Software

基　　金：国家自然科学基金(61070235;61173180)

摘　　要：为求解等球packing问题,在拟物模型基础上提出两个启发式策略:伪球策略和序列对称换位策略.前者旨在保证获取精确解;后者则用于从局部最优布局出发搜索到紧凑的可行布局.在处理器为Pentium E6500 2.93GHz的PC机上进行了实算.在球形容器内对多达200个等球、在立方体内对多达150个等球进行了紧密装填.结果在质量和算例数量上均显著改进了国际上已知最好记录.特别地,在半径小于5的大球中装下了68个半径为1的等球,证明否定了一个猜想,其认为半径为5的大球最多只能装下67个半径为1的等球.Based on the quasi physical model, two heuristic strategies are proposed for dealing with the equal sphere packing problem. The fake sphere strategy guarantees that the results are rigorous. The serial symmetrical relocation strategy is designed to search a dense feasible configuration from a local optimal configuration. Through a personal computer with Pentium E6500 2.93GHz CPU, the study has densely packed up to 200 equal spheres in spherical container and up to 150 equal spheres in cubic container. The obtained results not only have better quality than that of the international best known records, but also greatly outnumbered them. Particularly, the study packed 68 equal spheres of radius 1 into a large sphere whose radius is smaller than 5, thus proved wrong a conjecture which alleges a large sphere of radius 5 can contain at most 67 equal spheres of radius 1.

关 键 词：等球packing问题 拟物模型 启发式 伪球策略 序列对称换位策略 

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