1

今週の日曜日に試験があるんだけど、自分がやっていることは正しいかどうかを確認したいだけなんだ (試験は私を懐疑的にするんだよね)

アルゴリズムの仕組みは次のとおりです。

int Find(int x)
{ // Return the set containing x and compress the path from x to root
  // First, find the root
int z = x; while (P[z] > 0) { z = P[z]; } int root = z;
// Start at x again and reset the parent // of every node on the path from x to root z = x;
while (P[z] > 0)
{ int t = P[z];
     P[z] = root; // Reset Parent of z to root
z = t; }
return root; }

これは質問です：

n 個の要素の集合から素集合に対する Union-Find 問題のために開発されたアルゴリズムを思い出してください。Find はパス圧縮を使用し、Union はランキングを使用します。また、同じランクの 2 つのツリーの和集合は、2 番目の引数に関連付けられたルートを新しいルートとして選択します。セット S = {1, 2, ..., 10} と 10 個の互いに素な部分集合 (それぞれが 1 つの要素を含む) から始めます。を。
Union(1,2)、Union(3,4)、Union(5,6)、Union(1,5)、Union(1,3)を実行した後、ツリーの最終セットを描画します。

そして、これは質問に対する私の解決策です：

ここに画像の説明を入力

このアルゴリズムに関するヒントや提案があれば幸いです。

ありがとう！

4

1 に答える 1

0

の検索操作のポイントUnion-Find Setはパスの圧縮です。

r1集合 Aのルートが であり、集合 B のルートが であることがわかっている場合、r2集合 A と集合 B を結合するとします。最も簡単な方法は、セット B のルートをセット A のルートにすることです。つまり、father[r2] = r1;

しかし、それはそれほど「賢い」とは言えませんr2。私たちが言うように、息子xがその根を知りたがり、父親にx尋ねr2、次に父親r2が自分の父親r1である blabla に根まで尋ねますr1。x次にのルートをもう一度尋ねたときに、xその父親にr1「私たちのルートは何ですか?r1 」と尋ねると、前のループをもう一度繰り返す必要はありません。はルートがであることをr1すでに知っているので、直接 に戻すことができます。r2r1x

簡単に言えば、xのルートはx父親のルートでもあります。したがって、パス圧縮を実装する方法を取得します(再帰の方が簡単だと思います)。

int Find(int x)
{
    // initial each element's root as itself, which means father[x] = x;
    // if an element finds its father is itself, means root is found
    if(x == father[x])
        return father[x];
    int temp = father[x];
    // root of x's father is same with root of x's father's root
    father[x] = Find(temp);
    return father[x];
}

パス圧縮された検索操作の時間の複雑さについては、非常に高いパフォーマンスです。http://www.gabrielnivasch.org/fun/inverse-ackermannを参照してください。

于 2015-02-09T13:32:54.870 に答える