11

（非バイナリ）ツリーにn個のノードのセットがあります。任意の2つのノード間の距離の最大値を見つけたい。（2つのノード間の距離を、それらのノードとそれらの最も低い共通の祖先の間の距離の合計として定義します）。

各ノード間の距離を計算して最大値を取得するだけで、O（n ^ 2）でこの問題を簡単に解決できますが、これは私のアプリケーションシナリオには遅すぎる*ので、もっと良いものを期待しています。

（追加情報：私のアプリケーションシナリオでは、これらのノードは実際にはファイルであり、ツリーはディレクトリ構造です。したがって、ツリーは非常に浅い（深さ<〜10）が、300,000以上のノードがある可能性があります。ファイルのセットは次のようになります。サイズは3〜200の間です。事実上、各セットのファイルがどこまで広がっているかを把握しようとしています。）*

編集：おそらく私はより多くの答えを促すために同等の質問をすることができます：私のセットのノードとそれらを接続するために必要なノードのみを含む元のツリーのサブセットを考えてみてください。次に、質問は次のようになります。無向非周期グラフで最長の単純なパスを見つけるにはどうすればよいですか。

*編集2： didiercが指摘したように、私は実際にはファイルではなくフォルダーのセットを検討する必要があります。これは私のセットを小さくし、徹底的なアプローチは十分に速いかもしれません。それでも、より高速な解決策を見つけることは有益であり、私はそれがあるかどうかを知りたいと思っています。

4

4 に答える 4

11

あなたの問題は、木の直径を見つけることとしても知られています。ノードのペア間のすべての最短経路の中で、最も長い経路を探しています。

木の直径Sをd（S）で表し、その高さをh（S）で表します。

サブツリーS1...Sdを持つツリーSの2つの最も遠いノードは、そのサブツリーの1つの下にあるか、2つのサブツリーにまたがっている可能性があります。最初のケースでは、最も離れた2つのノードがサブツリーSiの下にある場合、d（S）はちょうどd（Si）です。2番目のケースでは、最も距離のある2つのノードが2つのサブツリー（たとえばSiとSj）にまたがる場合、2つのノードは各サブツリーの最も深い2つのノードに2を加えたものでなければならないため、それらの距離はh（Si）+ h（Sj）+2になります。 2つのサブツリーを結合するためのより多くのエッジ。実際、この2番目のケースでは、SiとSjはSの最も高いサブツリーと2番目に高いサブツリーである必要があります。

O（n）アルゴリズムは次のように進行します

アルゴリズムd（S）

1. recursively compute d(S1)...d(Sd) and h(S1)...h(Sd) of the subtrees of S.
2. denote by Si be the deepest subtree and Sj the second deepest subtree
3. return max(d(S1), ..., d(Sd), h(Si)+h(Sj)+2)

分析

2行目と3行目は、それぞれ計算にO（d）時間を要します。ただし、各ノードはこれらの行によって1回だけ検査されるため、再帰では、これには合計O（n）が必要です。

于 2012-11-21T21:51:59.467 に答える
6

この興味深い問題に対して、単純なO（n）欲張りアルゴリズムがあります。

アルゴリズム

  1. ツリーのルートとして任意の頂点Xを選択し、ルートXとの距離が最大になる頂点Yを見つけます。このステップの複雑さはO（n）です。
  2. ツリーの新しいルートとして頂点Yを作成し、ルートYとの距離が最大になる頂点Zを見つけます。YとZの間の距離は、ツリー内の距離の最大値です。このステップの複雑さもO（n）です。
  3. この欲張りアルゴリズムの全体的な複雑さはO（n）です。

証拠

  • YとZが木の1つの直径を形成していることは明らかであり、YとZを木の角のペアと呼びます。
  • 定理：ツリー内の各頂点Pについて、YまたはZのいずれかが最大距離を持つ頂点になります。
  • アルゴリズムのステップ1は定理に基づいているため、ツリーの1つのコーナー（Y）を簡単に取得できます。
  • 2番目のコーナーZも、定理に基づいて求められます。

拡張する

