旅行推销员问题：旅行推销员问题 (TSP) 是一个试图找到一条最小成本的旅行路线，每个城市只访问一次的问题。在这个可视化中，我们假设底层图是一个完全图，具有（近似）度量距离（意味着距离函数满足三角不等式），通过取两点的距离并将其四舍五入到最近的整数。
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
在这里查看TSP算法的可视化。
原本，输入图中的所有边都被涂成了灰色。
在整个可视化过程中，遍历的边将被高亮为橙色。
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
- 绘制图形：你可以在绘制框内绘制一些点，但为了确保图形的度量特性，不要绘制任何边。在你输入点以后，边会自动生成。
- 示例图形：你可以从图形列表中选择一个开始。
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
暴力法：它尝试所有 (V-1)! 个顶点的排列（不是所有的 V!，因为我们从哪里开始并不重要）。它通过执行具有类似于Held-Karp算法参数的深度优先搜索来枚举所有可能性，也就是说，深度优先搜索将返回从当前顶点到我们尚未访问的所有顶点的旅行的值。
时间复杂度：O(V * (V - 1)!) = O(V!)。
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
动态规划：它使用了一种广为人知的算法，叫做Held-Karp。在这个可视化中，它被实现为一个与暴力算法相同的DFS搜索，但是使用了记忆化来缓存答案。这大大降低了运行时间复杂度，达到了O(2^V * V^2)。
时间复杂度：O(2^V * V^2)。
请注意，对于N = 10，这个算法大约需要 ~(100 * 2^10) = 102K 操作，而暴力算法大约需要 ~(10!) = 3628800 操作，大约快了30倍。
近似：有两种近似算法可用，一种是2-近似算法，另一种是1.5-近似算法，也被广泛称为Christofides算法。
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
Visualisation Scale
编辑图表
Input Graph
图示
简单模式匹配
动态编程
估计
Bitonic TSP
Local Search