|
扩展功能
|
|
| 本文信息 | |
 |
补充材料 |
|
PDF(807KB) |
|
[HTML全文] |
|
参考文献 |
| 服务与反馈 | |
|
加入引用管理器 |
|
引用本文 |
|
Email Alert |
|
文章反馈 |
|
浏览反馈信息 |
| 本文关键词相关文章 | |
|
Packing问题 |
|
NP难度 |
|
启发式算法 |
|
拟人方法 |
|
穴度 |
| 本文作者相关文章 | |
|
黄文奇 |
|
何琨 |
| PubMed | |
|
Article by Huang, W. A. |
|
Article by H. K. |
求解长方体Packing问题的纯粹拟人算法
黄文奇, 何琨
华中科技大学计算机科学与技术学院, 武汉,430074
于具有NP难度的长方体Packing问题, 挖掘出了中国古代谚语``金角银边草肚皮''中隐藏的智慧, 并进一步发展出新子句``价值最高钻石穴''. 在利用现代西方的先进数学工具经过确切化、完整化与形式化后, 得出了一种纯粹拟人型的求解算法. 试算了国际上公开通行的两组有代表性的算例(benchmark). 对于100个强异构型的困难算例, 所得布局图案达到了87.31%的平均空间利用率, 刷新了当今国际上的最好纪录, 将它提高了1.83个百分点. 对于47个无方向约束的困难算例, 得到了92.05%的平均空间利用率, 将当今国际上的最好纪录提高了1.05个百分点.
国家自然科学基金(批准号: 60773194)、国家重点基础研究发展计划(批准号: 2004CB318000)和中国博士后科学基金(批准号: 20070420174)资助项目