有向無巡回グラフのパス合計

Question

有向非循環グラフが与えられた場合、分岐が22に等しいパスの合計を返すかどうかを決定します。下の例では、そのようなパスは（7 + 8 + 3 + 4）にあります。そのようなアルゴリズムの実行時間の複雑さは何ですか？

 7 
    /\ 
    8 6 
/\/\ 
    2 3 8 
// \  
5 4  1 

これは私が思いついたものです。

public boolean hasPathToSum(Node root, int sum) 
{ 
    if (root == null) return false; 
    if (root.value == sum && (root.left == null && root.right == null)) 
     return true; 

    return hasPathToSum(root.left, sum - root.value) || hasPathToSum(root.right, sum - root.value); 
} 

複雑さを改善するための推奨事項はありますか？

Answer 1

グラフのすべての値が負でない場合は、memoizationを使用してO（（n + m）* sum）でこの問題を解決できます。あなたのケースでは、和は固定され、22に等しいので、解は事実上線形です。

Memoizationは同じ値を2回計算しないテクニックです。 hasPathToSum(root, sum)は純粋な関数であることに注意してください。その結果は引数のみに依存し、副作用はありません。これは、この関数の結果をあるマップ(root, sum) -> boolに保存することができることを意味します（おそらくHashMapまたはJavaのTreeMapです。私は言語に精通していないため正確に言えません）。

ここで、関数を呼び出すときに、引数がマップに表示されているかどうかを確認します。はいの場合は、保存された値を返します。そうでなければ、それを計算し、マップに保存して戻ります。このようにして、関数は実際には引数の集合に対して1回だけ計算されます。

最後の最適化は、負でない値でのみ機能します。この場合、hasPathToSum(v, x)の結果はx <の場合はfalseであることに注意してください。カットオフを行うことができます。この最適化により、各ノードに対してhasPathToSumが最大23の異なる合計値で呼び出され、前述の実行時間が得られます。