求解三角形Packing问题的占角算法  

A Full-angle Algorithm for Solving the Triangles Packing Problem

作　　者：王瑞民[1] 陈卓[2] 

机构地区：[1]郑州大学信息工程学院,河南郑州450052 [2]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《郑州大学学报（工学版）》2004年第4期52-55,共4页Journal of Zhengzhou University（Engineering Science）

摘　　要：三角形Packing问题是NP难的,其完整算法的时间复杂度是指数型的.建立了求解三角形Pack ing问题的数学模型;沿着拟人的途径,通过把待解决的问题与人类的社会经验作对比,得到了求解三角形Packing问题的若干拟人策略,并以此策略为基础发展出一种高效的近似求解算法.实验结果表明,沿此途径得出的求解三角形Packing问题的算法,针对三角形数目较多的情况,具有较好的完整性和较低的时间复杂度.The triangles packing problem is NP-hard. The complexity of their accurate algorithm is exponential. Personificaion approach is an which draws on analogy between the resolving problem and some social phenomena. According to personification approach, some strategies for tackling the triangles packing problem are presented and two highly efficient approximate algorithms have been developed based on these strategies. The result of our tests explains that the algorithm to solve the triangles packing problem by using personification approach is of high efficiently and low complexity.

关 键 词：三角形 PACKING问题 占角算法 时间复杂度 拟人思想 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]