求解圆形Packing问题的一个启发式算法  

A HEURISTIC ALGORITHM FOR SOLVING THE DISKS PACKING PROBLEM

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

机构地区：[1]中国科学院软件研究所,北京100080 [2]华中科学技术大学计算机科学与技术学院,武汉430074

出　　处：《计算机研究与发展》2002年第4期410-414,共5页Journal of Computer Research and Development

摘　　要：求解ＮＰ难度问题一直是计算机科学技术中的一个瓶颈任务．自２０世纪７０年代以来的研究表明，求解ＮＰ难度问题不存在既完整严格又不太慢的求解算法．因此，近年来，启发式方法成为研究热点．圆形Ｐａｃｋｉｎｇ问题是ＮＰ难的，具有很高的理论和实践价值．它的求解目标是寻求多个圆在一个大圆内的一个优良布局，使得这些圆互不重叠地放置．基于拟物法以及适者生存的启发式思想，为圆形Ｐａｃｋｉｎｇ问题的快速求解提出了一个高效的启发式算法．算法的高效性通过计算实例得到了验证．Solving NP hard problems is always the bottleneck task for computer science and techniques. Investigations from the 1970s to now show that for NP hard problems, there does not exist an algorithm that is both complete and rigorous and not too slow. In recent years, people turn to obtain heuristic methods for solving NP hard problems. The disks packing problem, one of the NP hard problems, is of high theoretical and practical value. Given a fixed set of disks and a larger circle, the disks packing problem is to find a good layout by packing disks without overlap entirely inside a larger circle. The quasi-physical method solves the problem by imitating the movement of smooth elastic disks in a circular container. A heuristic idea which is inspired by the law of 'the survival of the fittest' in the nature is presented by increasing the utilization of the good layouts. On the basis of the quasi-physical method and the heuristic idea, a heuristic algorithm of high effectiveness is presented. The solution to the disks packing problem can be obtained quickly by applying this algorithm, and the performance of the algorithm is verified by the calculation results.

关 键 词：圆形PACKING问题 启发式算法 NP难度问题 计算机 

分 类 号：O22[理学—运筹学与控制论] TP301.6[理学—数学]