The equal circles packing problem is considered by using the quasi-physical method. Two quasi-physical strategies are presented. The first one is a quasi-physical descent algorithm, and the second is to make violent movements of the circles guided by certain physical laws. By these strategies, a unitary algorithm is given to solve the congruent circles packing problem. This algorithm is tested by the famous benchmark of packing N(N=1,2,...,100) congruent circular disks into a smallest possible circular container. This benchmark is also a clear touch stone for quality of algorithm in solving famous NP-hard problems. Comparing with previously recorded best packings, better packings for N=66,67,70,71,77,89 are found.
HUANG Wenqi
, YE Tao. , {{custom_author.name_en}}.
Quasi-Physical Algorithm for the Equal Circles Packing Problem. Journal of Systems Science and Mathematical Sciences, 2008, 28(8): 993-1001 https://doi.org/10.12341/jssms10193
PDF(495 KB)
