版权所有：内蒙古大学图书馆 技术提供：维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
求解不等圆Packing问题的一个启发式算法
A Heuristic Algorithm for the Unequal Circle Packing Problem作者机构：华中师范大学教育信息技术工程研究中心武汉430079 华中科技大学计算机科学与技术学院武汉430074
出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)
年 卷 期：2007年第44卷第12期
页 面：2092-2097页
核心收录：
学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）]
基 金：国家自然科学基金项目(10471051) 国家"九七三"重点基础研究发展规划基金项目(2004CB318000) "十一五"国家科技支撑计划重点基金项目(2006BAK11B01)
主 题：NP难问题 圆形packing问题 启发式算法 占角动作 有限枚举策略
摘 要：求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将待布局圆按半径大小降序排列,然后用占角动作来逐个放置.通过试探性地放入一个或多个待布局圆,给出了占角动作的度以及更全局的有限枚举策略来评价占角动作的优度.在放置每一个圆时,以贪心的方式选取当前具有最大优度的占角动作来放置.最后用测试算例验证了算法的高效性.
