A Quasi-Physical-Society Algorithm For Solving Congruent Circles Packing Problem

The congruent circles packing problem is a representational Np-hard problem. With the experience of the nature and the human society , we designed an algorithm which can solve this problem effectively. We call it Quasi-Physical-Society algorithm.The method of Quasi-Physical algorithm is opposite to the method of mathematics model .At first , it translates a mathematics problem to a physical problem .Then solve it with the rule of nature . Finally, translate the solution of the physical problem to the solution of the initial mathematics problem . In order to solve the congruent circles packing problem, we imported the concept of elasticity and search the solution automatically under the influence of elasticity.Moreover, we designed an"euthanasia"method in order to improve efficiency .While executing the Quasi-Physical algorithm , we estimate the possibility of obtaining the solution constantly . If the possibility is too small, we stop current searching path immediately and startup a new searching path .Using this method, we can avoid a lot of unnecessary calculation and save a lot of time .If the instance if very difficult to solve , using sheer Quasi-physical algorithm always plunges into"local minimum", we must strive to jump off the"local minimum".By observing the phenomena of human society, we designed a series of method to jump off the"local minimum". We call them Quasi-Society algorithms, such as"remove the most anguished one","rescue the most anguished one","global adjust"etc. On most instance,"rescue the most anguished one"performs more effectively than"remove the most anguished one".Using less time than most other algorithms, our algorithm reached the advanced international level on 79 examples of 100 examples(N=1—100).