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

• 作者: 余亮 黄文奇
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 等球packing问题 拟物模型 启发式 伪球策略 序列对称换位策略
• 年，卷（期）: 2012,（9）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 2285-2296
• 页数: 12页
• 分类号: TP301
• 字数: 7294字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2012.04158

摘要

为求解等球packing问题,在拟物模型基础上提出两个启发式策略:伪球策略和序列对称换位策略.前者旨在保证获取精确解；后者则用于从局部最优布局出发搜索到紧凑的可行布局.在处理器为Pentium E6500 2.93GHz的PC机上进行了实算.在球形容器内对多达200个等球、在立方体内对多达150个等球进行了紧密装填.结果在质量和算例数量上均显著改进了国际上已知最好记录.特别地,在半径小于5的大球中装下了68个半径为1的等球,证明否定了一个猜想,其认为半径为5的大球最多只能装下67个半径为1的等球.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄文奇	华中科技大学计算机科学与技术学院	88	1090	21.0	27.0
2	余亮	华中科技大学计算机科学与技术学院	19	15	3.0	3.0