| 旅行商问题的近优解评价方法--浅析启发式算法的有效性 |
| |
| 引用本文： | 苏丽杰,聂义勇. 旅行商问题的近优解评价方法--浅析启发式算法的有效性[J]. 计算机科学, 2004, 31(Z2): 310-311 |
| |
| 作者姓名： | 苏丽杰 聂义勇 |
| |
| 作者单位： | 1. 中科院沈阳自动化所,沈阳,110016;中科院研究生院,北京,100039;东北大学理学院,沈阳,110004
2. 中科院沈阳自动化所,沈阳,110016;中科院研究生院,北京,100039 |
| |
| 摘 要： | 1引言旅行商问题(Traveling Salesman Problem,TSP)的描述如下:给定N个城市,已知它们之间的距离矩阵,寻求一条经过所有城市一次且仅一次的最短Hamilton回路.TSP已被证明属于NP完全问题,由于启发式算法具有计算复杂性与算法所得近优解的"质量"折中性好的特点,它在TSP算法的研究中占有重要的地位[1],启发式算法的有效性表现在两方面:一是计算复杂性低,二是近优解"质量"高.启发式算法的上界收敛性,即准收敛性的研究是评价启发式算法的一个重要问题.本文以评价近优解为中心,通过总结、归纳已有方法,整理各种典型算法的评价结果,对现有方法的适用范围和评价结果的意义作了分析讨论,其结论对于改善现有算法以及评价新算法有一定的指导作用.启发式算法的准收敛性仍旧是一个正在研究中的问题.
|
Evaluation on Near-Optimal Solution of Traveling Salesman Problem--Efficiency of Heuristic Algorithm |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
