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

作者：刘景发 张国建 刘文杰 高泽旭 周子铃等圆packing问题模拟退火算法启发式格局更新策略梯度法二分法

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

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社