2

アンバランス ツリーを (バランスのとれた) スパニング ツリーに変換する方法は? ツリーがあるとします（異なるノードで異なる（必ずしも異なる）数の子を持つ）。k-aryスパニングツリーになるようにツリーを操作したい。

ツリーでのさまざまな反復が許可されます。制限は、すべてのノードを 1 か所に集めて、それらからスパニング ツリーを作成することはできないということです (これは簡単な方法です)。むしろ、指定されたツリーからスパニング ツリーを作成する必要があります。つまり、子は親 (および必要に応じて祖父母) と情報 (子ノードの数や子ノードの ID など) を交換でき、親は子の間でノードを移動することを決定します (順番に木のバランスをとります）。

並列コンピューティング環境でこれを行おうとしていることは理解できたかもしれません。ここで、ノードが知っているのは、その親、その子のID、およびその子をルートとする各サブツリー内のノードの数だけです。

(ツリーのバランスをとろうとすると、親と子が変わります)。この問題にアプローチする方法についてのヒントはありますか?

なぜこの問題が重要なのか、検討する価値があるのか​​というコメントに返信してください。

  1. 理論的には、スパニング ツリーを構築するために (自明なアプローチで使用される) O(N) 未満のスペースを使用するアルゴリズムを開発することは困難です。

  2. 大規模な代替ソリューション アプローチについて考えるのは興味深いことです。

  3. 数値に関する限り、N=100,000 (これは今日のスーパーコンピューターでは一般的ですが、N は次の BG/Q では 1000,000 になります)。含まれる単純なアプローチの手順は、a) all-reduce、b) スパニング ツリーを構築するための O(N)、および c) 最後に 1 対多のブロードキャストです。

別の分散型アプローチではあまり改善されないかもしれませんが、好奇心から試してみる価値があるかもしれません。

4

2 に答える 2

1

適切なアルゴリズムの断片でのいくつかのランダムな熟考:

  1. 「ルート」を任意に選択します。おそらく、参加している要素の中で最もインデックスの低い要素として、または既存の構造のルートとして選択します。
  2. 「フェーズ」は、ツリーの最も深い部分と、まだ飽和していないツリーの最も浅い部分の深さと同一性を計算する 1 つの並列削減と考えてください。
  3. 各フェーズの後、ルートは適切な数のノードの動きを最も深い部分から浅い部分に向けて、深さごとにバランスを取ります。
  4. 完全にバランスが取れるまで繰り返す

これは、AVL 基準のようなものに従って各近隣がバランスを取り、最終的に大きな構造変化が伝播する、完全に分散された方法でも機能する可能性があります。

于 2011-05-16T02:31:01.850 に答える