Data Structures Algorithms 简明教程
Travelling Salesman Problem (Greedy Approach)
旅行商问题是图论中的一个计算问题，其中旅行商需要访问列表中的所有城市（表示为图中节点），并且已知所有城市之间的距离（表示为图中各边）。此问题需要找到一条最短路径，路径中旅行商访问了所有城市并返回至出发城市。
请看下方的图，假设旅行商从顶点“a”出发，他们需要访问剩余的顶点 b、c、d、e、f，并回到“a”，同时确保花费最小。
有各种方法可以找到旅行商问题的解决方案：朴素方法、贪婪方法、动态规划方法等。在本教程中，我们将学习如何使用贪婪方法解决旅行商问题。
Travelling Salesperson Algorithm
如贪婪方法所定义，我们需要找到局部最优解决方案，以找出全局最优解决方案。算法采用的输入是图 G {V, E}，其中 V 是顶点集，E 是边集。图 G 从一个顶点出发再回到同一顶点的最短路径作为输出。
Algorithm
-
旅行商问题以图 G {V, E} 作为输入，并将另一个图声明为输出（比如 G'），它将记录旅行商从一个节点前往另一个节点的路径。
-
算法首先将图 G 中的所有边从最小距离到最大距离进行排序。
-
选择的第一个边是最小距离的边，两个顶点（比如 A 和 B）中的一个是出发节点（比如 A）。
-
然后在该节点（B）除出发节点外的相邻边中，找到最小成本的边，并将其添加到输出图中。
-
继续处理其他节点，确保输出图中没有环，并且路径返回到始发节点 A。
-
但是，如果在给定问题中提到了开始节点，则解决方案必须始终仅从该节点开始。让我们看一些示例问题以更好地理解这一点。
Examples
考虑以下具有六个城市及城市之间距离的图形 -
从给定的图中，由于已经提到了起始点，所以解决方案必须始终从该节点开始。在从 A 出发的边中，A → B 具有最短距离。
然后，B → C 具有它们之间最短且唯一的边，因此它被包含在输出图中。
在 C → D 之间只有一个边，因此它被添加到输出图中。
D 有两条向外边。即使 D → B 比 D → E 距离更短，B 也已被访问过一次，如果将其添加到输出图中，它将形成一个环。因此，D → E 被添加到输出图中。
从 e 只有一个边，即 E → F。因此，它被添加到输出图中。
同样，即使 F → C 比 F → A 距离更短，F → A 也被添加到输出图中，以避免形成环，并且 C 已被访问过一次。
从 A 开始并结束于 A 的最短路径是 A → B → C → D → E → F → A
路径的成本是：16 + 21 + 12 + 15 + 16 + 34 = 114。
即使如果路径从其他节点开始，路径的成本可能会降低，但问题并未就此提出。