| 基于动作空间求解二维矩形Packing问题的高效算法? |
| |
| 引用本文： | 何琨,黄文奇,金燕.基于动作空间求解二维矩形Packing问题的高效算法?[J].软件学报,2013(5). |
| |
| 作者姓名： | 何琨 黄文奇 金燕 |
| |
| 作者单位： | 华中科技大学 计算机科学与技术学院,湖北 武汉,430074 |
| |
| 摘 要： | 对于二维矩形Packing这一典型的NP难度问题，在黄文奇等人提出的拟人型穴度算法的基础上，通过定义动作空间来简化对不同放入动作的评价，使穴度的计算时间明显缩短，从而使算法能够快速地得到空间利用率较高的布局图案。实验测试了Hopper和Turton提出的21个著名的二维矩形Packing问题的实例。改进的算法对其中的每一个实例都得到了空间利用率为100%的最优布局，且在普通PC机上的平均计算时间未超过7分钟。实验结果表明，基于动作空间对拟人型穴度算法所进行的改进是明显而有效的。
|
| 关 键 词： | NP难度 矩形Packing 拟人 动作空间 穴度 |
Efficient Algorithm Based on Action Space for Solving the 2D Rectangular Packing Problem |
| |
| HE Kun
,
HUANG Wen-Qi
,
JIN Yan.Efficient Algorithm Based on Action Space for Solving the 2D Rectangular Packing Problem[J].Journal of Software,2013(5). |
| |
| Authors: | HE Kun HUANG Wen-Qi JIN Yan |
| |
| Abstract: | |
| |
| Keywords: | NP hard rectangular packing quasi-human action space caving degree |
| 本文献已被 万方数据 等数据库收录！ |