証明の定理によれば、別のより困難な問題を解決できます。ツリー内の各頂点について、その頂点の最も遠い頂点を計算します。

  • ツリーの2つのコーナーをO（n）の複雑さで見つけることができ、次に定理を再び使用できます。
  • コーナーYとZからそれぞれdfsを実行し、各頂点p [i]について、YとZまでの距離を取得できます（これらをdisY[i]とdisZ[i]と呼びます）。したがって、p[iの最も遠い距離です。 ]はmax（disY [i]、disZ [i]）です。dfsを2回実行するだけなので、O（n）の複雑さで情報を取得できます。
  • この拡張された問題は、複雑さがO（n）である複雑なツリー動的計画法によっても解決できます。
于 2012-11-22T04:06:11.303 に答える
5

2つのノード間の最大長のパスがルートノードを通過するとします。次に、2つのノードの1つは一方の子のサブツリーに属し、もう一方は別の子のサブツリーに属している必要があります。したがって、これらの2つのノードが、これら2つの子の最も低い/最も深い子孫であることが簡単にわかります。つまり、これら2つのノード間の距離はですheight(child1) + height(child2) + 2。したがって、ルートを通過する2つのノード間の最大長のパスはですmax-height-of-a-child + second-to-max-height-of-a-child + 2。

これにより、全体的な最大長のパスを見つけるための単純なO（n）アルゴリズムが得られます。リーフ以外のすべてのノードに対して上記を実行するだけです。すべてのパスはリーフ以外のノードをルートにする必要があるため、これにより、ある時点で正しいパスが考慮されることが保証されます。

サブツリーの高さを見つけることはO（n）ですが、高さを再帰的に積み上げることができるので、すべてのサブツリーの高さを見つけることも便利なことにO（n）です。実際、別のステップとして高さを見つける必要はありません。最大長のパスとサブツリーの高さを同時に見つけることができます。つまり、このアルゴリズムはO（n）時間とO（ツリーの高さ）スペースのみを必要とします。

于 2012-11-21T21:13:12.517 に答える
1

これは再帰的なアルゴリズムです。疑似コード（テストされていないocamlコード）は次のとおりです。

 type result = {n1 : node; n2 : node; d1 : int (* depth of node n1 *); d2 : int; distance: int}
(* a struct containing:
    - the couple of nodes (n1,n2),
    - the depth of the nodes, with depth(n1) >= depth(n2)
    - the distance between n1 & n2 *)


let find_max (n : node) : result =
 let max (s1 : result) (s2 : result) = if s1.distance < s2.distance then s2 else s1 in
 let cl : node list = Node.children n in
 if cl = []
 then { n1 = n; n2 = n; d1 = 0; d2 = 0; distance = 0 }
 else 
   let ml = List.map find_max cl in
   let nl = List.map (fun e -> e.n1, e.d1+1) ml in
   let (k1,d1)::(k2,d2)::nl = nl in
   let k1,d1,k2,d2 = if d1 > d2 then k1,d1,k2,d2 else k2,d2,k1,d1 in
   let s = {n1 = k1;n2 = k2; d1 = d1; d2 = d2; distance = d1+d2} in
   let m1 =  List.fold_left (fun r (e,d) -> 
                      if r.d1< d
                      then { r with n1 = e; d1 = d; distance = d+d2 }
                      else if r.d2 < d 
                               then { r with n2 = e; d2 = d; distance = d+d1 }
                               else r) s nl in
   max m1 (List.fold_left max (List.hd ml) (List.tl ml))

m1値は、nlリストの最も深い2つのノードを保持することによって作成され、距離はそれらの深さの合計です。

List.mapリストのすべての要素に特定の関数を適用し、結果のリストを返す関数です。

List.fold_leftは、前のアプリケーションの結果を新しいアキュムレータ値として使用するたびに、指定された関数をアキュムレータとリストの要素に再帰的に適用する関数です。結果は最後のアキュムレータ値です。

List.hdリストの最初の要素を返します。

List.tl最初の要素のないリストを返します。

于 2012-11-21T22:12:17.170 に答える