求解TSP问题的多级归约算法

• 作者: 周智 邹鹏 陈国良 顾钧
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: TSP(traveling salesman problem) NP-hard 部分解 归约 多级归约算法
• 年，卷（期）: 2003,（1）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 35-42
• 页数: 8页
• 分类号: TP301
• 字数: 4864字
• 语种: 中文

摘要

TSP(traveling salesman problem)问题是最经典的NP-hard组合优化问题之一.长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的计算时间内解决大规模问题.由于对较大规模的问题,目前的近似算法尚不能在较短的时间内给出高质量的解,因此提出了多重归约算法.该算法的基本原理是通过对TSP问题的局部最优解与全局最优解之间关系的分析,发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解.利用这些部分解可以大大缩小原问题的搜索空间,同时也不会降低搜索的性能.这就是所谓的归约原理.再通过多次归约使问题的规模降到足够小,然后对这个较小规模的实例直接用已有的算法求解,最后通过相反的次序拼接部分解,最终得到一个合法的解.在TSPLIB(traveling salesman problem library)中,典型实例上的实验结果表明,此算法在求解质量和求解速度上与目前已知的算法相比有较大的改进.