6

次の属性を持つグラフがあります。

  • 無向
  • 加重なし
  • 各頂点には、最小で 2 つ、最大で 6 つのエッジが接続されています。
  • 頂点数は < 100 になります
  • グラフは静的であり、頂点/エッジを追加/削除または編集することはできません。

頂点のランダムなサブセット (少なくとも 2 つ) 間のパスを探しています。パスは、頂点を 1 回だけ通過する単純なパスにする必要があります。

私の最終的な目標は、ルートのセットを作成して、サブセット頂点の 1 つから開始し、他のサブセット頂点のいずれかに到達できるようにすることです。ルートをたどる場合、すべてのサブセット ノードを通過する必要はありません。

私が見つけたすべてのアルゴリズム (ダイクストラ、深さ優先検索など) は、2 つの頂点間のパスと最短パスを処理しているようです。

これらの頂点のサブセットを接続するすべてのパス (これらはサブグラフだと思います) を提供する既知のアルゴリズムはありますか?

編集：

私が達成しようとしていることを説明するために、(警告! プログラマー アート) アニメーション GIF を作成しました: http://imgur.com/mGVlX.gif

前処理と実行時の 2 つの段階があります。

前処理

  1. グラフと頂点のサブセット (青いノード) があります。
  2. すべての青いノードを接続するすべての可能なルートを生成します

ランタイム

  1. 任意の青いノードから開始して、生成されたルートのいずれかを選択し、それに沿って移動して目的の青いノードに到達できます。

したがって、私のタスクは、A->B からのパスを作成するのではなく、すべての青いノードを接続するすべてのサブグラフ (ルート) を作成することです。

4

3 に答える 3

1

あなたが探しているのは（私が正しく理解していれば）実際にはすべてのパスではなく、すべてのスパニングツリーです。ここでスパニングツリーに関するウィキペディアの記事を読んで、それらが探しているものであるかどうかを判断してください。もしそうなら、おそらく読みたいと思う論文があります：

ガボウ、ハロルドN .; マイヤーズ、ユージーンW.（1978）。「有向グラフと無向グラフのすべてのスパニングツリーを見つける」。SIAMJ.Comput。7（280）。

于 2010-04-28T12:01:45.300 に答える
1

単純な幅優先検索では、1 つのソース頂点から他のすべての頂点への最短パスが得られます。したがって、関心のあるサブセットの各頂点から開始して BFS を実行し、他のすべての頂点までの距離を取得できます。

いくつかの場所で、BFS は頂点のペア間のパスを提供すると説明されていることに注意してください。ただし、これは必須ではありません。グラフ内のすべてのノードを訪問するまで実行し続けることができます。

このアルゴリズムはジョンソンのアルゴリズムに似ていますが、グラフが重み付けされていないため、大幅に単純化されています。

時間の複雑さ: 頂点ごとに一定数のエッジがあるため、各 BFS は O(n) かかり、合計は O(kn) になります。ここで、n は頂点の数、k はサブセットのサイズです。比較として、Floyd-Warshallアルゴリズムは O(n^3) かかります。

于 2010-04-27T17:59:49.473 に答える
1

これにアプローチするには非常に多くの方法があり、混乱しないようにするために、コアの問題の説明に対処する別の回答を次に示します。

とにかく一度に 1 つしか使用しない場合、青い頂点を接続するすべての可能なサブグラフを見つけることはおそらくやり過ぎです。私はむしろ、単一のアルゴリズムをランダムに見つけるアルゴリズムを使用したいと思います（常に同じであるため、最短パスアルゴリズムなどではありません）。

これらのサブグラフの 1 つを保存したい場合は、乱数ジェネレーターに使用したシードを保存するだけで、同じサブグラフを再度作成できます。

また、サブグラフの束を本当に見つけたい場合は、異なるシードで複数回実行できるため、ランダム化されたアルゴリズムが適切な選択です。

唯一の本当の欠点は、可能なサブグラフをすべて見つけたかどうかわからないことですが、それがアプリケーションの要件であるとは思えません。

アルゴリズムについて: グラフのプロパティに応じて、最適なアルゴリズムは異なる場合がありますが、常に単純なランダム ウォークから始めることができます。1 つの青いノードから開始して、別の青いノードに移動します (作成中)。自分の古い足跡をたどっていないことを確認してください）。次に、そのパス上のランダムなノードを選択し、そこから次の青まで歩き始めます。

特定のグラフでは、これは最悪の場合の複雑さが非常に悪いですが、あなたの場合には十分かもしれません。もちろん、ランダムなパスを見つけるためのよりインテリジェントな方法はありますが、簡単に始めて、それで十分かどうかを確認します。彼らが言うように、時期尚早の最適化は悪です ;)

于 2010-04-29T09:19:18.200 に答える