The Heuristic Methods For The Disks Packing Problem

Now there does not exist an exactly effective method that can always provide an optimal solution for NP-hard problems within a reasonable time limit. Inspired by the wisdom of the nature and the human society, we present heuristic methods to effectively provide approximate solutions to one of the NP-hard problems, the disks packing problem.Most of our work was done as follows:Firstly, a fast quasi-physical and quasi-human algorithm, which can effectively provide approximate solutions to the disks packing problem, is obtained. The performance of this algorithm is obviously better than the best algorithm obtained so far. This algorithm's computational speeds on the difficult instances are between 10 and 100 times faster than those of the best algorithm, on the condition of keeping the quality of the solutions same.Secondly, inspired by the movement rule of the elastic objects of the physical world, a strategy that predicts the prospect of the search is obtained. It improves the performance of the search by early stopping the search that will get trapped in local minima; Inspired by the survival of the fittest principle of the nature, another strategy lets the search escape from local minima to the direction of better prospect by using the wisdom that human has accumulated in social events. The fast quasi-physical and quasi-human algorithm is obtained as the integration of the above two methods and the quasi-physical and quasi-human algorithm.Thirdly, based on simulating the elastic objects movement, two heuristic algorithms are presented by using the idea of the simulated annealing algorithm. By accepting the new solution, whose quality is not better than the previous one, according to the different rules, the above two algorithms are possible to let the search escape from local minima and thus effectively solve the equal disks packing problem.Finally, by effectively using obtained heuristic methods to solve a lot of instances, we study the working principle of the heuristic methods, and present a feasible plan to design the heuristic methods.