基于禁忌搜索的启发式算法求解球体Packing问题

摘要

To solve the sphere Packing problem which was a NP-hard problem, proposed a heuristic algorithm which combined the taboo search algorithm with the gradient descent method based on the adaptive step length and dichotomous search.Tested 50 equal sphere instances.The proposed algorithm approved the results of 44 instances obtained by previous algorithms.The computational results show that this heuristic algorithm is an effective algorithm for the sphere Packing problem.%为求解具有NP难度的球体Packing问题,通过将禁忌搜索方法与基于自适应步长的梯度下降法和二分法相结合,提出了一个启发式算法.对50个等球算例进行了实例测试,算法改进了其中44个算例的目前最优结果.大量的实例计算结果表明,该启发式算法是求解球体Packing问题的一个有效算法.