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

A Heuristic Algorithm for the Unequal Circle Packing Problem

作　　者：陈矛[1] 黄文奇[2] 

机构地区：[1]华中师范大学教育信息技术工程研究中心,武汉430079 [2]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机研究与发展》2007年第12期2092-2097,共6页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(10471051);国家"九七三"重点基础研究发展规划基金项目(2004CB318000);"十一五"国家科技支撑计划重点基金项目(2006BAK11B01)~~

摘　　要：求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将待布局圆按半径大小降序排列,然后用占角动作来逐个放置.通过试探性地放入一个或多个待布局圆,给出了占角动作的度以及更全局的有限枚举策略来评价占角动作的优度.在放置每一个圆时,以贪心的方式选取当前具有最大优度的占角动作来放置.最后用测试算例验证了算法的高效性.Circle packing problem, one of the NP hard problems, is of great theoretical and practical value. To solve the circle packing problem that encounters in the field of transportation of freight, a heuristic algorithm is proposed for finding a good arrangement of multiple different-sized circles within a larger rectangular container. In this algorithm, the circles are sorted by non-increasing order of radius and packed into the container one by one according to the order. Each circle should be placed inside the container by a corner placement so that the circle does not overlap any other circle and is tangent with two previously packed circles. By pseudo-placing one or more circles to be packed, two greedy methods are introduced to evaluate the benefit of a corner placement, one of which is the degree of placement, and the other is a bounded enumeration strategy that is based on the first one. At each iteration of packing in the resulting algorithm, each circle is packed into the container by a corner placement with the highest benefit according to the bounded enumeration strategy. The experimental results are presented, showing the effectiveness of this algorithm.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]