一个快速稳定的算法用于节点图中的随机路径是什么？

Question

我有一个由节点组成的图，需要一个快速算法来生成两个节点之间的随机路径。我从零开始设计了几种算法，但似乎都无法得到正确的结果。有时算法会陷入循环，或者当我记录已访问的节点时，它有时会卡在已访问的节点之间。我遇到的另一个问题是，我的算法在性能方面太不稳定。因此我的问题是：是否有人知道在无向图中寻找两个可达节点之间的随机路径的快速稳定的算法？

- Marnix v. R.

---

“random”是什么意思？根据您所需的内容，可能会得到非常不同的分布。您是指“从节点之间的所有可能路径中均匀抽样”吗？还是“从一个节点到另一个节点有很多不同的路径，即使它们不是统计随机的？” - templatetypedef

Answer 1

让你的图形为G =（V，E）。创建一个子集U，使得U = {u |存在从u到目标的路径}。

请注意，找到这个子集U很容易 - 并且可以使用从目标反向的边缘上的DFS或BFS在线性时间内完成。

使用这个子集，创建一个图形G' =（U，E'），其中U如上所述定义，E' = E [intersection] UxU [相同的边缘，但仅应用于U中的顶点]。

在G'上运行随机（选择下一个要探索的顶点）DFS，直到到达目标。

• 注意 - 这个想法是找到一条路径 - 不一定简单，因此您不应该维护一个visited集合。
• 您可以添加一个“打破规则”，如果达到一定深度，您将寻找目标 - 未随机化，以避免在圆圈中出现无限循环。
• 性能预计会有所变化，因为它与找到的路径长度成线性关系，这可能非常长或非常短...

- amit

---

这不会很统一。如果图是有向的，也许你可以使用一些动态规划来计算每个dfs选择所产生的可用路径数量，并使用它来使其更加均匀。 - Thomas Ahle

Answer 2

如果我理解您的问题正确，您正在尝试生成一个均匀生成树。

- David Brabant

Answer 3

这取决于你对“随机”的定义。如果你不关心它的意思，你尝试过蒙特卡洛方法吗？

我猜测一下，假设目标是可达的，并且你有一个无向图的伪代码。

1. <i>s</i> <- start node
2. Choose a random neighbor of <i>s</i>, call that neighbor <i>n</i>.
3. Add the edge from <i>s</i> to <i>n</i> to the path.
4. Set <i>s</i> <- <i>n</i>.
5. Go to 2, unless you've reached the target.

阿米特的注意事项在这里也适用：

• 您可能会添加一个"中断规则"，如果达到一定深度，您将寻找目标 - 未随机化，以避免在圆圈中产生无限循环。
• 性能预计会有所变化，因为它与找到路径的长度成线性关系，可能非常长或非常短...

- nes1983

---

如果在某个点n没有通往目标的路径，你将会陷入无限循环。 - amit

添加可达性作为前提条件。如果前提条件不成立，修复起来很容易。 - nes1983

我尝试过这个，但问题是它太不稳定了。有时候非常慢。 - Marnix v. R.