| 摘要: |
| 为求解等球packing 问题,在拟物模型基础上提出两个启发式策略:伪球策略和序列对称换位策略.前者旨在保证获取精确解;后者则用于从局部最优布局出发搜索到紧凑的可行布局.在处理器为Pentium E6500 2.93GHz的PC 机上进行了实算.在球形容器内对多达200 个等球、在立方体内对多达150 个等球进行了紧密装填.结果在质量和算例数量上均显著改进了国际上已知最好记录.特别地,在半径小于5 的大球中装下了68 个半径为1 的等球,证明否定了一个猜想,其认为半径为5 的大球最多只能装下67 个半径为1 的等球. |
| 关键词: 等球packing 问题 拟物模型 启发式 伪球策略 序列对称换位策略 |
| DOI：10.3724/SP.J.1001.2012.04158 |
| 分类号: |
| 基金项目:国家自然科学基金(61070235, 61173180) |
|
| Two Strategies for Solving the Equal Sphere Packing Problem |
|
YU Liang, HUANG Wen-Qi
|
|
School of Computer Science and Technology, HuaZhong University of Science and Technology, Wuhan 430074, China
|
| Abstract: |
| 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. |
| Key words: the equal sphere packing problem the quasi physical model heuristic the fake sphere strategy serial symmetrical relocation strategy |
