【並列調査セット】交差しない集合-並列調査チュートリアル(著者:Slyar)
最近1週間以上書いて調べて、一瞬にしてこんなにたくさんの解題レポートが貼られたので、まとめの応用については一段落しようと思いますが、まとめておきます.
ネットで见て良いチュートリアルを调べると(一応言わせてください)、回らないのはもったいないです.勉强好きのあなたに捧げます
作者:Slyar文章来源:Slyar Home(www.slyar.com)転載ご明記ください.ご協力ありがとうございます.
等価関係と等価類
数学的に見ると、等価クラスはオブジェクト(またはメンバー)の集合であり、この集合内のすべてのオブジェクトが等価関係を満たす必要があります.集合上の等価関係を記号「≡」で表すと,その集合中の任意の対象x,y,zに対して,以下の性質が成り立つ.
1、自己反転性:x≡x
2、対称性:x≡yならy≡x
3、伝達性:x≡yかつy≡zならx≡z
したがって,等価関係は集合上の自己反転,対称,伝達の関係である.
金属線で接続された電気製品の連通性は、等価関係である.この関係は明らかに自己反転性を有する.なぜなら、どのデバイスも自己と連通しているからである.aがbに電気的に連通している場合、bもaに電気的に連通しているに違いないので、この関係は対称性を有する.aがbに連通し、bがcに連通している場合、aはcに連通している.
コレクションを調べる
そして,コレクションの一般的な用途は,ある種の自己反転,対称,伝達特性を有する関係を維持するための等価類である.そして、セットは一般的に木の構造で格納され、複数の木が1つの森を構成し、各木が1つの集合を構成し、木の中の各ノードがその集合の要素であり、代表要素をその木(集合)の祖先として探している.
調査セットでは、次の3つの操作がサポートされています.
1、Make_Set(x)は各要素を1つの集合に初期化する
初期化後の各要素の親ノードはそれ自体であり、各要素の祖先ノードもそれ自体である.
2、Find_Set(x)は、要素が存在する集合を検索します.
エレメントが存在する集合を検索します.このエレメントが存在する集合の祖先を見つければいいです.2つの要素が同じ集合に属しているかどうかを判断するには、彼らが集合している祖先が同じかどうかを見るだけです.
3、Union(x,y)はx,yが存在する2つの集合を合併する
2つの非交差集合をマージする操作は簡単です.まず、xの「父親」の番号を表す配列Father[x]を設定します.では、2つの交差しない集合を統合する方法は、そのうちの1つの集合の祖先を見つけ、別の集合の祖先を指すことです.
セットの最適化を調べる
1、Find_Set(x)時パス圧縮
祖先を探すときは再帰的に探すのが一般的ですが、要素が多くなったり、木全体がチェーンになったりするたびにFind_Set(x)はすべてO(n)の複雑さで、この複雑さを減らす方法はありませんか?
答えは肯定的で、これは経路の圧縮で、つまり私達が“プッシュ”を通じて祖先のノードを探し当てた後に、“回帰”の時ついでにその子孫のノードをすべて直接祖先に指して、このように後で再びFind_Set(x)では複雑度がO(1)となる.
2、ユニオン(x,y)の場合はランクでマージ
つまり、結合時に要素の少ない集合を要素の多い集合に結合すると、結合後のツリーの高さが相対的に小さくなります.
プライマリコード実装
+++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++
関連テーマ
セットの基礎的な適用を調べます.
POJ 1611 The Suspects C言語版
POJ 2524 Ubiquitous Religions C言語版
POJ 1182食物連鎖C言語版
最小生成ツリーKruskalアルゴリズムと検索セット応用:
POJ 1258 Agri-net C言語版Kruskal
POJ 1251 Jungle Roads C++版Kruskal
POJ 1861 Network C言語版Kruskal
記事の作成者:
Slyar
出典:Slyar Home(www.slyar.com)
)転載は明記してください.ご協力ありがとうございます.
ネットで见て良いチュートリアルを调べると(一応言わせてください)、回らないのはもったいないです.勉强好きのあなたに捧げます
作者:Slyar文章来源:Slyar Home(www.slyar.com)転載ご明記ください.ご協力ありがとうございます.
等価関係と等価類
数学的に見ると、等価クラスはオブジェクト(またはメンバー)の集合であり、この集合内のすべてのオブジェクトが等価関係を満たす必要があります.集合上の等価関係を記号「≡」で表すと,その集合中の任意の対象x,y,zに対して,以下の性質が成り立つ.
1、自己反転性:x≡x
2、対称性:x≡yならy≡x
3、伝達性:x≡yかつy≡zならx≡z
したがって,等価関係は集合上の自己反転,対称,伝達の関係である.
金属線で接続された電気製品の連通性は、等価関係である.この関係は明らかに自己反転性を有する.なぜなら、どのデバイスも自己と連通しているからである.aがbに電気的に連通している場合、bもaに電気的に連通しているに違いないので、この関係は対称性を有する.aがbに連通し、bがcに連通している場合、aはcに連通している.
コレクションを調べる
そして,コレクションの一般的な用途は,ある種の自己反転,対称,伝達特性を有する関係を維持するための等価類である.そして、セットは一般的に木の構造で格納され、複数の木が1つの森を構成し、各木が1つの集合を構成し、木の中の各ノードがその集合の要素であり、代表要素をその木(集合)の祖先として探している.
調査セットでは、次の3つの操作がサポートされています.
1、Make_Set(x)は各要素を1つの集合に初期化する
初期化後の各要素の親ノードはそれ自体であり、各要素の祖先ノードもそれ自体である.
2、Find_Set(x)は、要素が存在する集合を検索します.
エレメントが存在する集合を検索します.このエレメントが存在する集合の祖先を見つければいいです.2つの要素が同じ集合に属しているかどうかを判断するには、彼らが集合している祖先が同じかどうかを見るだけです.
3、Union(x,y)はx,yが存在する2つの集合を合併する
2つの非交差集合をマージする操作は簡単です.まず、xの「父親」の番号を表す配列Father[x]を設定します.では、2つの交差しない集合を統合する方法は、そのうちの1つの集合の祖先を見つけ、別の集合の祖先を指すことです.
セットの最適化を調べる
1、Find_Set(x)時パス圧縮
祖先を探すときは再帰的に探すのが一般的ですが、要素が多くなったり、木全体がチェーンになったりするたびにFind_Set(x)はすべてO(n)の複雑さで、この複雑さを減らす方法はありませんか?
答えは肯定的で、これは経路の圧縮で、つまり私達が“プッシュ”を通じて祖先のノードを探し当てた後に、“回帰”の時ついでにその子孫のノードをすべて直接祖先に指して、このように後で再びFind_Set(x)では複雑度がO(1)となる.
2、ユニオン(x,y)の場合はランクでマージ
つまり、結合時に要素の少ない集合を要素の多い集合に結合すると、結合後のツリーの高さが相対的に小さくなります.
プライマリコード実装
+++++++++++++++++++++++++++++++++++++++
/* father[x] x */
int father[MAX];
/* rank[x] x */
int rank[MAX];
/* */
void Make_Set(int x)
{
father[x] = x;
rank[x] = 0;
}
/* x , */
int Find_Set(int x)
{
if (x != father[x])
{
father[x] = Find_Set(father[x]);
}
return father[x];
}
/* x,y */
void Union(int x, int y)
{
x = Find_Set(x);
y = Find_Set(y);
if (x == y) return;
if (rank[x] > rank[y])
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
}
+++++++++++++++++++++++++++++++++++++++
関連テーマ
セットの基礎的な適用を調べます.
POJ 1611 The Suspects C言語版
POJ 2524 Ubiquitous Religions C言語版
POJ 1182食物連鎖C言語版
最小生成ツリーKruskalアルゴリズムと検索セット応用:
POJ 1258 Agri-net C言語版Kruskal
POJ 1251 Jungle Roads C++版Kruskal
POJ 1861 Network C言語版Kruskal
記事の作成者:
Slyar
出典:Slyar Home(www.slyar.com)
)転載は明記してください.ご協力ありがとうございます.