ツリー内の最短パスのすべてのペアの合計
- 王林転載
- 2023-08-28 15:17:07817ブラウズ
ツリーでは、「ノードのすべてのペアの最短パスの合計」という用語は、ノードのすべてのペアの個々の最短パスの合計の計算を指します。効果的な方法は、デュアル DFS (深さ優先検索) アルゴリズムを使用することです。選択したノードと他のすべてのノードの間の距離は、最初の DFS パス中に決定されます。ツリーは 2 回目の DFS パス中に再び走査され、各ノードを潜在的な LCA (最下位共通祖先) とみなして、選択された LCA の子孫ノードのペア間の距離の合計を計算します。この方法を使用すると、ツリー内のノードのすべてのペアの最短パスの合計を計算し、理想的なソリューションを保証できます。
使用説明書
Double DFS (深さ優先探索) 方式
動的プログラミング手法
Double DFS (深さ優先探索) 方式
ツリー内の最短パスのすべてのペアの合計には、2 つの DFS パスを含むデュアル DFS (深さ優先検索) メソッドを使用します。まず、任意のノードから他のすべてのノードまでの距離を計算します。次に、2 回目の DFS トラバーサル中に、各ノードを潜在的な LCA として考慮しながらツリー内を移動します。トラバース中に、選択した LCA の子孫であるノードのペア間の距離を計算して合計します。すべてのノードに対してこのプロセスを繰り返すことにより、最短パスのすべてのペアの合計が得られます。この戦略は、ツリー内のすべてのノード セット間の距離の合計を効率的に計算できるため、この問題に対して非常に説得力があります。
＃＃＃アルゴリズム＃＃＃- ツリー内の任意のノードを開始ノードとして使用できます
-
Example
リーリー ＃＃＃出力＃＃＃ リーリー動的プログラミング手法:
最初に任意のノードをルート ノードとして選択し、動的計画法でツリーをルート付きツリーに変換します。これは、ツリー内のすべてのノード間の最短パスの合計を計算するために使用されます。動的プログラミングを使用して、各ノードとルート ノード間の分割を計算し、結果を配列に保存します。次に、各ノードについて、ルート ノードからの子の (計算された) 距離を追加して、他のすべてのノードの全体的な距離を決定します。このようにして、すべてのノード間の最短パスの総数をすばやく計算できます。この問題を解決する効率的な方法として、このアルゴリズムの時間計算量は O(N) です。ここで、N はツリー内のノードの数です。
＃＃＃アルゴリズム＃＃＃ ツリー内の任意のノードをルートとして取得し、(たとえば、ルート ノードの深さ検索を使用して) ツリーをルート化して、ルート化されたツリーを作成します。
- 動的プログラミングを使用して、ルートから各ノードの距離を決定できます。これらの距離は、配列またはデータ構造に格納する必要があります。
- a. 現在のノードの子ノードを走査します。
b. 現在のノードを通るパスを検討するには、各サブツリーのサブツリー内のノードの数と、各サブツリーについて以前に計算されたルートまでの距離を加算します。
c. アクティブ ノードの子ノードごとに、次の金額を追加します。
-
リーリー
＃＃＃出力＃＃＃
リーリー
＃＃＃結論は＃＃＃
ツリー内の最短パスのすべてのペアの合計は、Double DFS (深さ優先検索) メソッドまたは動的プログラミングを使用して計算できます。 Double DFS メソッドは 2 つのパスで構成されます。最初に選択したノードから他のすべてのノードまでの距離を計算し、次に各ノードを潜在的な最低共通祖先 (LCA) として扱いながらツリーを再度走査して、子孫ノードのペア間の距離を合計します。動的プログラミング手法では、DFS を再帰的に使用してツリーのルートを構築し、ルートから他のすべてのノードまでの距離を計算する必要があります。どちらの方法の結果も同じで、ツリー内のすべてのペアごとの最短パスの合計で構成されます。 2 つのアルゴリズムのどちらを選択するかは、特定の実装設定またはツリー構造に基づいて決定される可能性がありますが、どちらのアルゴリズムも効率的なソリューションを提供します。
d. 現在のノードの合計を最終結果に追加します。
ツリー内の最短パスのすべてのペアの合計が最終結果になります。
以上がツリー内の最短パスのすべてのペアの合計の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。