[1]王石.一种解决矩形布局问题的启发式快速算法[J].计算机技术与发展,2011,(03):36-39.
WANG Shi.A Fast Heuristic Algorithm for Solving Rectangle Packing Problem[J].,2011,(03):36-39.
点击复制
一种解决矩形布局问题的启发式快速算法(
)
《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]
- 卷:
-
- 期数:
-
2011年03期
- 页码:
-
36-39
- 栏目:
-
智能、算法、系统工程
- 出版日期:
-
1900-01-01
文章信息/Info
- Title:
-
A Fast Heuristic Algorithm for Solving Rectangle Packing Problem
- 文章编号:
-
1673-629X（2011）03-0036-04
- 作者:
-
王石
-
华中科技大学软件学院
- Author(s):
-
WANG Shi
-
School of Software Engineering, Huazhong University of Science and Technology
-
- 关键词:
-
装填问题; 阶梯式; 启发式; 矩形排样
- Keywords:
-
pacldng; steplike; heuristic algorithm; rectangle packing problem
- 分类号:
-
TP301.6
- 文献标志码:
-
A
- 摘要:
-
针对二维矩形Packing问题，提出了一种沿阶梯线轮廓进行布局矩形的启发式算法。该算法基于“阶梯式堆码”的启发式规则，能够快速地对矩形块进行紧靠布局。为避免算法陷入局部最优，算法采用随机回溯策略在选择矩形和阶位上扩大搜索范围。结果表明，算法对于浪费面积为零的矩形全Packing问题，能够在极短的时间内找到最优解，同时它也可以很好地求解非零浪费问题。采用国际公认的两个算例进行测试，证明文中算法是非常高效的
- Abstract:
-
A steplike stacking algorithm was proposed to solving 2D rectangular packing problem. The algorithm was based on a steplike heuristic rule and probabilistic backtracking algorithm. For the zero-wasted problem, the algorithm spends less on finding the optimal solution than other methods. It also demonstrated fairly good performance on solving none-zero-waste problems. Two well known test cases were executed, and verified that our proposed algorithm was very effective
备注/Memo
- 备注/Memo:
-
国家自然科学基金资助项目（60073045）王石（1977-），男，硕士，CCF会员，研究方向为启发式算法、软件工程、教育信息化等
更新日期/Last Update:
1900-01-01