A Complete Quasi-physcial Algorithm For The Congruent Circles Packing Problem

NP hard problems are the most difficult problems in computer science.Even in highly civilized today,we are not able to present a rigid and high efficient solving algorithm for NP hard problems.However,there are lots of NP hard problems in every aspect of our lives,they have become the bottleneck of technological development. For computer scientist and mathematicians,how to solve NP hard problems is an engaging challenge in the 21st century.Congruent circles packing problem is the simplest and the most natural one of all the NP hard problems.It is about how to place without overlap N unit circles into a smallest possible circular container.The goodness of the answer is decided by the radius of the circular container R_n,the smaller the better.The congruent circles packing problem is a simplified description of some real packing problems.More importantly,it is the simplest and the most natural target when we attack NP hard problems.The congruent circles packing problem is now widely regarded as the most natural touchstone of efficient algorithms on solving NP hard problems.After 20 years of hard work,the famous American mathematician R.L.Graham and hundreds of his followers have tested various algorithms on the congruent circles packing problem.They revealed the best known results they found.For every specific N(N=1,2,…,100),they presented a densest known packing diagram and a corresponding smallest R_n.Our work is that,we designed an unitary algorithm and tested it on the best known packing records.For N=66,67,70,71,73,77,89,99,we found better packing diagrams, the radius of the circular container of every case is reduced by 10^-5-10^-3Our approach is an improved quasi-physical method.When the basic quasiphysical descent algorithm gets stuck at a local optima,we add some strong,longdistance attraction or repulsion forces into the algorithm.Driven by these strong forces,all circles will undergo a period of violent movement,and the computation will jump out the local optima trap.The deficiency of the original quasi-physical method is that when the computation gets stuck at a local optima,the original method can not do anything except calling some quasi-human strategy.But it is really a hard task to think out some useful quasi-human strategy,and sometimes the quasi-human strategy also seems to be too artificial.In the improved quasi-physical algorithm,both the descent algorithm and the jump-out-trap algorithm are physically inspired,so it can be called as "a complete quasi-physical algorithm".