在有向图中寻找哈密顿路径的随机算法

Question

从维基百科的这篇文章中：

http://en.wikipedia.org/wiki/Hamiltonian_path_problem

一个在大多数图上运行快速的哈密顿路径随机算法如下：从随机顶点开始，如果有未访问的邻居，则继续。如果没有更多未访问的邻居，并且形成的路径不是哈密顿路径，则均匀地随机选择一个邻居，并以该邻居为枢轴进行旋转。（也就是说，向那个邻居添加一条边，并从那个邻居中删除一条现有的边，以便不形成循环。）然后，在路径的新末端继续算法。

我不太理解这个枢轴过程应该如何工作。有人能详细解释一下这个算法吗？也许我们最终可以更新维基百科文章，以获得更清晰的描述。

编辑1：我现在认为我理解了该算法，但似乎它仅适用于无向图。有人可以证实吗？

以下是我认为它仅适用于无向图的原因： alt text http://www.michaelfogleman.com/static/images/graph.png 假装顶点编号如下：

123
456
789

假设我的路径是：9, 5, 4, 7, 8。 8的邻居都已经被访问过了。假设我选择从5中删除一个边缘。如果我删除(9, 5)，我最终只会创建一个循环：5, 4, 7, 8, 5，因此似乎我必须删除(5, 4)并创建(8, 5)。如果图是无向的，那就没问题了，现在我的路径是9、5、8、7、4。但是，如果你想象这些边是有向的，那么这不一定是一条有效的路径，因为(8, 5)是一条边，但(5, 8)可能不是。

编辑2：我想对于一个有向图，我可以创建(8, 5)的连接，然后让新路径只是4, 7, 8, 5，但这似乎是逆向进行的，因为我必须切掉之前通向顶点5的所有东西。

- FogleBird

---

按照定义，哈密顿路径存在于无向图上。任何找到它们的算法必须在无向图上运行。 - Kevin Montrose

好的，维基百科的文章说：“哈密顿路径问题和哈密顿回路问题是确定给定图（有向或无向）中是否存在哈密顿路径或哈密顿回路的问题。” 基本上我正在寻找有向图中最长的简单路径（没有重复访问的顶点）。现在看来这个算法对我没用。 - FogleBird

好的，那么我们如何实现您在伪代码中称之为FindEnd的功能呢？请参见我的编辑2。 - FogleBird

我已经实现了这个算法。它归功于Angluin和Valiant（1979），在Wilf的一本书中得到了证明：http://www.math.upenn.edu/~wilf/AlgoComp.pdf。(来源：MathWorld: http://mathworld.wolfram.com/HamiltonianPath.html。) - Jason Orendorff

最后要指出的一件事：如果你只让路径的一端漫游，那么一个糟糕的初始选择可能会导致你永远无法找到解决方案。 （或者至少漫游很长时间。我已经吃过这亏了！）所以在某个时候你必须切换到路径的另一端，并让该端漫游一段时间。或确保选择一个好的起始节点。 - Jason Orendorff

Answer 1

这确实是一个非常不清楚的解释，而且该算法似乎并不来自列出的任何参考资料之一。

这个想法似乎是首先通过随机选择初始节点并从那里选择随机邻居，只要可能就继续进行以形成随机路径。当无法再选择邻居时，路径要么是哈密顿路径，要么不是。如果不是，则路径上的最后一个节点已经有一些在路径上的邻居（见下文），因此“枢轴”意味着从最后一个节点向已经在路径上的邻居建立一条边，并删除已选择为路径的邻居之一的链接。然后，有了新的路径末端，从中继续这个过程。

看起来这个算法假设，例如，不存在仅具有单个边缘的节点。尽管这很容易解决：如果有一个这样的节点，就从那个节点开始；如果有两个，则从其中一个开始，并尝试在另一个结束；如果有两个以上，则不能存在哈密顿路径。

- JaakkoK

Answer 2

基本上，一旦您随机选择的节点构建了一个图形，使得最后一个顶点A没有未访问的相邻顶点，您需要使一个顶点可用以继续进行。

要做到这一点：随机选择一个相邻的顶点，删除其中一条现有边（在哈密顿路径中，每个单个顶点只能有两条边），然后从当前顶点向这个现在可用的随机选择的顶点绘制一个新边。然后，从随机选择的顶点跟踪到图形的末尾（只有一个离开它的单个边的第一个顶点），并继续算法。

用可怕的伪代码来说就是：

  Graph graph;
  Vertex current;
  Path path;

  while(!IsHamiltonian(path))
  {
    if(HasUnvisitedNeighbor(current, path))
    {
      Vertex next = SelectRandomUnvisited(current, path);
      DrawEdgeTo(next, current, path);
      current= next;
    }
    else
    {
       Vertex next = SelectRandomNeighbor(current, path);
       RemoveRandomEdgeFrom(next, path);
       DrawEdgeTo(next, current, path);
       path = FindEnd(next, current, path);  //Finds the end of the path, starting from next, without passing through current
    }
  }

- Kevin Montrose

---

从（next，path）中删除随机边缘；向（next，current，path）绘制边缘可能导致循环。您不能随意删除边缘。您必须删除最接近“current”的边缘。 - Jason Orendorff

我接受这个答案，因为伪代码有助于理解算法，尽管我们发现它仅适用于无向图。 - FogleBird

Answer 3

你知道什么是边吗？如果顶点是v1，v2，.. vn，则边是一对（v1，v2）-想象一下在v1和v2之间画一条线，这就是一条边。

因此，基本上你要执行一个基本的爬山算法（不断添加边并访问未访问的节点），但受到一个约束条件的限制，即不要重复访问一个节点。

如果你发现无法继续了（无法从当前顶点到达更多未访问的节点），那么你选择一个随机的连接顶点（该顶点与你已经访问过的顶点之一之间有一条边），并在路径中添加一条连接该顶点和未访问节点的边，该边还没有在路径中。

这可能会（也可能必须，由数学家决定）创建一个循环。您可以通过从路径中的边缘中删除另一条边来消除循环。

基本上，这是一种爬山算法，当你卡住时加入了一些随机扰动。当你卡住时，你基本上会添加另一条边并从图形中删除一条边，并尝试继续。如果你完全错了，你仍然可以得到一个解决方案，因为理论上你可以添加所有正确的边缘并删除所有原始错误选择。

- Larry Watanabe