求解圆形packing问题的一个快速拟物算法  

A Fast Quasi-physical Algorithm for the Disks Packing Problem

作　　者：康雁[1] 黄文奇[2] 

机构地区：[1]云南大学软件学院,昆明650091 [2]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机工程与应用》2003年第35期30-32,共3页Computer Engineering and Applications

基　　金：国家973基础研究发展规划项目基金资助(编号:G1998030600)

摘　　要：求解NP难问题一直是计算机科学技术中的一个瓶颈任务。自20世纪70年代以来的研究表明,不存在求解此类问题的完整严格的有效算法。因此用启发式方法求解成为当今研究的一个热点。圆形packing问题是一个有着很高理论和实用价值的NP难问题。该文提出了一些有效的搜索策略,得到了一个求解它的快速有效启发式算法。最后用计算实例验证了此算法的有效性,计算结果表明此算法明显优于已有快速算法。Solving NP hard problems is always the bottleneck task for computer science and techniques.Investigations from the1970s to now show that there does not exist an exactly effective algorithm that can provide an optimal solu-tion for NP-hard problems within a reasonable time limit.In recent years,people turn to obtain heuristic methods for solving NP hard problems.The disks packing problem is of high theoretical and practical value.In this paper,a fast heuristic method is presented by using efficient search strategies.A lot of computational experiments demonstrate the ef-fectiveness of this algorithm.

关 键 词：圆形PACKING问题 拟物方法 NP难度 启发式方法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]