球形容器内等球装填问题的启发式算法

• 作者: 余亮 黄文奇
• 来源期刊: 华中科技大学学报：自然科学版
• 学科: 工学
• 关键词: NP难度 等球装填问题 启发式 拟物算法 序列对称换位策略
• 年，卷（期）: 2012,（12）
• 所属期刊栏目: 计算机科学与技术
• 页码范围: 23-27
• 分类号: TP301.6
• 字数: 5219字
• 语种: 中文

摘要

为了在球形容器内紧密装填n个等球,设计了序列对称换位策略,将其与拟物算法结合得到一个有效的启发式算法.序列对称换位策略每次从一个局部最优布局出发,通过对称换位此局部最优布局的不同真子集得到n（n-1）/2个不同的新布局,并用拟物算法检查这些新布局.此启发式算法只须检查O（n2）个布局,即可找到一个紧凑的可行布局.所找到的最好结果显著改进了目前best known记录,并证否了半径为5的球形容器至多只能装填67个半径为1的等球的猜想.

作者信息

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