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

A HEURISTIC ALGORITHM FOR SOLVING THE DISKS PACKING PROBLEM

求解ＮＰ难度问题一直是计算机科学技术中的一个瓶颈任务．自２０世纪７０年代以来的研究表明，求解ＮＰ难度问题不存在既完整严格又不太慢的求解算法．因此，近年来，启发式方法成为研究热点．圆形Ｐａｃｋｉｎｇ问题是ＮＰ难的，具有很高的理论和实践价值．它的求解目标是寻求多个圆在一个大圆内的一个优良布局，使得这些圆互不重叠地放置．基于拟物法以及适者生存的启发式思想，为圆形Ｐａｃｋｉｎｇ问题的快速求解提出了一个高效的启发式算法．算法的高效性通过计算实例得到了验证．

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.