%0 Journal Article
%T 基于动作空间求解二维矩形packing问题的高效算法
%A 何琨？
%A 黄文奇？
%A 金燕？
%J 软件学报
%P 1037-1044
%D 2012
%R 10.3724/SP.J.1001.2012.03986
%X 对于二维矩形packing这一典型的np难度问题,在黄文奇等人提出的拟人型穴度算法的基础上,通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法能够快速地得到空间利用率较高的布局图案.实验测试了hopper和turton提出的21个著名的二维矩形packing问题的实例.改进的算法对其中的每一个实例都得到了空间利用率为100%的最优布局,且在普通pc机上的平均计算时间未超过7分钟.实验结果表明,基于动作空间对拟人型穴度算法所进行的改进是明显而有效的.
%K np
%K 难度
%K 矩形packing
%K 拟人
%K 动作空间
%K 穴度
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=3986&flag=1