寻找哈密尔顿路径有向图随机算法 [英] Randomized algorithm for finding hamiltonian path in a directed graph

问题描述

从这个维基百科文章：

<一个href="http://en.wikipedia.org/wiki/Hamiltonian_path_problem">http://en.wikipedia.org/wiki/Hamiltonian_path_problem

一个随机算法哈密尔顿   路径是快速的大多数图形是   如下：从随机启动   顶点，并且继续，如果有一个   邻居无法访问。如果没有   更未访问的邻居，和路径   形成不是汉密尔顿，挑   邻居一致地随机，和   旋转使用的邻居作为一个支点。   （即，边添加到该   邻居，并删除之一   从邻居现有的边缘，使   以不形成环。）然后，继续   该算法在对新的终点   路径。

A randomized algorithm for Hamiltonian path that is fast on most graphs is the following: Start from a random vertex, and continue if there is a neighbor not visited. If there are no more unvisited neighbors, and the path formed isn't Hamiltonian, pick a neighbor uniformly at random, and rotate using that neighbor as a pivot. (That is, add an edge to that neighbor, and remove one of the existing edges from that neighbor so as not to form a loop.) Then, continue the algorithm at the new end of the path.

我不太了解这个转动过程应该工作。有人能详细解释一下这个算法？也许我们可以最终用更新更清楚的说明了维基文章。

I don't quite understand how this pivoting process is supposed to work. Can someone explain this algorithm in more detail? Perhaps we can eventually update the Wiki article with a more clear description.

修改1：我想我现在明白了算法，但现在看来似乎只适用于无向图。谁能证实？

Edit 1: I think I understand the algorithm now, but it seems like it only works for undirected graphs. Can anyone confirm that?

这也是为什么我认为它仅适用于无向图：

Here's why I think it only works for undirected graphs:

pretend顶点的编号，像这样：

Pretend the vertices are numbered like so:

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），就不一定了。

Let's say my path so far is: 9, 5, 4, 7, 8. 8's neighbors have all been visited. Let's say I choose 5 to remove an edge from. If I remove (9, 5), I just end up creating a cycle: 5, 4, 7, 8, 5, so it seems I have to remove (5, 4) and create (8, 5). If the graph is undirected, that's fine and now my path is 9, 5, 8, 7, 4. But if you imagine those edges being directed, that's not necessarily a valid path, since (8, 5) is an edge but (5, 8) might not be.

编辑2：我猜有向图，我可以创建（8,5）连接，然后让新的路径只是 4，7，8，5 ，但似乎适得其反，因为我不得不砍掉一切，previously导致了顶点5。

Edit 2: I guess for a directed graph I could create the (8, 5) connection and then let the new path be just 4, 7, 8, 5, but that seems counter productive since I have to chop off everything that previously led up to vertex 5.

推荐答案

基本上，一旦你随机选择的节点具有构造成这样一个图表，最后一个顶点A没有未访问邻国的顶点，你需要做一个顶点可用要继续。

Basically, once your random selection of nodes has construct a graph in such a way that the last vertex A has no unvisited neighboring vertices you need to make a vertex available to continue on.

要做到这一点：选择一个相邻的顶点随意，删除其现有的边缘（在一个哈密尔顿路径也可以从任何一个顶点只有两个边），然后画出一个新的边缘从当前顶点到这个现在可随机选择之一。然后，从随机选择的顶点到图形（即仅具有单个边缘离开它的第一个顶点）的端跟踪和继续的算法。

To do this: select a neighboring vertex at random, remove one of its existing edges (in a Hamiltonian path there can be only two edges from any single vertex), then draw a new edge from your current vertex to this now available randomly selected one. You then trace from the randomly selected vertex to the end of the graph (the first vertex that has only a single edge leaving it) and continue the algorithm.

在各种可怕的psuedo- code：

In all sorts of horrific psuedo-code:

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

这篇关于寻找哈密尔顿路径有向图随机算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！