頂点uとvを持つウェイト付きDAGが与えられた場合、各エッジウェイトは-1または1です。ウェイト和がゼロからvまでのパスがあるかどうかを調べるには?私は、uからvまでのすべてのパスを計算し、その後、ウェイトを合計して、パスが要件を満たすことができるかどうかを確認するアルゴリズムを考え出すことができます。私は同様の問題についてA *アプローチについて聞いたことがありますが、この質問は複雑ではないはずです。この問題のより良いアルゴリズムはありますか?2つの頂点間のウェイト合計がゼロのパスを見つける
答えて
頂点u
が後続ノードn_i
であり、エッジ重みがそれぞれw_i
であるとします。
あなたが持っている場合はW u
からv
重量のパスを持っている:重量W - w_0
とv
からn_0
から
パス、または重量
W - w_1
とv
からn_1
からパスを、または
- ...
- は、など
あなたは上記に基づいてDPアルゴリズムを作成し、重量w
とv
からn
からのパスであります」を意味し、<n,w>
ペアを含む、セットの形で部分問題の解決策をmemoizingすることができます。 " セットに最後に<u,0>
が含まれている場合、解決策があります。
すべてのパスの中に2つ以上の異なる重みが存在できないため、空間の複雑さは最悪です(| V || E |)重みは| E |であり、最小は - | E |)である。 –
合理的な解決策。しかし、どのようにサブ問題の数を決定するのですか? – haruhi93
@ haruhi93:個体(頂点、総重量)ごとに最大1つの副問題があります。あまりにも多くはありません(私の前のコメントを参照してください)、あなたは*すべての*そのようなペアを解決することができます。 –
- 1. 点集合から四角形の頂点を見つける
- 2. 2つの頂点の間の最長のパス
- 3. グラフ - すでに2つの頂点間のパスを印刷する方法
- 4. Floyd-Warshallアルゴリズムを使用して2つの頂点の間のパス数を計測する
- 5. 2つの頂点間のエッジを見つける正しい方法は何ですか?
- 6. バイナリサーチツリー内のターゲット値に合計するパスを見つける
- 7. Box2D AndEngineの2つの頂点間の結合を中断する
- 8. 2つの頂点間のグラフ接続をチェックする方法
- 9. 完全なグラフの順序付き集合の頂点を見つける
- 10. 非常に重要な頂点を持つ二部グラフの頂点カバーを見つける
- 11. xy平面内の2つの点の間に見出しをつける
- 12. グリッドビューの合計を見つける
- 13. 無向グラフに2つの頂点間のパスがあるかどうかを調べる
- 14. Mathematicaで2つのListLinePlotの交点を見つける
- 15. C#2つの緯度/経度の中点を見つける
- 16. 2つの配列の交点を見つける
- 17. 他の点のセットとの距離の合計が最小である点を見つける
- 18. 最大合計を見つける
- 19. グラフ - 他のすべての頂点から到達可能な頂点を見つけよう
- 20. 2つの数値の間の素数を見つける
- 21. 2つのxy点の間のクワッドカーブを計算する
- 22. OpenGL:OpenGLを使用して他のアプリケーションの頂点構造を見つける
- 23. 2つのリモートブランチ間の違いを見つける
- 24. 2つのドキュメント間の類似性を見つける
- 25. 2つのポリゴンの間に区切り線を見つける
- 26. matlab:平行四辺形の4番目の頂点を見つける
- 27. 強く接続された頂点のすべてのセットを見つける
- 28. SVNが2つのブランチ間でマージする - "パスが見つかりません"
- 29. 特定の開始点と終了点の間にあるすべての可能なパスを見つける
- 30. cで2行の形状の間違った点を見つける#
DAGであるため、DPを使用して解決することができます。 – Sayakiss
はい、おそらくDPがそれを解決できます。しかし、どのような部分問題がどのように見えるのか分かりません。/ – haruhi93