algorithm - 遍历非汉密尔顿、未加权、无向图中的所有顶点

Question

我想找到一种启发式或算法来解决类似旅行销售人员的问题，但有一些关键区别:

-图表未加权。 (所以从任何一个顶点走到一个相连的顶点的代价是1)

-我想通过每个顶点至少一次，而不是恰好一次。

-图中有死胡同，我们必须从中回溯。

图表看起来像这样:

目前，我沿着一条随机路线前进，将我的历史保存在堆栈中，直到我到达一个未连接到任何未走过的顶点的顶点 - 然后我回溯到最近的未探索分支并探索它。我重复此操作，直到没有要探索的顶点 - 我可以使用此方法分 2n 步遍历图形，其中 n 是顶点数。我觉得一定有更好的方法 - 我将不胜感激任何帮助或指向我应该研究的 Material !

Answer 1

您的问题实际上是 TSP 的一般定义。您当前的方法可能比 2n 大得多，您可以通过一条很长的路径然后返回到连接到路径的第一个顶点的某个未访问的顶点，这会导致最佳方法和您的方法之间存在任意大的差距。

如果您正在寻找好的启发式方法，那么 nearest neighbor是一个好方法。首先找到每两个顶点之间的最短路径并创建一个新图G'，使得每条边uv的权重是G中这两个顶点之间的最短路径的长度。然后在新创建的图中运行最近邻算法。

另一种方法是使用 Christofides algorithm .找到图形的生成树，然后基于此生成树创建欧拉之旅。这个总是最多 3/2 x 最优，所以你可以结合使用这个和最近邻算法来获得好的结果。

顺便说一下，几乎所有众所周知的 TSP 启发式算法都适用于您的问题，我知道最广为人知的是，我认为您可以在网络上找到它的实现是 tour merging algorithm由于 Cook 和 Seymour，它非常准确，但不是很快或不容易实现。 (如果您没有找到实现，您可以要求论文的作者带来实现)。