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

一尘不染

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

algorithm

从这篇维基百科文章：

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

在大多数图中，汉密尔顿路径的随机算法如下：从随机顶点开始，如果没有邻居访问，则继续。如果没有其他未访问的邻居，并且形成的路径不是哈密顿量，则随机地均匀选择一个邻居，然后以该邻居为支点进行旋转。（也就是说，向该邻居添加一条边，并从该邻居删除现有边之一，以免形成环路。）然后，在路径的新端继续执行该算法。

我不太了解这个关键过程应该如何工作。有人可以更详细地解释此算法吗？也许我们最终可以使用更清晰的描述来更新Wiki文章。

编辑1： 我想我现在已经了解算法，但似乎只适用于无向图。谁能确认？

这就是为什么我认为它仅适用于无向图的原因：

替代文字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）连接，然后让新路径为just 4, 7, 8, 5，但这似乎适得其反，因为我必须砍掉先前导致顶点5的所有内容。

阅读 841

2020-07-28

共1个答案

一尘不染

基本上，一旦您对节点的随机选择以一种方式构造了图，使得最后一个顶点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
    }
  }

2020-07-28