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

• 作者: 何琨 金燕 黄文奇
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: NP难度 矩形Packing 拟人 动作空间 穴度
• 年，卷（期）: 2012,（5）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 1037-1044
• 分类号: TP301
• 字数: 4105字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2012.03986

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄文奇	华中科技大学计算机科学与技术学院	88	1090	21.0	27.0
2	金燕	华中科技大学计算机科学与技术学院	5	59	3.0	5.0
3	何琨	华中科技大学计算机科学与技术学院	31	263	10.0	16.0