5

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

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

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

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

4

5 に答える 5

5

私はこれを動的計画法で解決します。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へのエッジを持つノードの最大コストを加えたものになります。
于 2008-09-20T09:09:45.803 に答える
2

このためのアルゴリズムがあると主張する論文があります:「時間制約のある活動ネットワークのクリティカルパス」。悲しいことに、無料コピーへのリンクが見つかりませんでした。それを除けば、http ://en.wikipedia.org/wiki/Dijkstra%27s_algorithmまたはhttp://en.wikipedia.org/wiki/A *を変更するというアイデアしか支持できません。

更新: お粗末な書式で申し訳ありません。サーバー側のマークダウン エンジンが壊れているようです。

于 2008-09-21T01:47:27.763 に答える
2

「クリティカルパス」についてはわかりませんが、これを意味していると思います。

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

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

しかし、それをしなければ、完全なトラバーサルから本当にあなたを救うものは何もありません。トラバーサルを行い、同じパスを 2 回通過しない限り、順序は重要ではありません。

于 2008-09-20T09:02:10.923 に答える
0

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

A*検索アルゴリズム

最後に、葉に対処するために、それらすべてを最終ポイントに導き、目標として設定します。

于 2008-09-20T09:14:33.233 に答える