Randomized algorithm for finding hamiltonian path

问题:

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.

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:

alt text http://www.michaelfogleman.com/static/images/graph.png

Pretend the vertices are numbered like so:

123
456
789

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.

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.

回答1:

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

回答2:

It is indeed a very unclear explanation, and the algorithm does not seem to come from any of the listed references either.

The idea seems to be to first make a random path by picking the initial node at random and proceeding from that by selecting random neighbors for as long as that is possible. When no more neighbors can be picked, either the path is Hamiltonian or it is not. If it is not, this last node on the path has some neighbor already on the path (see below), so the pivoting means to make an edge from the last node to the neighbor already on the path and deleting one of the links from the neighbor that have been chosen for the path. Then, there is a new end to the path, from which the process is continued.

It seems this algorithm assumes, for instance, that there are no nodes with only a single edge. These are easy to cover, though: if there is one of them, just start from that, if there are two, start from one of them and try to end up at the other, and if there are more than two, there cannot be a Hamiltonian path.

回答3:

Do you understand what an edge is? If the vertices are v1, v2, .. vn, then an edge is a pair (v1, v2) - imagine drawing a line between v1 and v2, and that is an edge.

So, basically you do a basic hill-climbing algorithm (keep adding edges and visiting unvisited nodes) subject to the constraint that you don't visit a node more than once.

And if you find you can't continue any more (can't reach any more of the unvisited nodes from the current vertex), then you choose a random vertex which is connected (there is an edge between that vertex and one of the vertices that you have visited already) and add in an edge between that vertex and the visited nodes that is not already in the path.

This might (and possibly must, leave that up to the mathematicians) create a loop. You can remove the loop by removing another edge from the edges in the path.

Basically, this is a hill-climbing algorith, with a bit of randomized perturbation when you get stuck. When you get stuck, you basically add in another edge and remove one from the graph and try continuing. If you were completely wrong, you can still get to a solution because in theory you could add in all the right edges and delete all of your original wrong choices.