Abstract:
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.