7

我有一个由节点组成的图，我需要一个快速算法来生成两个节点之间的随机路径。我为此从头开始设计了几种算法，但似乎无法做到正确。

要么算法陷入循环，要么当我记录访问过的节点时，它有时会卡在访问过的节点之间。我遇到的另一个问题是我的算法在性能上太不稳定了。

所以我的问题是；有谁知道无向图中两个可达节点之间随机路径的快速稳定算法？

4

3 回答 3

5

让您的图表成为G=(V,E). 创建这样的子U集。VU = { u | there is a path from u to the target }

使用这个子集，创建一个上面定义的图G'=(U,E')和U[E' = E [intersection] UxU相同的边，但仅应用于U] 中的顶点。

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

  • 注意 - 想法是找到一条路径 - 不一定简单，因此您不应该维护一个visited集合。
  • 您可能会添加一个“中断规则”，如果您达到一定深度，您将寻找目标 - 非随机的，以避免循环中的无限循环。
  • 性能预计会发生变化，因为它与找到的路径的长度呈线性关系，可能非常长或非常短......
于 2012-04-17T20:00:38.757 回答
2

如果我正确理解了您的问题，则您正在尝试生成统一的生成树。

于 2012-04-17T20:30:53.877 回答
1

这取决于你的意思random。如果您不在乎它的含义，您是否尝试过蒙特卡罗方法？

假设目标完全可以到达，并且您有一个无向图，我在黑暗的伪代码中疯狂地刺伤。

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

amit的注意事项也在这里：

  • 您可能会添加一个“中断规则”，如果您达到一定深度，您将寻找目标 - 非随机的，以避免循环中的无限循环。
  • 性能预计会发生变化，因为它与找到的路径的长度呈线性关系，可能非常长或非常短......
于 2012-04-17T20:02:27.823 回答