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

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