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

摘要：

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

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

所属期刊栏目：24

分类号：TP391(计算技术、计算机技术)

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

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

页数：共8页

页码：808-815