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

• 作者: 陈端兵 黄文奇
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 矩形packing 贪心算法 占角动作
• 年，卷（期）: 2007,（4）
• 所属期刊栏目: 人工智能及识别技术
• 页码范围: 160-162
• 页数: 3页
• 分类号: TP301.06
• 字数: 3306字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2007.04.055

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄文奇	华中科技大学计算机科学与技术学院	88	1090	21.0	27.0
2	陈端兵	华中科技大学计算机科学与技术学院	6	110	6.0	6.0