基于动作空间求解二维矩形Packing问题的高效算法

摘要：

对于二维矩形Packing这一典型的NP难度问题,在黄文奇等人提出的拟人型穴度算法的基础上,通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法能够快速地得到空间利用率较高的布局图案.实验测试了Hopper和Turton提出的21个著名的二维矩形Packing问题的实例.改进的算法对其中的每一个实例都得到了空间利用率为100％的最优布局,且在普通PC机上的平均计算时间未超过7分钟.实验结果表明,基于动作空间对拟人型穴度算法所进行的改进是明显而有效的.

关键词：NP难度、矩形Packing、拟人、动作空间、穴度

所属期刊栏目：34

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

资助基金：国家自然科学基金60773194

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

页数：共8页

页码：1037-1044