7

ノードで構成されるグラフがあり、2つのノード間にランダムパスを生成する高速アルゴリズムが必要です。私はこれのためにいくつかのアルゴリズムをゼロから設計しましたが、それを正しく理解できないようです。

アルゴリズムがループでスタックするか、訪問したノードの記録を保持すると、訪問したノード間でスタックすることがあります。私が遭遇したもう1つの問題は、アルゴリズムのパフォーマンスが不安定すぎることです。

だから私の質問は; 無向グラフの2つの到達可能なノード間のランダムパスの高速で安定したアルゴリズムを知っている人はいますか？

4

3 に答える 3

5

グラフを としますG=(V,E)。そのようなのサブセットUを作成します。VU = { u | there is a path from u to the target }

  • このサブセットを見つけるのは簡単であり、ターゲットからの逆エッジでDFSまたはBFSUを使用して線形時間で実行できることに注意してください。

このサブセットを使用して、 が上で定義され、[同じエッジですが、 の頂点にのみ適用される] グラフを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 に答える