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

作者：何琨; 黄文奇; 金燕

来源：软件学报, 2013, (5): 1037-1044.

• NP难度
• 矩形Packing
• 拟人
• 动作空间
• 穴度

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

• 单位
  华中科技大学