一种求解矩形packing问题的智能枚举算法

摘要：

矩形packing问题有许多工业应用,如码头货物装载,木材下料,超大规模集成电路(VLSI)布局设计,新闻排版等.国内外已提出了许多求解此问题的算法,如:遗传算法,模拟退火算法以及启发式算法等.在目前已有研究的基础上,提出了一种智能枚举算法,该算法的关键在于设计一种快速有效的枚举策略.用Hopper和Turton提出的21个矩形packing实例对所提出的算法性能进行了实算测试,平均面积未利用率为0.04%,平均计算时间为277.69s,并求得了其中18个实例的最优解.实算结果表明:该算法对求解矩形packing问题是行之有效的.

关键词：矩形packing、NP完全、智能枚举算法、占角动作、穴度

所属期刊栏目：20

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家高技术研究发展计划06AA01Z414,07AA01Z440;国家242信息安全计划项目2007827;四川省应用技术研究与开发项目支撑计划2008GZ0009

在线出版日期：2008-09-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：447-452