正三角形容器内等圆Packing问题的启发式算法

作     者：刘景发 张国建 刘文杰 高泽旭 周子铃 Liu Jingfa;Zhang Guojian;Liu Wenjie;Gao Zexu;Zhou Ziling

作者机构：南京信息工程大学网络信息中心南京210044 南京信息工程大学计算机与软件学院南京210044 

基　　金：江苏省博士后科研资助计划(1001030B) 江苏省自然科学基金(BK2010570) 中国博士后科学基金特别资助(201104572) 江苏省高校自然科学研究项目(09 KJB520008) 江苏省"青蓝工程"项目 

出 版 物：《计算机辅助设计与图形学学报》 (Journal of Computer-Aided Design & Computer Graphics)

年 卷 期：2012年第24卷第6期

页      码：808-815页

摘      要：等圆Packing问题研究如何将n个单位半径的圆形物体互不嵌入地置入一个边长尽量小的正三角形容器内,作为一类经典的NP难度问题,其有着重要的理论价值和广泛的应用背景.模拟退火算法是一种随机的全局寻优算法,通过将启发式格局更新策略与基于梯度法的局部搜索策略融入模拟退火算法,并与二分搜索相结合,提出一种求解正三角形容器内等圆Packing问题的启发式算法.该算法将启发式格局更新策略用来产生新格局和跳坑,用梯度法搜索新产生格局附近能量更低的格局,并用二分搜索得到正三角形容器的最小边长.对41个算例进行测试的实验结果表明,文中算法改进了其中38个实例的目前最优结果,是求解正三角形容器内等圆Packing问题的一种有效算法.

主 题 词：等圆Packing问题 模拟退火算法 启发式格局更新策略 梯度法 二分法 

学科分类：081203[081203] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1003-9775.2012.06.015

馆 藏 号：203134402...