在兩個頂點之間找到一條具有零權重總和的路徑

Question

給定一個具有頂點u和v的加權DAG，每個邊權重爲-1或1.如何確定從u到v的路徑是否具有零權重和？我只能想出一個算法來計算從u到v的所有路徑，然後總結權重以查看路徑是否可以滿足要求。我聽說過類似問題的A *方法，但我認爲這個問題不應該那麼複雜。這個問題有更好的算法嗎？

Answer 1

考慮具有後繼節點n_i的頂點u，其各自的邊權重爲w_i。

你有重路徑W的u到v如果您有：從n_0到v體重W - w_0

• 路徑，或

• 從n_1到v體重W - w_1路徑，或

• ...
• 等

可以作出上述的基礎上，一個DP算法，並在一組的形式memoizing子問題的解決方案，包含<n,w>雙，意爲「有來自n的路徑v體重w。 「 如果該套件最終包含<u,0>，則您有解決方案。