求解矩形packing问题的贪心算法

摘要：

在货物装载、木材下料、超大规模集成电路设计等工作中提出了矩形packing问题.对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法.该文利用人类的智慧及历史上形成的经验,提出了一种求解矩形packing问题的贪心算法.并对21个公开测试实例进行了实算测试,所得结果的平均面积未利用率为0.28%,平均计算时间为17.86s,并且还得到了其中8个实例的最优解.测试结果表明,该算法对求解矩形packing问题相当有效.

关键词：矩形packing、贪心算法、占角动作

所属期刊栏目：33

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

资助基金：国家自然科学基金10471051;国家重点基础研究发展计划973计划2004CB318000

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

页数：共3页

页码：160-162