有向非循環グラフのクリティカル パスを計算するにはどうすればよいですか?

Question

グラフのノードに重みがある場合、有向非巡回グラフのクリティカル パスを計算する (パフォーマンスに関して) 最良の方法は何ですか?

たとえば、次のような構造があるとします。

            Node A (weight 3)
               /            \
     Node B (weight 4)      Node D (weight 7)
     /               \
Node E (weight 2)   Node F (weight 3)

クリティカル パスは A->B->F である必要があります (合計の重み:10)

Answer 1

「クリティカル パス」についてはまったくわかりませんが、おそらく次のことを意味していると思います。 これ.

重み付きの非巡回グラフで最長のパスを見つけるには、ツリー全体を走査して長さを比較する必要があります。これは、ツリーの残りの部分がどのように重み付けされているかが実際には分からないためです。ツリートラバーサルの詳細については、次のサイトを参照してください。 ウィキペディア. 。実装が簡単で簡単なため、事前注文トラバーサルを使用することをお勧めします。

頻繁にクエリを実行する場合は、挿入時のサブツリーの重みに関する情報を使用してノード間のエッジを拡張することもできます。これは比較的安価ですが、走査を繰り返すと非常に高価になる可能性があります。

しかし、そうしなければ、完全な横断からあなたを救うものは何もありません。実行する限り、順序はあまり重要ではありません。 横断 そして同じ道を二度進むことはありません。

Answer 2

私なら動的計画法でこれを解決します。S から T までの最大コストを求めるには、次のようにします。

• グラフのノードを S = x_0, x_1, ..., x_n = T として位相的に並べ替えます。(S に到達できるノード、または T から到達できるノードは無視します。)
• S から S までの最大コストは S の重量です。
• すべての i < k について S から x_i までの最大コストを計算したと仮定すると、S から x_k までの最大コストは、x_k のコストに、x_k までのエッジを持つノードへの最大コストを加えたものになります。

Answer 3

このためのアルゴリズムがあると主張する論文があります。「時間制限のあるアクティビティ ネットワーク内のクリティカル パス」。残念ながら、無料版へのリンクは見つかりませんでした。それ以外では、変更するという考えは二の次です http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm または http://en.wikipedia.org/wiki/A*

アップデート：ひどいフォーマットで申し訳ありません。サーバー側のマークダウン エンジンが壊れているようです。

Answer 4

私の最初の回答ですので、スタックオーバーフローの文化による非標準的な点についてはご容赦ください。

解決策は簡単だと思います。重みを無効にして、DAG の古典的な最短パスを実行するだけです (もちろん頂点の重みに合わせて変更されています)。かなり高速に実行されるはずです。(時間計算量はO(V+E)くらいかな)

重みを否定すると、最大の重みが最小になり、2 番目に大きいものが 2 番目に小さくなるなどのように機能するはずだと思います。 a > b それから -a < -b. 。その後、否定されたパスの最小パスの解が見つかり、元のパスの最長パスが見つかるため、DAG を実行するだけで十分です。

Answer 5

A* メソッドを試してください。

A* 検索アルゴリズム

最後に葉っぱを処理するために、すべての葉っぱを最終点につなげてゴールに設定します。