3

ウィキペディア: 有向非巡回グラフ

リーフノードは実際にはツリーではないため(各ノードは複数の子と複数の親を持つことができます)、実際にすべてのルートノードを見つけようとしているため、リーフノードがまだ適切な用語であるかどうかはわかりません(これは実際にはセマンティクスの問題です.すべてのエッジの方向を逆にすると、それらはリーフ ノードになります)。

現在、グラフ全体 (指定されたノードから到達可能) をトラバースしているだけですが、それはやや高価であることが判明したため、これを行うためのより良いアルゴリズムがあるかどうか疑問に思っています. 私が考えていることの 1 つは、(別のパスをたどっている間) 既にアクセスされたノードを追跡し、それらを再チェックしないことです。

他にアルゴリズムの最適化はありますか?

また、このノードが子孫であるルート ノードのリストを保持することも考えましたが、ノードが追加、移動、または変更されるたびに変更されるかどうかを確認する必要がある場合、そのようなリストを保持するのもかなりコストがかかるようです。削除されました。

編集：

これは、単一のノードを見つけるだけではなく、エンドポイントであるすべてのノードを見つけることです。

また、ノードのマスター リストもありません。各ノードには、その子と親のリストがあります。(まあ、それは完全に正しいわけではありませんが、事前に DB から数百万のノードをプルすると、非常にコストがかかり、OutOfMemory 例外が発生する可能性があります)

編集2:

可能な解決策を変更する場合と変更しない場合がありますが、グラフは、多くても数十のルート ノード (私が見つけようとしているもの) と数百万 (おそらく数千万または数億) のリーフ ノード (ここでから始めています）。

4

3 に答える 3

3

構造に応じてそれぞれがより高速な方法がいくつかありますが、一般的に必要なのはトラバーサルです。

深さ優先検索では、考えられる各ルートを調べて、既にアクセスしたノードを追跡します。各ノードで分岐し、その各子ノードを試す必要があるため、これは再帰関数です。オブジェクトを探す方法がわからない場合は、それぞれの方法を試してみる必要があります。すでにどこに行ったかを把握しておく必要があります。そうしないと無駄になるからです。完全なトラバーサルを実行するには、ノード数のオーダーが必要です。

幅優先検索は似ていますが、「移動」する前にノードの各子にアクセスし、選択したルートからの距離のレイヤーを構築します。宛先がルートノードに近いと予想される場合、これはより高速になる可能性があります。可能なすべてのエッジをトラバースする必要があるため、パスをずっと下っていると予想される場合は遅くなります。

既知のルート ノードのリストを保持することについてはおそらく正しいですが、グラフを変更するたびに基本的に検索を実行する必要があるというトレードオフがあります。グラフをめったに変更しない場合はこれで問題ありませんが、この情報を生成するのに必要な頻度よりも頻繁にグラフを変更すると、もちろんコストがかかりすぎます。

編集: 情報の更新。2 つの任意のノード間のパスを実際に探しているように思えますが、ルート/リーフ セマンティックは常に入れ替わっています。DepthFirstSearch (DFS) は 1 つのノードで開始し、未訪問の子ごとに再帰します。目的のノードが見つかったら中断します。再帰の評価方法により、これは「左」のパスをずっとたどり、「右」のパスにたどり着く前にこの距離でノードを列挙します。ターゲット ノードが右側の最初の子である可能性がある場合、これは時間がかかり、非効率的です。BreadthFirst は、前進する前にすべての子をカバーしながら、段階的に歩きます。グラフは木のように底が重いため、両方の実行時間はほぼ同じになります。

グラフの下部が重い場合は、逆トラバーサルに興味があるかもしれません。この方向にはノードが比較的少ないため、ターゲット ノードから始めて上に向かって歩きます。一般に、ノードが子よりも多くの親を持っている限り、この方向ははるかに高速になります。アプローチを組み合わせて、一方を上に、もう一方を下にステップアップしてから、ノードのリストを比較し、途中で会うこともできます。(各ステップで 2 倍の作業が行われることを無視すると、この組み合わせが最速に見えるかもしれません)。

ただし、グラフは子のリストのリストとして保存されていると言ったので、グラフを逆方向にたどる実際の方法はありません。ノードは、その親が何であるかを知りません。これは問題です。それを修正するには、グラフの更新時にそのデータを追加するか、構造全体の複製を作成することによって、その親が何であるかをノードに認識させる必要があります（これは大きすぎると言われています）。構造全体を書き直す必要がありますが、現時点では大規模なデータベースであるため、これはおそらく問題外に思えます。やるべきことがたくさんあります。 http://en.wikipedia.org/wiki/Graph_(データ構造)

于 2009-05-28T15:59:50.087 に答える
2

訪問したノードに色を付ける (追跡する) だけです。

Python でのサンプル:

def reachable(nodes, edges, start, end):
  color = {}
  for n in nodes:
    color[n] = False
  q = [start]
  while q:
    n = q.pop()
    if color[n]:
      continue
    color[n] = True
    for adj in edges[n]:
      q.append(adj)
  return color[end]
于 2009-05-28T15:50:01.977 に答える
0

ビット配列 f(x) を計算する頂点 x の場合、各ビットはルート頂点 Ri に対応し、1 (resp 0) は「ルート頂点 Ri から x に到達できる (または到達できない)」ことを意味します。

グラフを、すべてのターゲット ルート R を含む 1 つの「上位」セット U に分割し、x が U 内にある場合、x のすべての親が U 内にあるようにすることができます。たとえば、最も近い Ri からの距離 <=D にあるすべての頂点のセット.

U が大きすぎないようにし、U の各頂点 x について f を事前計算します。

次に、クエリ頂点 y の場合: y が U にある場合、既に結果が得られています。それ以外の場合は、y のすべての親に対して再帰的にクエリを実行し、訪問した各頂点 x の値 f(x) を (マップなどで) キャッシュするため、値を 2 回計算することはありません。f(y) の値は、その親の値のビットごとの OR です。

于 2009-06-02T13:26:31.723 に答える