| 用嵌套插队算法解决TSP问题 |
| |
| 引用本文： | 翟东海,靳蕃. 用嵌套插队算法解决TSP问题[J]. 运筹与管理, 2003, 12(4): 49-54 |
| |
| 作者姓名： | 翟东海 靳蕃 |
| |
| 作者单位： | 西南交通大学,计算机与通信工程学院,四川,成都,610031 |
| |
| 摘 要： | 本提出了一种求解TSP问题的近似算法—嵌套插队算法。这种算法结合了启发式算法和随机化算法以及局部寻优的思想。实验结果表明对于较小规模的。TSP问题，直接用插队算法(QJA)就能以很大的概率获得已知最优解。对于规模较大的问题实例。嵌套插队算法(NQJA)能获得质量高于名的启发式算法的解。另外，用嵌套插队算法找到的China144的最短路径优于目前已知的最短路径。嵌套插队算法是专门针对TSP问题而提出的，但其思想也可以给求解其他NP难解的组合优化问题以启发。
|
| 关 键 词： | 嵌套插队算法 TSP问题 启发式算法 随机化算法 最短路径 最优解 组合优化 旅行商问题 |
| 文章编号： | 1007-3221(2003)04-0049-06 |
| 修稿时间： | 2002-11-15 |
Nested Queue-jumping Algorithm for Traveling Salesman Problem |
| |
| Abstract: | |
| |
| Keywords: | traveling salesman problem queue-jumping algorithm nested queue-jumping algorithm randomized algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
