A New Quasi-Human Algorithm for Solving the Packing Problem of Unit Equilateral Triangles. (5th August 2014)

• Record Type: Journal Article
• Authors: Wang, Ruimin; Qi, Xiaozhuo; Luo, Yuqiang; Dong, Jianqiang
• Other Names: Wang Zidong Academic Editor.
• Is Part Of: Abstract and applied analysis. Volume 2014(2014)
• Publication Date: 2014-08-05
• Subjects: Mathematical analysis -- Periodicals; Mathematical analysis; Applied Mathematics; Mathematical Analysis; Periodicals; 515.05
• DOI: 10.1155/2014/308474
• Languages: English
• ISSNs: 1085-3375

Abstract

Abstract : The packing problem of unit equilateral triangles not only has the theoretical significance but also offers broad prospects in material processing and network resource optimization. Because this problem is nondeterministic polynomial (NP) hard and has the feature of continuity, it is necessary to limit the placements of unit equilateral triangles before optimizing and obtaining approximate solution (e.g., the unit equilateral triangles are not allowed to be rotated). This paper adopts a new quasi-human strategy to study the packing problem of unit equilateral triangles. Some new concepts are put forward such as side-clinging action, and an approximation algorithm for solving the addressed problem is designed. Time complexity analysis and the calculation results indicate that the proposed method is a polynomial time algorithm, which provides the possibility to solve the packing problem of arbitrary triangles.