一种解决矩形布局问题的启发式快速算法

• 作者: 王石
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 装填问题 阶梯式 启发式 矩形排样
• 年，卷（期）: 2011,（3）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 36-39,43
• 分类号: TP301.6
• 字数: 3754字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2011.03.009

摘要

针对二维矩形Packing问题,提出了一种沿阶梯线轮廓进行布局矩形的启发式算法.该算法基于"阶梯式堆码"的启发式规则,能够快速地对矩形块进行紧靠布局.为避免算法陷入局部最优,算法采用随机回溯策略在选择矩形和阶位上扩大搜索范围.结果表明,算法对于浪费面积为零的矩形全Packing问题,能够在极短的时间内找到最优解,同时它也可以很好地求解非零浪费问题.采用国际公认的两个算例进行测试,证明文中算法是非常高效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王石	华中科技大学软件学院	3	11	2.0	3.0