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

Question

来自这篇维基百科文章:

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.

我不太明白这个旋转过程应该如何运作。有人可以更详细地解释这个算法吗？或许我们最终可以用更清晰的描述更新 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

这确实是一个非常不清楚的解释，算法似乎也不是来自任何列出的引用文献。

这个想法似乎是首先通过随机选择初始节点来创建随机路径，然后通过尽可能长时间地选择随机邻居来从该节点开始。当无法选择更多邻居时，路径要么是哈密顿路径，要么不是。如果不是，则路径上的最后一个节点已经在路径上有一些邻居(见下文)，因此旋转意味着从最后一个节点到已经在路径上的邻居创建一条边，并从中删除一个链接为路径选择的邻居。然后，路径有一个新的终点，从那里继续该过程。

例如，该算法似乎假定不存在只有一条边的节点。不过，这些很容易涵盖:如果有一个，就从那个开始，如果有两个，从其中一个开始，并尝试在另一个结束，如果有两个以上，就不能哈密​​顿路径。