摘要
沿着拟物的思路进一步研究了具有NP难度的等圆Packing问题. 提出了两个拟物策略,第一个是拟物下降算法,第二是让诸圆饼在某种物理定律下做剧烈运动. 结合这两个策略,提出了一个统一的拟物算法. 当使用$N(N=1,2,3,...,100) 等圆最紧布局的国际记录对此算法进行检验时, 发现对于N=66,67,70,71,77,89这6个算例,本算法找到了比当前国际纪录更优的布局.
Abstract
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.
关键词
等圆Packing问题 /
NP难度 /
拟物方法 /
启发式算法.
{{custom_keyword}} /
Key words
Congruent circles packing problem /
NP hard /
quasi-physical method /
heuristic algorithm.
{{custom_keyword}} /
黄文奇
, 叶涛.
, {{custom_author.name_cn}}.
求解等圆Packing问题的完全拟物算法. 系统科学与数学, 2008, 28(8): 993-1001. https://doi.org/10.12341/jssms10193
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
中图分类号：
68W25
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
PDF(495 KB)
