アルゴリズム#08--union-findアルゴリズムを深く詳細に解き、収集する
union-findアルゴリズムを深く詳細に解き、収集する
どうてきせつぞくせい
1.問題の説明
各整数が何らかのタイプのオブジェクトを表す一連の整数ペアを入力し、一対の整数pqは「pとqは接続されている」と理解することができる.
接続は対等な関係であり、以下の性質が必要です.自己反転:pとpは接続されている. 対称性:pとqが接続されている場合、qとpも接続されている. 伝達性:pとqが接続され、qとrも接続されている場合、pとrも接続されている.
次の図の(4,3)(3,8)などの整数ペアを入力したとします.各ペアの整数は、この2つのpoints/sitesが連通していることを表します.データの入力が進むにつれて、図全体の連通性も変化し、上図からこの点が明確に発見される.同時に、すでに連通状態にあるpoints/sitesについては、上図の(8,9)のように直接無視される.
2.シーンの適用ネットワーク:整数は、大規模なコンピュータネットワーク内のコンピュータである可能性があり、整数対は、ネットワーク内の無数の接続を表す.このプログラムは、pとqの間に新しい接続を架けて通信する必要があるかどうかを判断することができます. 変数名等同性(ポインタの概念に似ている):プログラムでは、複数の参照を宣言して同じオブジェクトを指すことができ、このとき、プログラムで宣言された参照と実際のオブジェクトに動的連通図を作成することで、実際に同じオブジェクトを指す参照を判断することができます. 数学集合:より高い抽象階層では、入力されたすべての整数を異なる数学集合に属すると見なすことができる.整数対pqを処理するとき,それらが同じ集合に属するか否かを判断する.そうでなければ、最終的にはすべての整数が同じ集合に属します.
3.数学モデリング
問題をモデリングするときは、解決すべき問題が何なのかをできるだけよく考えなければなりません.モデルで選択したデータ構造とアルゴリズムは明らかに問題によって異なるため、動的連通性というシーンでは、解決すべき問題は次のような可能性があります.は、2つのノードを与える、それらが連通しているか否かを判断し、連通している場合、具体的な経路 を与える必要はない.は2つのノードを与え、それらが連通か否かを判断し、連通する場合、具体的な経路 を与える必要がある.
上記の2つの問題については,特定の経路の違いを与えることができるかどうかのみであるが,この違いは選択アルゴリズムの違いをもたらし,本稿では,特定の経路を与える必要のないUnion−Findアルゴリズム,第2のケースではDFSベースのアルゴリズムを用いることができる第1のケースを主に紹介する.
quick-findアルゴリズム
1. API
注記:ノードを表すには整数を使用します.文字列などの他のデータ型を使用する必要がある場合は、Stringをここで必要なIntegerタイプにマッピングするハッシュ・テーブルを使用します.
2.原理
例えば、入力された整数ペアが(5,9)である場合、まずfindメソッドでグループ番号が異なることを発見し、unionのときに1回の遍歴でグループ番号1を8に変更します.もちろん、8から1に変更しても構いませんが、いずれも1つのルールを使って操作すればいいのです.
3.コード
出力:
軌跡は次の図です.
4.アルゴリズム分析 union(p,q)は配列回数N+3~2 N+1 にアクセスする.最良の場合、union(p,q)アクセス配列N+3回、N個の整数はN−1回統合union(p,q)操作を行い、アクセス配列(N+3)(N−1)~N^2となる. quick-unionアルゴリズムは平方レベルである.
quick-unionアルゴリズム
1.原理
考えてみると、なぜ以上の解法が「一発で全身を動かす」のか.
各ノードが属するグループ番号は単独で記録されているため、それぞれが政治的であり、より良い方法で組織されていない.修正にかかわる場合、一つ一つ通知し、修正する以外に方法がない.だから今の問題は、どのようにノードをより良い方法で組織するか、組織する方法はたくさんありますが、最も直感的なのはグループ番号の同じノードを組織して、学んだデータ構造を考えて、どのようなデータ構造がいくつかのノードを組織することができますか?よくあるのはチェーン時計、図、木などです.しかし、どの構造が検索と修正に最も効率的ですか?ツリーであることは間違いないので,ノードとグループの関係をツリーとしてどのように表現するかを考える.
下位データ構造を変更しない、すなわち配列を用いた表現方法を変更しない場合.parent-linkでノードを整理できます.
たとえば、id[p]の値はpノードの親ノードのシーケンス番号であり、pがツリールートであればid[p]の値はpであるため、最後にいくつかの検索を経て、1つのノードは常にそのルートノードを見つけることができ、すなわちid[root]=rootを満たすノード、すなわちグループのルートノードであり、その後、ルートノードのシーケンス番号を使用してグループ番号を表すことができる.したがって、1つの整数ペアを処理するときに、まず整数ペアの各ノードのグループ番号(すなわち、ツリーのルートノードのシーケンス番号)が見つかり、異なるグループに属する場合は、1つのルートノードの親ノードを別のルートノードに設定し、1つの独立したツリーを別の独立したツリーのサブツリーにプログラミングすることに相当します.
2.コード
インプリメンテーションでは、以前のQuick-Findとunionの2つの方法とは異なります.
3.アルゴリズム分析
quick-unionアルゴリズムは、各入力の配列全体を巡回する必要がないため、quick-findアルゴリズムブロックよりも見えます.
①最良の場合find(p)は、一度だけ配列にアクセスし、このとき接点pはルート接点
②最悪の場合find(p)、アクセス配列2 N-1回
while(p != id[p]) p = id[p];
最悪の場合、接点pが存在する連通成分に対応するツリーは線形テーブルに劣化し、1つの連通成分のみが存在し、pは線形テーブルの表尾にある.while()ループの判定条件はN次配列にアクセスし、while()ループの実行体はN-1次配列にアクセスする(最後にルートノードに到達した場合、ループ体は実行しない).合計2 N-1回.
このことからfind(p)が配列にアクセスする回数は,接点pに対応するノードがツリーの高さで決定される.pのツリーにおける高さをhとすると,アクセス配列の回数は2 h+1回である.
いくつかの定義について:
秩序整数対0−1,0−2,0−3…0−Nが入力されると仮定し,N−1対以降のN個の接点はすべて同一の連通成分内にあり(main()を参照),quick−unionアルゴリズムにより得られたツリーの高さはN−1であり,そのうち0→1,1→2...N−1→Nである.
整数対0-iの場合、union(0,i)が実行され、2 i+1次配列にアクセスします.
①ここで0のルート接点はi-1,高さはi-1であり,3,find(0)アクセス配列により2 i-1回
②ここでiのルート接点はi,高さは0であり,3,find(i)アクセス配列により1回
③i-1のルート接点(原指向そのもの、現指向接点i)の配列内容をiとし、配列に1回アクセスする
本の上で2 i+2回で、私は0-iが連通していることを分析して、このように0のルート接点はiで、iのルート接点はiで、find(0)は2 i+1回、find(i)は1回の計2 i+2回訪問します.main()メソッドによれば、この場合0とiは連通しないはずです.
整数に対するNの処理に必要なすべてのfind()操作へのアクセスは、Σ(1→N)(2i) = 2(1+2+…N) ~N^2
quick-unionとquick-findは両方とも平方レベルの**であることがわかります.
重み付けquick-unionアルゴリズム
1.原理
上のquick-unionアルゴリズムの効率が低い(平方レベル)のは,union(p,q)法が,1本の木を勝手に別の木に接続する(1本の木が1つの連通成分に対応する)ことが主な原因である.小さな木(高さが低い)が大きな木のルートノード(高さが高い)に接続されている場合、小さな木の高さは1を加え、木全体の高さは変わらない. 大木(高さ)が小木の根ノード(高さが低い)に接続されている場合、大木の高さは1を加え、木全体の高さは元の小木の高さから大木の高さに1を加える.
quick−unionアルゴリズム解析によればfind(p)がアクセスする配列の回数はノードpが存在する高さに関係する.高さが高いほど、配列にアクセスする回数が多くなります.
このことから,アクセス配列の回数を減らし,アルゴリズム効率を向上させるためにunion(p,q)操作を実行する際に,ケース1,すなわちツリーが大木に接続されていることを確保する.このため、接点pが存在する連通成分に含まれる接点(接点が多ければ多いほど、対応するツリーのノードが多ければ多いほど、大きな木)を記録する配列sz[]が必要となる.
もちろん、pとqが存在する連通成分に対応するツリーの高さが等しい場合もあり、この場合、pがqに接続されていてもqがpに接続されていても、ツリーの高さは増加する.重み付けquick−unionアルゴリズムでは,これが最悪の場合である.
従って、重み付けquick−unionからなるツリーの高さは、重み付けされていない構造のツリーの高さよりはるかに小さい.
Quick-Unionと重み付けQuick-Unionの比較:
2.コード
コードダウンロードアドレス:
https://github.com/tclxspy/Articles/blob/master/algorithm/Code/WeightedQuickUnionUF.java
出力は同じです.
3.アルゴリズム分析
①最悪の場合:
集計されるツリーのサイズは常に等しい(常に2^n).各ツリーは2^nノードを含む満二叉木であるため,高さはちょうどnである.2^nノードを含む2つのツリーを集計すると、2^(n+1)ノードを含む本が得られ、これによりツリーの高さがn+1に増加する.このことから,重み付けquick−unionアルゴリズムは対数レベルであることが分かった.すなわち,N個の接点で構成される木に対して最も高い高さはlgNである.
次のように推論されます.
②最悪の場合はどうやって?
簡単な解析から,重み付けquick−unionアルゴリズムでは線形テーブルが得られないことが分かった(重み付けされていないquick−unionは線形テーブルに劣化したツリーを生じる).したがって,各層のノードが多ければ多いほど,木の高さは小さくなる.最悪の場合、二叉木がいっぱいです.
③重み付けquick-unionアルゴリズムはN個の接点を処理し、M本接続時には配列cMlgN回までアクセスする.
cは定数である.接続を処理するたびにunion(p,q)メソッドが呼び出されます.一方union(p,q)はlgNレベルである.lg[height(p)]+lg[height(q)]+5=clgN,5はunionメソッドでif else文が配列にアクセスした回数である.M回はcMlgN)である.一方、quick-findアルゴリズムおよび場合によっては重み付けされていないquick-unionアルゴリズムは、少なくとも配列MNにアクセスする.
要約
どうてきせつぞくせい
1.問題の説明
各整数が何らかのタイプのオブジェクトを表す一連の整数ペアを入力し、一対の整数pqは「pとqは接続されている」と理解することができる.
接続は対等な関係であり、以下の性質が必要です.
次の図の(4,3)(3,8)などの整数ペアを入力したとします.各ペアの整数は、この2つのpoints/sitesが連通していることを表します.データの入力が進むにつれて、図全体の連通性も変化し、上図からこの点が明確に発見される.同時に、すでに連通状態にあるpoints/sitesについては、上図の(8,9)のように直接無視される.
2.シーンの適用
3.数学モデリング
問題をモデリングするときは、解決すべき問題が何なのかをできるだけよく考えなければなりません.モデルで選択したデータ構造とアルゴリズムは明らかに問題によって異なるため、動的連通性というシーンでは、解決すべき問題は次のような可能性があります.
上記の2つの問題については,特定の経路の違いを与えることができるかどうかのみであるが,この違いは選択アルゴリズムの違いをもたらし,本稿では,特定の経路を与える必要のないUnion−Findアルゴリズム,第2のケースではDFSベースのアルゴリズムを用いることができる第1のケースを主に紹介する.
quick-findアルゴリズム
1. API
注記:ノードを表すには整数を使用します.文字列などの他のデータ型を使用する必要がある場合は、Stringをここで必要なIntegerタイプにマッピングするハッシュ・テーブルを使用します.
2.原理
例えば、入力された整数ペアが(5,9)である場合、まずfindメソッドでグループ番号が異なることを発見し、unionのときに1回の遍歴でグループ番号1を8に変更します.もちろん、8から1に変更しても構いませんが、いずれも1つのルールを使って操作すればいいのです.
3.コード
import java.util.Scanner;
public class UF {
private int[] id; // id（ ）
private int count; //
public UF(int N)
{
// id .
count = N;
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
return id[p];
}
public void union(int p, int q) {
// p q
int pID = find(p);
int qID = find(q);
// ，
if (pID == qID) return;
// ，
for (int i = 0; i < id.length; i++)
if (id[i] == pID) id[i] = qID;
count--;
}
public static void main(String[] args) {
String data = "4 3 3 8 6 5 9 4 2 1 5 0 7 2 6 1";
Scanner sc = new Scanner(data);
UF uf = new UF(10);
while (sc.hasNext()) {
int p = sc.nextInt();
int q = sc.nextInt();
if(uf.connected(p, q) ) {
continue;
}
uf.union(p, q);
System.out.println(p+ " " + q);
}
sc.close();
System.out.println(uf.count() + " ");
}
}出力:
4 3
3 8
6 5
9 4
2 1
5 0
7 2
6 1
2 軌跡は次の図です.
4.アルゴリズム分析
：
(1) find() ， 2
(2) id[]， p q f if(find(i)==pID)， N
(3)① p， p id[p] =qID, 1
② q ， p id[i] = qID(i≠q)， N-1 ，
①2+N+1 = N+3②2+N+N-1 = 2N+1quick-unionアルゴリズム
1.原理
考えてみると、なぜ以上の解法が「一発で全身を動かす」のか.
各ノードが属するグループ番号は単独で記録されているため、それぞれが政治的であり、より良い方法で組織されていない.修正にかかわる場合、一つ一つ通知し、修正する以外に方法がない.だから今の問題は、どのようにノードをより良い方法で組織するか、組織する方法はたくさんありますが、最も直感的なのはグループ番号の同じノードを組織して、学んだデータ構造を考えて、どのようなデータ構造がいくつかのノードを組織することができますか?よくあるのはチェーン時計、図、木などです.しかし、どの構造が検索と修正に最も効率的ですか?ツリーであることは間違いないので,ノードとグループの関係をツリーとしてどのように表現するかを考える.
下位データ構造を変更しない、すなわち配列を用いた表現方法を変更しない場合.parent-linkでノードを整理できます.
たとえば、id[p]の値はpノードの親ノードのシーケンス番号であり、pがツリールートであればid[p]の値はpであるため、最後にいくつかの検索を経て、1つのノードは常にそのルートノードを見つけることができ、すなわちid[root]=rootを満たすノード、すなわちグループのルートノードであり、その後、ルートノードのシーケンス番号を使用してグループ番号を表すことができる.したがって、1つの整数ペアを処理するときに、まず整数ペアの各ノードのグループ番号(すなわち、ツリーのルートノードのシーケンス番号)が見つかり、異なるグループに属する場合は、1つのルートノードの親ノードを別のルートノードに設定し、1つの独立したツリーを別の独立したツリーのサブツリーにプログラミングすることに相当します.
2.コード
インプリメンテーションでは、以前のQuick-Findとunionの2つの方法とは異なります.
public int find(int p) {
// p ， id[root] = root
while (p != id[p]) p = id[p];
return p;
}
public void union(int p, int q) {
// p q
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot)
return;
id[pRoot] = qRoot; // ( ) ( )
count--;
} 3.アルゴリズム分析
quick-unionアルゴリズムは、各入力の配列全体を巡回する必要がないため、quick-findアルゴリズムブロックよりも見えます.
①最良の場合find(p)は、一度だけ配列にアクセスし、このとき接点pはルート接点
②最悪の場合find(p)、アクセス配列2 N-1回
while(p != id[p]) p = id[p];
最悪の場合、接点pが存在する連通成分に対応するツリーは線形テーブルに劣化し、1つの連通成分のみが存在し、pは線形テーブルの表尾にある.while()ループの判定条件はN次配列にアクセスし、while()ループの実行体はN-1次配列にアクセスする(最後にルートノードに到達した場合、ループ体は実行しない).合計2 N-1回.
このことからfind(p)が配列にアクセスする回数は,接点pに対応するノードがツリーの高さで決定される.pのツリーにおける高さをhとすると,アクセス配列の回数は2 h+1回である.
いくつかの定義について:
秩序整数対0−1,0−2,0−3…0−Nが入力されると仮定し,N−1対以降のN個の接点はすべて同一の連通成分内にあり(main()を参照),quick−unionアルゴリズムにより得られたツリーの高さはN−1であり,そのうち0→1,1→2...N−1→Nである.
整数対0-iの場合、union(0,i)が実行され、2 i+1次配列にアクセスします.
①ここで0のルート接点はi-1,高さはi-1であり,3,find(0)アクセス配列により2 i-1回
②ここでiのルート接点はi,高さは0であり,3,find(i)アクセス配列により1回
③i-1のルート接点(原指向そのもの、現指向接点i)の配列内容をiとし、配列に1回アクセスする
本の上で2 i+2回で、私は0-iが連通していることを分析して、このように0のルート接点はiで、iのルート接点はiで、find(0)は2 i+1回、find(i)は1回の計2 i+2回訪問します.main()メソッドによれば、この場合0とiは連通しないはずです.
整数に対するNの処理に必要なすべてのfind()操作へのアクセスは、Σ(1→N)(2i) = 2(1+2+…N) ~N^2
quick-unionとquick-findは両方とも平方レベルの**であることがわかります.
重み付けquick-unionアルゴリズム
1.原理
上のquick-unionアルゴリズムの効率が低い(平方レベル)のは,union(p,q)法が,1本の木を勝手に別の木に接続する(1本の木が1つの連通成分に対応する)ことが主な原因である.
quick−unionアルゴリズム解析によればfind(p)がアクセスする配列の回数はノードpが存在する高さに関係する.高さが高いほど、配列にアクセスする回数が多くなります.
このことから,アクセス配列の回数を減らし,アルゴリズム効率を向上させるためにunion(p,q)操作を実行する際に,ケース1,すなわちツリーが大木に接続されていることを確保する.このため、接点pが存在する連通成分に含まれる接点(接点が多ければ多いほど、対応するツリーのノードが多ければ多いほど、大きな木)を記録する配列sz[]が必要となる.
もちろん、pとqが存在する連通成分に対応するツリーの高さが等しい場合もあり、この場合、pがqに接続されていてもqがpに接続されていても、ツリーの高さは増加する.重み付けquick−unionアルゴリズムでは,これが最悪の場合である.
従って、重み付けquick−unionからなるツリーの高さは、重み付けされていない構造のツリーの高さよりはるかに小さい.
Quick-Unionと重み付けQuick-Unionの比較:
2.コード
コードダウンロードアドレス:
https://github.com/tclxspy/Articles/blob/master/algorithm/Code/WeightedQuickUnionUF.java
import java.util.Scanner;
public class WeightedQuickUnionUF {
private int[] id; // id（ ）
private int[] sz; // （ ）
private int count; //
public WeightedQuickUnionUF(int N)
{
// id .
count = N;
id = new int[N];
sz = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
sz[i] = 1;
}
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
// p ， id[root] = root
while (p != id[p]) p = id[p];
return p;
}
public void union(int p, int q) {
int i = find(p);
int j = find(q);
if (i == j) return;
//
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
}
else {
id[j] = i;
sz[i] += sz[j];
}
count--;
}
public static void main(String[] args) {
String data = "4 3 3 8 6 5 9 4 2 1 5 0 7 2 6 1";
Scanner sc = new Scanner(data);
WeightedQuickUnionUF uf = new WeightedQuickUnionUF(10);
while (sc.hasNext()) {
int p = sc.nextInt();
int q = sc.nextInt();
if(uf.connected(p, q) ) {
continue;
}
uf.union(p, q);
System.out.println(p+ " " + q);
}
sc.close();
System.out.println(uf.count() + " ");
}
}出力は同じです.
3.アルゴリズム分析
①最悪の場合:
集計されるツリーのサイズは常に等しい(常に2^n).各ツリーは2^nノードを含む満二叉木であるため,高さはちょうどnである.2^nノードを含む2つのツリーを集計すると、2^(n+1)ノードを含む本が得られ、これによりツリーの高さがn+1に増加する.このことから,重み付けquick−unionアルゴリズムは対数レベルであることが分かった.すなわち,N個の接点で構成される木に対して最も高い高さはlgNである.
次のように推論されます.
②最悪の場合はどうやって?
簡単な解析から,重み付けquick−unionアルゴリズムでは線形テーブルが得られないことが分かった(重み付けされていないquick−unionは線形テーブルに劣化したツリーを生じる).したがって,各層のノードが多ければ多いほど,木の高さは小さくなる.最悪の場合、二叉木がいっぱいです.
③重み付けquick-unionアルゴリズムはN個の接点を処理し、M本接続時には配列cMlgN回までアクセスする.
cは定数である.接続を処理するたびにunion(p,q)メソッドが呼び出されます.一方union(p,q)はlgNレベルである.lg[height(p)]+lg[height(q)]+5=clgN,5はunionメソッドでif else文が配列にアクセスした回数である.M回はcMlgN)である.一方、quick-findアルゴリズムおよび場合によっては重み付けされていないquick-unionアルゴリズムは、少なくとも配列MNにアクセスする.
要約