旅行推销员问题

1. Introduction

Traveling Salesperson Problem: TSP is a problem that tries to find a tour of minimum cost that visits every city exactly once. In this visualization, it is assumed that the underlying graph is a complete graph with (near-)metric distance (meaning the distance function satisfies the triangle inequality) by taking the distance of two points and round it to the nearest integer.

2. 可视化

View the visualisation of TSP algorithm here.

Originally, all edges in the input graph are colored grey.

Throughout the visualization, traversed edge will be highlighted with orange.

3. 输入

指定输入图形的两种不同方式：
  1. 绘制图形：你可以在绘制框内绘制一些点，但为了确保图形的度量特性，不要绘制任何边。在你输入点以后，边会自动生成。
  2. 示例图形：你可以从图形列表中选择一个开始。

4. 简单模式匹配算法（Bruteforce）

暴力法：它尝试所有 (V-1)! 个顶点的排列（不是所有的 V!，因为我们从哪里开始并不重要）。它通过执行具有类似于Held-Karp算法参数的深度优先搜索来枚举所有可能性，也就是说，深度优先搜索将返回从当前顶点到我们尚未访问的所有顶点的旅行的值。

时间复杂度：O(V * (V - 1)!) = O(V!)。

5. 动态编程

动态规划：它使用了一种广为人知的算法，叫做Held-Karp。在这个可视化中，它被实现为一个与暴力算法相同的DFS搜索，但是使用了记忆化来缓存答案。这大大降低了运行时间复杂度，达到了O(2^V * V^2)。

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

请注意，对于N = 10，这个算法大约需要 ~(100 * 2^10) = 102K 操作，而暴力算法大约需要 ~(10!) = 3628800 操作，大约快了30倍。

6. 近似

近似：有两种近似算法可用，一种是2-近似算法，另一种是1.5-近似算法，也被广泛称为Christofides算法。