求解三维矩形布局的最大穴度算法

被引：4

作者：

何琨

黄文奇

机构：

[1] 华中科技大学计算机科学与技术学院

来源：

华中科技大学学报(自然科学版) | 2008年 / 03期

基金：

中国博士后科学基金;

关键词：

NP难题; 排样; 启发式算法; 穴度; 三维矩形布局;

D O I：

10.13245/j.hust.2008.03.028

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

针对三维矩形布局问题提出了一种新的启发式算法——最大穴度算法,其主要思路是通过现代的数学工具,将人类几千年来形成的智慧予以形式化和确切化.该算法以最大穴度的动作优先放入为原则,使装入容器的长方体尽可能紧凑,从而可装入尽可能多的长方体.计算了OR-Library中无方向约束的全部47个算例,实验结果表明:该算法在合理的时间内取得了平均体积利用率为94.31%的结果,比此前报道的最好结果高3.31%.

引用

页码：92 / 94

页数：3

共 4 条

[1] 基于欧氏距离的矩形Packing问题的确定性启发式求解算法 [J].