旅行商查询

Question

我已经阅读了近似的TSP之一是做到以下几点： - 计算的最小生成树（MST） - 执行的解决的MST

目标一个DFS TSP是每个顶点只被访问一次。旅行者从'A'点开始，他需要访问图表上的所有其他点并回到'A'点（有时候，这个子句不存在），确保每个点只访问一次。

假设MST图G是作为 'T' 如下：

此MST的DFS是A-B-C-E-d。

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

Answer 1

只要在原始图中存在从E到D的路径，在MST中是否存在从E到D的路径并不重要。通常TSP包含一个完全连通的图。本文的更多信息

见第2.1节： http://www.cs.tufts.edu/~cowen/advanced/2002/adv-lect3.pdf