用嵌套插队算法解决旅行推销员问题(英文)

摘要

提出了一种求解 TSP问题的近似算法—嵌套插队算法。这种算法结合了启发式算法和随机化算法以及局部寻优的思想。实验结果表明对于较小规模的 TSP问题 ,直接用插队算法 ( QJA)就能以很大的概率获得已知最优解。对于规模较大的 TSP问题 ,嵌套插队算法 ( NQJA)能获得质量高于著名的启发式算法的解。另外 ,用嵌套插队算法找到的 China144的最短路径优于目前已知的最短路径。嵌套插队算法是专门针对 TSP问题而提出的 ,但其思想也可以给求解其他