《计算机学报》文章摘要   全文下载
文章题目	求解旅行商问题的循环局部搜索算法的运行时间和性能分布分析
作者	邹鹏1) 周智1) 江贺1) 陈国良1) 顾钧1),2)
作者单位	1)(中国科学技术大学计算机科学技术系国家高性能计算中心(合肥) 合肥 230027) 2)(香港科技大学计算机科学与技术系 香港)
发表年份	2006
发表月份	1期 (92—99)
文章摘要	摘要 旅行商问题(Traveling Salesman Problem，TSP)是组合优化中最典型的NP难问题之一，长期以来人们都在寻求快速高效的近似算法以在合理的计算时间内准确地解决大规模问题，并设计出许多高效实用的启发式和宏启发式算法，其中循环LK算法是性能最好和最具代表性的算法之一.作者研究了该算法的运行时间分布：通过对TSPLIB中大量不同规模的TSP实例的运行时间分布的统计分析和拟合，发现求解TSP问题的循环LK算法的运行时间分布很好地服从Weibull分布，并进一步给出了该分布对求解TSP问题的物理意义.作者同时首次给出了循环LK算法求解TSP问题得到的解的性能分布以及由此得到的一些有实际指导意义的结论. 关键词 旅行商；循环LK算法；运行时间分布；解的性能分布；Weibull分布 中图法分类号 TP301