コース内容#
- 併合集合：合併集合 [連結関係を構築]、探索集合の連結関係 [2 つの点が連結しているかどうかを判断]
連結性問題#
-
-
ルール：すでに連結関係を持つ点は再接続できない
-
すべての点を 2 つの集合に分ける：①、②
-
[PS] 点と点の関係（合併、連結判断）→集合と集合の関係でもある
Quick-Find アルゴリズム#
- 中心思想：染色
- 1 つの色は 1 つのカテゴリに対応
- 初期化：個体は独立しており、自分のインデックスを書き込み、独立した集合に属する
- ⭐自分と連結しているすべての点の色を染める色に変更する
- 時間計算量
- 連結判断：O (1)—— 探索が速いため Quick-Find と呼ばれる
- 合併操作：O (N)—— すべての点を遍歴して合併するかどうかを決定する必要がある
- 🆒考えを引き起こす：なぜ「森林」と呼ばれるのか？
- 重要なのは合併操作であり、いくつかの点といくつかの点の合併、集合と集合の合併
- 子木と子木の間の合併、または 1 つの木を別の木の子木として扱うことに似ている
- すべての集合を一緒に置くと、すべての木を一緒に置くことになり、それが森林である
- では、染色以外の方法はあるのか？
- 考える：何色に染めるかは重要ではなく、どの点の色が同じか、つまり連結しているかを知るだけでよい
Quick-Union アルゴリズム#
- 生活のヒント：兄貴を探す、リーダーを探す
- 中心思想：代表要素を探す [根ノード]
- 保存される値はその代表要素である
- 初期化：個体は独立しており、自分のインデックスを書き込み、独立した集合に属する
- ⭐2 つの点の代表要素を見つけ、1 つの代表要素の値を別の代表要素の値に変更する
- 代表要素：内部の値はそれ自身である
- 連想：兄貴や彼の弟が反乱を起こすと、すべて兄貴から反乱が始まり、別の弟の兄貴に反乱する
- Quick-Find の結果と同じで、1 つの子木全体を別の子木に合併するが、代表要素を通じて実現される
- 根ノードが根ノードを指すことができる
- 時間計算量
- すべて根ノードを探す必要があり、木の高さに関連する
- 連結操作：O（木の高さ）
- 合併操作：O（木の高さ）
- ❗ 2 つの状況
- 正常状態→すべて O (logN)
- 退化して 1 つの連結リストになる→すべて O (N)
- 退化した場合、どう解決するのか？👇
weighted Quick-Union アルゴリズム#
【ランクによる合併】
- 退化を避けるには？→枝が繁茂することを保証する
- 合併基準 1：木の高さ、低い木は高い木の下にぶら下がる [2 つずつ結合]
- 高さが h の木には、少なくとも必要なノード数 N は 2 ^ (h - 1)
- つまり、木の高さ h = log [2] N + 1 ≈ log [2] N
- [PS] 同じ高さの 2 つの木が合併する場合のみ、高さが増加する
- 合併基準 2：ノード数、ノードが少ない木はノードが多い木の下にぶら下がる
- 2 つの最適化方法は O (logN) を得るが、合併基準 2【ノード数】の方が優れている
- 合併基準 1：木の高さ、低い木は高い木の下にぶら下がる [2 つずつ結合]
- ⭐なぜ合併基準 2 が優れているのか
- 【例】平均探索回数とは何か
- 以下の図に示すように、A、B 木の平均探索回数を計算した
-
- ノードの深さはノードの探索回数であり、平均探索回数 = 総探索回数 / 総ノード数
- この例では、B 木の探索操作がより速い
- 【導出】合併基準 2 は平均探索回数を直接決定する
- SA、SB 個のノードを持つ A、B 木に対して、それらの総探索回数 LA、LB はそれぞれ：
-
- ここで、li は i 番目のノードの深さを表す
-
- この時、合併操作を行い、①A→B と②B→A の平均探索回数をそれぞれ計算する
- ①A 木が B 木に子木として合併されるとき：
-
- A 木のすべてのノードは追加で 1 回探索する必要がある
-
- ②B 木が A 木に子木として合併されるとき：
-
- B 木のすべてのノードは追加で 1 回探索する必要がある
-
- ①A 木が B 木に子木として合併されるとき：
- ❗【2 つの方法の平均探索回数を比較】
- 木の高さ [LA、LB] とは直接関係がなく、分子のノード数 [SA、SB] が【直接】探索回数を決定し、回数が少ないほど良い
- 👉ノード数が少ない方が子木として合併される
- ❓考える：上記の導出は高さが合併基準にならないことを証明しているのか？
- ❌否、高さは間接的にノード数に影響を与え、一般的に高さが低いほどノード数が少ない
- しかし、特殊な場合において、A 木が B 木よりも高く、A 木のノード数が B 木よりも少ない場合は、依然として【ノード数】を合併基準として、A 木を B 木に子木として合併する
- SA、SB 個のノードを持つ A、B 木に対して、それらの総探索回数 LA、LB はそれぞれ：
- したがって、ノード数を合併基準とする方が優れている！👇合併の考え方は以下の通り
- 【例】平均探索回数とは何か
- 2 つの子木を合併する際
- ノード数が同じであれば、通常の Quick-Union の考え方に従って交換する
- 異なる場合、ノード数が少ない子木の根ノードを👉ノード数が多い子木の根ノードの下に接続する
- [PS] 言い換えれば
- 大兄を交換する際
- 小弟の数が同じであれば、通常の Quick-Union の考え方に従って交換する
- 異なる場合、小弟が少ない大兄は👉小弟が多い大兄と混ざる必要がある
+ パス圧縮#
- 随堂練習 2 の weighted Quick-Union の可視化結果を参照
-
- 0 の位置は少し気まずい
- ❗ 0 の代表要素が 1 であろうと 3 であろうと違いはなく、0 を直接 3 の下に接続することで木の高さを減少させることができる
- 【方法】すべての非根ノードを直接根ノードに指し示し、構造を平坦化する
-
上記のアルゴリズムの効率比較
随堂練習#
Quick-Find vs. Quick-Union#
-
-
【重要】Quick-Union を理解する
- 0->1->2->4->5、3->4->5；8->9->7->6
- 探索、合併の境界：自分の代表要素が自分自身であるとき、停止する
Quick-Union vs. weighted Quick-Union#
-
-
【重要】weighted の意味を理解する
- 2 つの集合の要素数が異なる場合
- 要素数が少ない集合の代表要素の値👉要素数が多い集合の代表要素の値
- 小弟が少ない大兄は小弟が多い大兄に従う必要がある
-
結果の可視化
-
- 明らかに、weighted 方法で得られた木はより低く、合併、探索の効率が高い
-
コードデモ#
HZOJ-71：友達の輪#
サンプル入力
6 5
1 1 2
2 1 3
1 2 4
1 4 3
2 1 3
サンプル出力
No
Yes
- 考え
- データ構造を使用 —— 併合集合
- 1 は合併操作、2 は探索操作
- Quick-Find、Quick-Union [+weighted、+ パス圧縮、-weighted] のアルゴリズム効率をそれぞれテストする
- コード
Quick-Find#
-
-
-
探索、合併戦略：染色に基づく
Quick-Union#
-
-
Quick-find に基づく
- 構造定義の color を代表要素 father に変更
- 探索操作を変更：底まで見つける必要がある
- 合併操作を変更：2 つの要素の底を見つけてから合併する必要がある
-
連結リストに退化する問題が発生しやすく、以下で最適化を行う
+ weighted#
-
-
Quick-Union に基づく
-
size 属性を追加し、ノードが属する集合のノード数を記録し、これを合併戦略として使用
+ パス圧縮#
-
-
毎回の探索でパス圧縮を行い、【探索要素】から【根代表要素】の区間にあるすべての要素を根代表要素 [根ノード] に指し示す
－weighted#
-
- size に関連するすべての操作を削除
- パス圧縮があれば、ランクに従わない合併 [size 属性を削除] でも良好な効果が得られる
HZOJ プラットフォーム上の問題テスト用時
| 方法 | Quick-Find | Quick-Union | +weighted | + パス圧縮 | weighted |
|---|---|---|---|---|---|
| 用時 (ms) | 744 | 2020 | 164 | 172 | 188 |
- Quick-Union は退化問題が発生した
- パス圧縮を加えた後、ランクに従わない合併でも良好な効果が得られる
- 🆒残りの 3 つの方法はすべて良好な効果を持っている！
考察点#
- weighted Quick-Union アルゴリズム部分で、ノード数が優れている導出は高さが合併基準にならないことを証明しているのか？
- ❌否、高さは間接的にノード数に影響を与え、一般的に高さが低いほどノード数が少ない
- しかし、特殊な場合において、A 木が B 木よりも高く、A 木のノード数が B 木よりも少ない場合
- 【ノード数】を合併基準として❗ A 木を B 木に子木として合併する必要がある
ヒント#
- 《C++ Primer》を参考書として使用することをお勧めします
-
