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

问题描述

来自这篇维基百科文章:

From this Wikipedia article:

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:

替代文字 http://www.michaelfogleman.com/static/images/graph.png

假设顶点是这样编号的:

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.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，但这似乎适得其反，因为我必须砍掉之前导致顶点 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.

在各种可怕的伪代码中:

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屋！