|
|||||
|
|
| 求解长方体Packing问题的纯粹拟人算法 | |
| 作者姓名： | 黄文奇 何琨 |
| 作者单位： | 华中科技大学计算机科学与技术学院 |
| 基金项目： | 国家自然科学基金(批准号:60773194);国家重点基础研究发展计划(批准号:2004CB318000);中国博士后科学基金(批准号:20070420174)资助项目 |
| 摘 要： | 对于具有NP难度的长方体Packing问题,挖掘出了中国古代谚语"金角银边草肚皮"中隐藏的智慧,并进一步发展出新子句"价值最高钻石穴".在利用现代西方的先进数学工具经过确切化、完整化与形式化后,得出了一种纯粹拟人型的求解算法.试算了国际上公开通行的两组有代表性的算例(benchmark).对于100个强异构型的困难算例,所得布局图案达到了87.31%的平均空间利用率,刷新了当今国际上的最好纪录,将它提高了1.83个百分点.对于47个无方向约束的困难算例,得到了92.05%的平均空间利用率,将当今国际上的最好纪录提高了1.05个百分点. |
| 关 键 词： | Packing问题 NP难度 启发式算法 拟人方法 穴度 |
| 本文献已被 维普 等数据库收录！ | |