旅行推销员问题

1. Introduction

旅行推销员问题(TSP):求解访问每座城市一次的最低花费路线。在此可视化中,假定基础图是一个完整的图,使用两点距离的最接近整数作为其度量距离(满足三角不等式的一个距离函数)。

2. 可视化

在这里查看TSP算法的可视化。

最初,图形中的所有边以灰色显示。

当进行可视化时,被穿过的边会高亮为橙色。

3. Input

There are two different sources for specifying an input graph:

  1. Draw Graph: You can put several points on the drawing box, but you must not draw any edge to ensure the (near-)metric property of the graph. After you have finished putting the points, the edges will be drawn automatically for you after.
  2. Example Graphs: You can select from the list of graphs to get you started.

4. 简单模式匹配算法(Bruteforce)

Bruteforce: It tries all (V-1)! permutation of vertices (not all V! since it does not matter where we start from). It enumerates all possibilities by doing a dfs search with parameters similar to those of Held-Karp algorithm, that is, the dfs search will return the value of the tour starting from current vertex to all vertices that we have not already visited.

Time complexity: O(V * (V - 1)!) = O(V!)

5. 动态编程

动态编程:这里使用了著名的Held-Karp算法。在可视化中,它被用作一种深度优先算法,就如同简单模式匹配算法(bruteforce algorithm)一样,但使用memoization技术缓存结果。这样做会使运行时间复杂度极大地下降至O(V^2 * 2^V)。

时间复杂度:O(V^2 * 2^V)。

请注意当N = 10 时,此算法将进行约~(100 * 2^10) = 102K 次操作,相较于简单模式匹配算法约 ~(10!) = 3628800 次操作而言大约快30倍。

6. 近似

Approximation: There are two approximation algorithms available, a 2-approximation algorithm and a 1.5-approximation algorithm that is also well known as Christofides Algorithm.