graph - 旅行商查询

Question

我读过 TSP 的近似值之一是执行以下操作： - 计算最小生成树 (MST) - 执行 MST 的 DFS

解决 TSP 的目标是每个顶点都被访问一次。旅行者从“A”点开始，他需要访问图表上的所有其他点，然后返回“A”点（有时，该子句不存在），确保每个点都被访问一次。

假设图 G 的 MST 'T' 如下：图的最小生成树

这个 MST 的 DFS 是 ABCED。

我的问题是解决 TSP，我需要旅行者必须访问的所有城市（点）的列表。显然，在 MST 中不存在从“E”到“D”的路径。那么这如何解决问题呢？

score 0 · Accepted Answer

只要原始图中存在从 E 到 D 的路径，MST 中是否没有从 E 到 D 的路径都没有关系。通常 TSP 涉及一个完全连通的图。

1 回答 1