这一篇可以当做前言来看, 主要是介绍一下TSP目前的情况

目前主流的tsp算法有三个

  1. LK算法
    1. LK基础算法, 他的思路就是交换路径上的点的顺序(就是用一段路径去替换另一段), LK本身在上世纪60年代实现了2交换, 3交换(3条路径)…
      1. L 贝尔实验室的 shen lin, 没错华裔
      2. K 贝尔实验室的brian kernighan
    2. LKH算法, 以LK交换为基础, 实现了更复杂的动态交换技术. 尝试类算法的代表和巅峰. H再上个世纪90年代实现了5交换, 后来又实现了动态交换.
      1. H keld helsgaun
      2. 动态交换最初由Applegate实现, 基于gates-papadimitriou的成果, 没错这个gates就是微软的那个bill gates, 这个成果是他念大学时做出来的, 一个本科生, 人家不要文凭, 不是因为无法毕业, 而是因为学业对他而言不够有挑战性.
    3. LK的链式算法, 顾名思义, 就是一次LK结果之后, 进行简单的随机交换(例如4交换), 然后, 再做一次LK, 简单的说就是链式调用LK. 它垄断了上个世纪90年代的路线搜寻, concorde用到了他. 10万城市, 仅需1s, 拿到1%误差的结果.
  2. 遗传算法, 选取两条路线进行配种, 例如EAX边交叉法, 两条路线A和B, 在A(妈妈)中选择一段边作为基础, 然后在A和B(爸爸)中选择线段(优先使用B)构建一条路径(可能会形成局部回路).
    1. 永田裕一采用EXA构造了非常有竞争力的方案, 他的蒙娜丽莎TSP方案非常精妙.
  3. 线性规划, 代表作品concorde 这个领域的概念和扩展都比较多, 后面专门介绍吧.

其他扎偏枪成功的算法, 这些算法虽然是为了TSP而生, 但是实际对TSP没有太多影响, 却在其他领域大放异彩.

  1. 退火算法, 作为一个通用的搜索算法, 它取得了巨大的成功.
  2. 蚁群算法, 他在时序调度, 蛋白质基因测序等等很多领域大显身手.
  3. 神经网络 neural network
  4. 禁忌搜索 tabu search
  5. 蜂群算法 honey bee

参考链接:

  • http://www.math.uwaterloo.ca/tsp/index.html
  • https://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
  • http://archive.dimacs.rutgers.edu/Challenges/TSP/
  • https://en.wikipedia.org/wiki/Travelling_salesman_problem