0

私はこれまで DFS を使用したことがなく、次の「ツリー」をトラバースする場合、パスの最小積を見つけるためにどのように使用できるか疑問に思っていました。

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

以下のコメントを参照して、混乱を解消してください(:

4

1 に答える 1

0

有向グラフを作成する必要があります。ここで、ノードは数値であり、各ノードには、次のレベルの数値/ノードへの2つのエッジがあります。この特定の問題のグラフは、有向非巡回グラフになります。

次に、作成したグラフでDFSを実行します。ただし、ノードに再度アクセスする必要があるため、以前にノードにアクセスしたことがあるかどうかを追跡/確認することはできません。代わりに、現在のノードのアウトディグリーが0かノードかを確認し（下部のノードのアウトディグリーが0になるため）、下部のノードに到達したときに現在の最小値を更新するだけで済みます。（現在の深度を追跡し、深度に達したときに現在の最小値を更新することもできます）。すべての積は、各レベルから1つずつ、正確に5つの数値を乗算した結果であるため、この特定の問題に対してこれを行うことができます。

上記で説明したのは、ノードが以前にアクセスされたかどうかを追跡する通常のグラフ検索バリアントと比較して、DFSのツリー検索バリアントと呼ばれます。グラフにサイクルがあるとツリー検索DFSがスタックしますが、これは有向非巡回グラフであるため、このような問題は発生しません。

数値がすべて負でない場合、次のことがわかります。ルートからノードに到達する方法に関係なく、前方の最適なパスは毎回同じになります。

このような場合、最下位ノードから逆方向に作業する方が高速です。同じ「親」ノードに隣接するペアごとに、小さい方のペアを選択し、「親」ノードで乗算します。ルートノードに到達するまでこれを続けてください。そうすれば、結果が得られます。

数値が正または負または0の場合は、絶対値が最大および最小の負の積、最大および最小の正の積の4つの数値を追跡する必要があります。また、0個の製品を形成できるかどうかを追跡する必要があります。2つの最大の絶対値は、正のx負の場合です。2つの最小絶対値は、正のx正または負のx負の場合です。アルゴリズムの開始時には、これら5つのフィールドはすべて未定義です。

更新方法の詳細は読者にお任せします。結果は、絶対値が最大の負の数0、絶対値が最小の正の数の順にチェックする必要があります。フィールドが未定義の場合は、スキップして次のフィールドを確認してください。

于 2013-02-26T06:54:16.103 に答える