旅行推销员问题

1. Introduction

旅行推销员问题：旅行推销员问题 (TSP) 是一个试图找到一条最小成本的旅行路线，每个城市只访问一次的问题。在这个可视化中，我们假设底层图是一个完全图，具有（近似）度量距离（意味着距离函数满足三角不等式），通过取两点的距离并将其四舍五入到最近的整数。

2. 可视化

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

原本，输入图中的所有边都被涂成了灰色。

在整个可视化过程中，遍历的边将被高亮为橙色。

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算法。