| 基于禁忌搜索的启发式算法求解球体Packing问题* |
| |
| 引用本文： | 刘景发,周国城,潘锦基b.基于禁忌搜索的启发式算法求解球体Packing问题*[J].计算机应用研究,2011,28(3):892-894. |
| |
| 作者姓名： | 刘景发 周国城 潘锦基b |
| |
| 作者单位： | 1. 南京信息工程大学,网络信息中心,南京,210044;南京信息工程大学,计算机与软件学院,南京,210044
2. 南京信息工程大学,计算机与软件学院,南京,210044 |
| |
| 基金项目： | 省自然科学基金资助项目 |
| |
| 摘 要： | 为求解具有NP难度的球体Packing问题，通过将禁忌搜索方法与基于自适应步长的梯度下降法和二分法相结合，提出了一个启发式算法。对50个等球算例进行了实例测试，算法改进了其中44个算例的目前最优结果。大量的实例计算结果表明，该启发式算法是求解球体Packing问题的一个有效算法。
|
| 关 键 词： | 球体Packing问题 启发式算法 禁忌搜索算法 梯度下降法 二分法 |
| 收稿时间： | 9/2/2010 12:00:00 AM |
| 修稿时间： | 2011/1/28 0:00:00 |
Heuristic algorithm based on taboo search for sphere Packing problem |
| |
| LIU Jing-fa,ZHOU Guo-cheng,PAN Jin-jib.Heuristic algorithm based on taboo search for sphere Packing problem[J].Application Research of Computers,2011,28(3):892-894. |
| |
| Authors: | LIU Jing-fa ZHOU Guo-cheng PAN Jin-jib |
| |
| Affiliation: | (a. Network Information Center, b. College of Computer & Software, Nanjing University of Information Science & Technology, Nanjing 210044, China) |
| |
| Abstract: | To solve the sphere packing problem which is a NP-hard problem, a heuristic algorithm which combines the taboo search algorithm with the gradient descent method based on the adaptive step length and dichotomous search is proposed. 50 equal sphere instances are tested. The proposed algorithm approves 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. |
| |
| Keywords: | Sphere packing problem Heuristic algorithm Taboo search algorithm Gradient descent method dichotomous search |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
