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

Question

从这篇维基百科文章:

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

在大多数图上快速的哈密顿路径的随机算法如下:从随机顶点开始,如果没有访问的邻居则继续.如果没有更多未访问的邻居,并且形成的路径不是哈密顿量,则随机均匀地选择邻居,并使用该邻居作为枢轴进行旋转.(即,向该邻居添加边缘,并从该邻居中移除一个现有边缘,以便不形成循环.)然后,在路径的新端继续算法.

我不太明白这个旋转过程应该如何工作.有人可以更详细地解释这个算法吗？也许我们最终可以用更清晰的描述更新Wiki文章.

编辑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的所有内容.

Answer 1

这确实是一个非常不清楚的解释,并且该算法似乎也没有来自任何列出的参考文献.

这个想法似乎是首先通过随机选择初始节点来制作随机路径,然后通过选择随机邻居来进行,只要可能就行.当不能再挑选邻居时,要么路径是汉密尔顿,要么不是.如果不是,则路径上的最后一个节点已经在路径上有一些邻居(见下文),因此,旋转意味着从最后一个节点到已经在路径上的邻居边缘并从中删除其中一个链接已被选为路径的邻居.然后,路径有了一个新的结束,继续进行该过程.

例如,该算法似乎假设没有只有一条边的节点.但这些很容易掩盖:如果有其中一个,那么从这开始,如果有两个,从其中一个开始并尝试最终到另一个,如果有两个以上,则不能汉密尔顿主义的道路.

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
    }
  }