求解长方体Packing问题的纯粹拟人算法

摘要：

对于具有NP难度的长方体Packing问题,挖掘出了中国古代谚语"金角银边草肚皮"中隐藏的智慧,并进一步发展出新子句"价值最高钻石穴".在利用现代西方的先进数学工具经过确切化、完整化与形式化后,得出了一种纯粹拟人型的求解算法.试算了国际上公开通行的两组有代表性的算例(benchmark).对于100个强异构型的困难算例,所得布局图案达到了87.31%的平均空间利用率,刷新了当今国际上的最好纪录,将它提高了1.83个百分点.对于47个无方向约束的困难算例,得到了92.05%的平均空问利用率,将当今国际上的最好纪录提高了1.05个百分点.

关键词：Packing问题、NP难度、启发式算法、拟人方法、穴度

所属期刊栏目：39

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金;国家重点基础研究发展计划（973计划）;中国博士后科学基金

在线出版日期：2010-07-12（万方平台首次上网日期，不代表论文的发表时间）

页码：617-622