| 求解旅行商问题的循环局部搜索算法的运行时间和性能分布分析 |
| |
| 引用本文： | 邹鹏,周智,江贺,陈国良,顾钧.求解旅行商问题的循环局部搜索算法的运行时间和性能分布分析[J].计算机学报,2006,29(1):92-99. |
| |
| 作者姓名： | 邹鹏 周智 江贺 陈国良 顾钧 |
| |
| 作者单位： | 1. 中国科学技术大学计算机科学技术系国家高性能计算中心(合肥),合肥,230027
2. 中国科学技术大学计算机科学技术系国家高性能计算中心(合肥),合肥,230027;香港科技大学计算机科学与技术系,香港 |
| |
| 摘 要： | 旅行商问题（Traveling Salesman Problem，TSP）是组合优化中最典型的NP难问题之一，长期以来人们都在寻求快速高效的近似算法以在合理的计算时间内准确地解决大规模问题，并设计出许多高效实用的启发式和宏启发式算法，其中循环LK算法是性能最好和最具代表性的算法之一．作者研究了该算法的运行时间分布：通过对TSPLIB中大量不同规模的TSP实例的运行时间分布的统计分析和拟合，发现求解TSP问题的循环LK算法的运行时间分布很好地服从Weibull分布，并进一步给出了该分布对求解TSP问题的物理意义．作者同时首次给出了循环LK算法求解TSP问题得到的解的性能分布以及由此得到的一些有实际指导意义的结论．
|
| 关 键 词： | 旅行商 循环LK算法 运行时间分布 解的性能分布 weibull分布 |
| 收稿时间： | 2003-08-28 |
| 修稿时间： | 2003-08-282005-10-09 |
Analysis of the Run-Time Distribution and Solution Performance Distribution of Iterated Local Search for the TSP |
| |
| ZOU Peng,ZHOU Zhi,JIANG He,CHEN Guo-Liang,GU Jun.Analysis of the Run-Time Distribution and Solution Performance Distribution of Iterated Local Search for the TSP[J].Chinese Journal of Computers,2006,29(1):92-99. |
| |
| Authors: | ZOU Peng ZHOU Zhi JIANG He CHEN Guo-Liang GU Jun |
| |
| Affiliation: | 1.National High Performance Computing Center at Hefei , Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027; 2.Department of Computer Science and Technology, Hong Kong University of Science and Technology, Hong Kong |
| |
| Abstract: | |
| |
| Keywords: | TSP iterated Lin-Kernighan algorithm RTDs SPDs Weibull distribution |
| 本文献已被 维普 万方数据 等数据库收录！ |
