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

• 作者: 翟东海 靳蕃
• 来源期刊: 重庆邮电学院学报(自然科学版)
• 学科: 工学
• 关键词: TSP问题 插队算法 嵌套插队算法 随机化算法
• 年，卷（期）: 2003,（3）
• 所属期刊栏目: 学术论文
• 页码范围: 51-56
• 页数: 6页
• 分类号: TP301.6
• 字数: 385字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-825X.2003.03.013

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	靳蕃	西南交通大学计算机与通信工程学院	56	954	14.0	29.0
2	翟东海	西南交通大学计算机与通信工程学院	45	285	9.0	14.0