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

Heuristic algorithm based on taboo search for sphere Packing problem

作　　者：刘景发[1,2] 周国城[2] 潘锦基[2] 

机构地区：[1]南京信息工程大学网络信息中心,南京210044 [2]南京信息工程大学计算机与软件学院,南京210044

出　　处：《计算机应用研究》2011年第3期892-894,共3页Application Research of Computers

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

摘　　要：为求解具有NP难度的球体Packing问题,通过将禁忌搜索方法与基于自适应步长的梯度下降法和二分法相结合,提出了一个启发式算法。对50个等球算例进行了实例测试,算法改进了其中44个算例的目前最优结果。大量的实例计算结果表明,该启发式算法是求解球体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.

关 键 词：球体Packing问题 启发式算法 禁忌搜索算法 梯度下降法 二分法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]