求解不等圆Packing问题的一个启发式算法

摘要：

求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将待布局圆按半径大小降序排列,然后用占角动作来逐个放置.通过试探性地放入一个或多个待布局圆,给出了占角动作的度以及更全局的有限枚举策略来评价占角动作的优度.在放置每一个圆时,以贪心的方式选取当前具有最大优度的占角动作来放置.最后用测试算例验证了算法的高效性.

关键词：NP难问题、圆形packing问题、启发式算法、占角动作、有限枚举策略

所属期刊栏目：44

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金10471051;国家重点基础研究发展计划973计划2004CB318000;国家科技支撑计划重点基金2006BAK11B01

在线出版日期：2008-03-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：2092-2097