| A heuristic method for solving triangle packing problem |
| |
| 作者姓名： | 陈传波 何大华 |
| |
| 摘 要： | INTRODUCTION Most packing problems (Dowsland and Dow-sland, 1992) are NP-hard (Garey and Johnson, 1979); among which are bin-packing, floorplan, rectangle packing, packing a set of circles into a large circle or square, non-rectangular packing problems and so on (Li and Milenkovic, 1995; Liang et al., 2002; Lip-nitskii, 2002; Milenkovic and Daniels, 1996; Milenk-ovic et al., 1991; Osogami and Okano, 2003; Wang, 2002). Some of these such as bin-packing problem and rectangle packing p…
|
| 关 键 词： | 三角形包装问题 刚性放置 最小破坏性 策略 数据备份 |
| 收稿时间： | 11 June 2004 |
| 修稿时间： | 20 October 2004 |
A heuristic method for solving triangle packing problem |
| |
| Chen Chuan-bo,He Da-hua.A heuristic method for solving triangle packing problem[J].Journal of Zhejiang University Science,2005,6(6):565-570. |
| |
| Authors: | Chen Chuan-bo He Da-hua |
| |
| Institution: | (1) College of Computer Science & Technology, Huazhong University of Science & Technology, 430074 Wuhan, China |
| |
| Abstract: | Given a set of triangles and a rectangle container, the triangle packing problem is to determine ifthese triangles can be placed into the container without overlapping. Triangle packing problem is a special case of polygon packing problem and also NP-hard, so it is unlikely that an efficient and exact algorithm can be developed to solve this problem. In this paper, a new concept of rigid placement is proposed, based on which a discrete solution space called rigid solution space is constructed. Each solution in the rigid solution space can be built by continuously applying legal rigid placements one by one until all the triangles are placed into the rectangle container without overlapping. The proposed Least-Destruction-First (LDF) strategy determines which rigid placement has the privilege to go into the rectangle container. Based on this, a heuristic algorithm is proposed to solve the problem.Combining Least-Destruction-First strategy with backtracking, the corresponding backtracking algorithm is proposed. Computational results show that our proposed algorithms are efficient and robust. With slight modification, these techniques can be conveniently used for solving polygon packing problem. |
| |
| Keywords: | Triangle packing problem Rigid placement Flexibility Destruction Least-Destruction-First (LDF) strategy Backtracking |
| 本文献已被 万方数据 SpringerLink 等数据库收录！ |
|
