Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (22): 49-51.DOI: 10.3778/j.issn.1002-8331.2010.22.017

• 研究、探讨 • Previous Articles     Next Articles

Quasiphysical strategy for solving triangles Packing problem

JIA Hai-feng1,WANG Rui-min2,PEI Li-jun3   

  1. 1.Zhengzhou Infant Normal School,Zhengzhou 450002,China
    2.College of Information Engineering,Zhengzhou University,Zhengzhou 450001,China
    3.Department of Mathematics,Zhengzhou University,Zhengzhou 450001,China
  • Received:2009-05-27 Revised:2009-07-31 Online:2010-08-01 Published:2010-08-01
  • Contact: JIA Hai-feng

求解三角形Packing问题的拟物策略

贾海峰1,王瑞民2,裴利军3   

  1. 1.郑州幼儿师范学校,郑州 450002
    2.郑州大学 信息工程学院,郑州 450001
    3.郑州大学 数学系,郑州 450001
  • 通讯作者: 贾海峰

Abstract: Solving NP hard problems is always the bottleneck task for computer science and techniques.Investigations from the 1970’s to now show that for NP hard problems,these does not exist an algorithm that is both complete and rigorous and not too slow.The triangles packing problem,is one of the NP hard problems.According to physical approach,some strategies for tackling the triangles packing problem are presented and a highly efficient approximate algorithms have been developed based on two strategies.The result of the test indicates that the algorithm to solve the triangles packing problem by using quasiphysical approach is of high efficiently.

摘要: NP难度问题的求解一直是计算机科学技术的一个瓶颈任务。自20世纪70年代以来的研究结果表明,求解NP难度问题不存在既完整严格又不太慢的求解算法。三角形Packing问题是NP难的。给出了泊位的定义,并给出了求解三角形Packing问题的拟物策略。以拟物策略为基础发展出拟物算法。实验结果表明,拟物算法具有较高的完整性。

CLC Number: