2

整数値と N レベルのグラフ G を指定して、ルートからリーフ ノードまでの値を合計しようとしています。これらのパス値の最大合計を見つけます。子ノードは複数の親を持つことができます。そのため、ツリーというよりはグラフです。

例えば、

ここに画像の説明を入力

小さな Java アプレット用に BFS を介してこれを実装しようとしましたが、それが最善の方法だったかどうかはわかりません。これをノードの数、つまりO(n)に合わせてスケーリングするための他の提案はありますか? O（n）にスケーリングする方法は考えられません。何か案は？

4

1 に答える 1

5

これを線形時間で解くには、動的計画法アルゴリズムを使用して最下層のノードから情報を上方に伝播します。

このように考えてみてください。グラフにレイヤーが 1 つしかない場合、最適な答えは、そのレイヤーから最大値を取得することです。一方、グラフに n + 1 層があると仮定し、一番下の n 層の最適解を (再帰的に) 計算したと仮定します。その場合、最上位層を見て、各エントリについて、そのエントリの合計とその直接の子 (既に事前計算済み) の最適解を計算することで、全体として最適な解を見つけることができます。これらすべての最大値が全体の最大値になります。

このアプローチでは、すべてのエッジを 1 回だけ訪問することになるため、合計実行時間は O(n + m) になります。ここで、n はノードの数、m はエッジの数です。

お役に立てれば！

于 2013-03-21T23:29:25.170 に答える