頂点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つの副問題があります。あまりにも多くはありません（私の前のコメントを参照してください）、あなたは*すべての*そのようなペアを解決することができます。 –
DAGであるため、DPを使用して解決することができます。 – Sayakiss
はい、おそらくDPがそれを解決できます。しかし、どのような部分問題がどのように見えるのか分かりません。/ – haruhi93