Bo2SS

コース内容#

• 並列集合：合併集合 [連結関係を構築]、探索集合内の連結関係 [2 つの点が連結しているかを判断]

連結性問題#

• 

• ルール：すでに連結関係を持つ点は再接続できない

• すべての点を 2 つの集合に分けた：①、②

• [PS] 点と点の関係（合併、連結判断）→集合と集合の関係でもある

Quick-Find アルゴリズム#

• 中核思想：染色
  • 1 つの色は 1 つのカテゴリに対応
  • 初期化：個体は独立しており、自分のインデックスを書き込み、独立した集合に属する
  • ⭐自分と連結しているすべての点の色を染める色に変更
• 時間計算量
  • 連結判断：O (1)—— 探索が速いため Quick-Find と呼ばれる
  • 合併操作：O (N)—— すべての点を遍歴して合併するかを決定する必要がある
• 🆒考えを引き起こす：なぜ森林と呼ばれるのか？
  • 重要なのは合併操作であり、いくつかの点といくつかの点の合併、集合と集合の合併
  • 子木と子木の間の合併、または 1 つの木を別の木の子木として扱うことに似ている
  • すべての集合を一緒に置くと、すべての木を一緒に置くことになり、森林となる
• では、染色以外に他の方法はあるのか？
  • 考察：何色に染めたかは重要ではなく、どの点の色が同じか、つまり連結しているかを知るだけでよい

Quick-Union アルゴリズム#

• 生活のヒント：兄貴を探す、リーダーを探す
• 中核思想：代表要素を探す [根ノード]
  • 保存されている値はその代表要素
  • 初期化：個体は独立しており、自分のインデックスを書き込み、独立した集合に属する
  • ⭐2 つの点の代表要素を見つけて、1 つの代表要素の値をもう 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【ノード数】の方が優れている
• ⭐なぜ合併の基準 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 回多く探索する必要がある
    • ❗【2 つの方法の平均探索回数を比較】
      • 木の高さ [LA、LB] とは直接関係がなく、分子のノード数 [SA、SB] が【直接】探索回数を決定し、回数が少ないほど良い
      • 👉ノード数が少ない方が子木として合併される
      • ❓考察：上記の導出は高さが合併の基準にならないことを証明しているのか？
        • ❌否、高さは間接的にノード数に影響を与え、一般的には高さが低いほどノード数が少ない
        • しかし、特殊な場合において、A 木が B 木よりも高く、A 木のノード数が B 木よりも少ない場合は、【ノード数】を合併の基準として、A 木を子木として B 木に合併する
  • したがって、ノード数を合併の基準とする方が優れている！👇合併の考え方は以下の通り
• 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 に関連するすべての操作を削除
• パス圧縮があれば、ランクに基づく合併 [サイズ属性を削除] でも良好な効果を得ることができる

HZOJ プラットフォーム上の問題テスト用時

• Quick-Union は退化問題が発生した
• パス圧縮を加えた後、ランクに基づく合併を行わなくても良好な効果が得られる
• 🆒残りの 3 つの方法はすべて良好な効果を持っている！

考察点#

• weighted Quick-Union アルゴリズム部分で、ノード数が優れている導出は高さが合併の基準にならないことを証明しているのか？
  • ❌否、高さは間接的にノード数に影響を与え、一般的には高さが低いほどノード数が少ない
  • しかし、特殊な場合において、A 木が B 木よりも高く、A 木のノード数が B 木よりも少ない場合
    • 【ノード数】を合併の基準として❗ A 木を子木として B 木に合併する必要がある

ヒント#

• 《C++ Primer》は参考書として使用することをお勧めします
• 

コース速記#