すずめでも分かる「UnionFind」
こんにちは、まゆです。
今回は、UnionFindについて解説していきたいと思います。
UnionFindとは？
UnionFindは簡単に言うと、集合を管理するアルゴリズムです。
作りたい命令は、主に2つあります。
| 命令 | 戻り値 | 内容 |
|---|---|---|
| unite(a,b) | なし | aとbが同じ集合に属することを示す |
| same(a,b) | bool型 | aとbが同じ集合に属するかをチェックする |
これだけだとわかりにくいので、例を見てみましょう。
unite命令を実行する前の状態ではsame(2,3)の戻り値はfalseですが、unite(6,9)を行った後ではsame(2,3)の戻り値がtrueに変化していますね！
以上がUnionFindの主要な機能です。
木構造にする前段階
同じ集合に属することを示すには、以下のような方法を使います。
まず配列 id[N] を用意します。idにはそれぞれの番号を格納しておきます。
unite(a,b)を実行したら、id[a]と同じ数を格納している配列を全てid[b]に書き換えるようにします。
例えば、unite(1,4)を実行すると、配列1の要素がid[4]の4で書き換えられます。
次に、unite(4,5)を実行すると、配列4(4)と同じ値を持っている1が、id[5]の5で書き換えられます。
このアルゴリズムを使えば、等しい値をもつ配列を探すことで同じ集合に属するものを簡単に見つけることができます。
では実装してみましょう。
struct UnionFind { vector<int> id; UnionFind(int n) : id(n) { for (int i = 0; i < n; i++) id[i] = i; } void unite(int p, int q) { int x = id[p]; int y = id[q]; for (int i = 0; i < id.size(); i++) { if (id[i] == x) id[i] = y; } } bool same(int p, int q) { return id[p] == id[q]; } };
このようになります。
このコードをみてみると、unite関数の中にfor文があり、効率の悪いアルゴリズムだということが分かると思います。
| 初期化 | unite | same |
|---|---|---|
| N | N | 1 |
1回実行するごとにこれだけかかるので、全体ではO(N2)ですね。これからこのコードを改善していきたいと思います。
木構造にする
先ほど問題だったのはunite部分です。
効率良く繋ぐことができるようにするにはどうすればいいでしょうか？
QuickUnionでは木構造の集合である、森構造(？)を用います。
はじめに用意するのは先ほどと同じサイズで同じ値が格納されている配列です。
それから、いくつかの命令を実行していきます。
配列の値はそれぞれの親を指すようにします。
この状態で、union(7,3)を実行します。
木構造にすると、このように根を探して、根の一方を書き換えれば2つの木を繋げることができます。
それでは実装していきます。
struct UnionFind { vector<int> id; UnionFind(int n) : id(n) { for (int i = 0; i < n; i++) id[i] = i; } int root(int i) { while (i != id[i]) i = id[i]; // i==idになったとき根である return i; } void unite(int p, int q) { int i = root(p); int j = root(q); id[i] = j; } bool same(int p, int q) { return root(p)== root(q); } };
root関数では、根に辿り着くまで（idが自分自身を指すまで）繰り返しid[id[id[id[i....]]]]のようにノードを辿っています。
これは、先ほどと比べて一見効率の良いアルゴリズムに見えますね。 しかし最悪のケースでは、root関数部分でO(N)かかってしまいます。
0-1-2-3-4-5-6-7-8-9のような、根にたどり着くまでにNかかる木が出来上がってしまう可能性があるからです。
ここから、このような最悪なケースを回避するようなアルゴリズムに改良しようと思います。
マージテク
それでは問題です。軽い木に重い木を繋げる場合と、重い木に軽い木を繋げる場合では、どちらが深さが浅くなるでしょうか？
上図からも分かるとおり「重い木に軽い木を繋げる」方が、深さが浅くなります。
これを実装するのは、そんなに難しくありません。
木のサイズを表す配列を別に用意してあげて、サイズが大きい方に小さい方を繋げる、という風にif文で書いてあげれば良いだけです。
実装してみると、以下のようになります。
struct UnionFind { vector<int> id; vector<int> s; UnionFind(int n) : id(n), s(n) { for (int i = 0; i < n; i++) { id[i] = i; s[i] = 1; } } int root(int i) { while (i != id[i]) i = id[i]; return i; } void unite(int p, int q) { if (p == q) return; if (s[p] < s[q]) { id[p] = q; s[p] += s[q]; } else { id[p] = q; s[p] += s[q]; } } bool same(int p, int q) { return root(p) == root(q); } };
このように重み付きにすることで、木の深さが高々底が2のlogNに収まります。このことを簡単に証明をします。
木１と木２を繋げるとします。
木２が木１に結合される場合は、（マージテクの性質より）木２が木１と同じサイズかそれ以上でした。
ということは、結合された後の木のサイズは少なくとも2倍以上になります。
ノードの数は全部でN個なのでlogN乗までしか繰り返せませんね。
つまり木の深さが増える回数はlogN回以下で、深さはlogNに収まることが証明されました！
経路圧縮
ここから更に経路圧縮の工夫をしていきたいと思います。
経路圧縮は根まで辿るついでに木を平坦にしていこう、というものです。
この部分は実は一行で済みます。
struct UnionFind { vector<int> id; vector<int> s; UnionFind(int n) : id(n), s(n) { for (int i = 0; i < n; i++) { id[i] = i; s[i] = 1; } } int root(int i) { while (i != id[i]) { id[i] = root(id[i]); //<--new i = id[i]; } return i; } void unite(int p, int q) { if (p == q) return; if (s[p] < s[q]) { id[p] = q; s[p] += s[q]; } else { id[p] = q; s[p] += s[q]; } } bool same(int p, int q) { return id[p] == id[q]; } };
通った部分が全て根に繋がり平坦な木を作ることができます。
余談ですが、付け足した部分についてid[i]=id[id[i]]と書いている解説もありました。
どちらの方が効率が良いんでしょうか？私には良くわかりません...
おわりに
はじめタイトルを「重み付きUnionFind」としていたのですが、私が理解したと思っていたものは普通のUnionFindだったようです。（この間違いは、英語のUnionFindの解説を聞いていたところ、weightedと書いてあったので「重み付きUnionFindって聞いたことあるけどこれか〜！」と私が勘違いしたところから起こりました。）
悔しいのできちんと重み付きUnionFindも理解しようと思ったら、アーベル群の単位元という言葉が出てきて、数学ができない私は「？？？」となったので諦めました（笑）
はてなブログでProcessingを動かす
Processingがブログ上で動いたらいいな〜と思って調べていたら、
<script src="https://cdnjs.cloudflare.com/ajax/libs/processing.js/1.6.6/processing.min.js"></script> <div style="text-align:center"> <script type="text/processing"> // ここにProcessingのコードを貼り付ける </script> <canvas></canvas> </div>
こうすると動くらしいということを知ったので、やってみます！！ (参考文献→Processing.jsをJavaScriptから使う - kitao's blog)
動いてますか？？(タップで再生)
感想
良くわかりませんが、importが出来なさそうです...(import java.util.Random;したら動かなくなった)
でもブログにそのまま貼り付けられるって楽しいですね！！
すずめでも分かる「bit全探索」
記憶喪失になってbit全探索を１から理解しないといけなくなったときのために、(自分用に)解説しておこうと思います。
bit全探索とは
部分集合を列挙するときに使えるアルゴリズムです。
つまり、こういうことができます。
実装はこんな感じ
for (int bit = 0; bit < (1 << n); ++bit) { for (int i = 0; i < n; ++i) { if (bit & (1 << i)) { //何か処理を書く } } }
これを見せられても、何をしているのか訳がわかりませんね。細かく見てみましょう。
for (int bit = 0; bit < (1 << n); ++bit) って何してるの？
ここで特にわからないのは、<<の部分だと思います。<<はシフト演算子と呼ばれています。シフト演算子は、数値の各ビットを左または右へシフトさせるための演算子です。<<だと左に、>>だと右にいきます。
各ビットをシフトするということは、下図のように遷移していくことを表します。
2進数の状態で遷移します！(10進数で35が350になったりしません！！！)
すずめ「1が1回左にシフトされるとどうなりますか？」
うさぎ「00001が00010になるので、10進数だと2になります。」
すずめ「では、2が1回左にシフトされるとどうなりますか？」
うさぎ「00010が00100になるので、4になります！」
ここまでで、シフトされる度に2倍になっていっているということが分かると思います。
ということは、for (int bit = 0; bit < (1 << n); ++bit) {の1<<nは、「1をn回左にシフトする」=「2のn乗」ですね！
if (bit & (1 << i)) の部分
ここでは何をしているのでしょうか。
&は、各ビットについて「両方のビットが1ならば1」という操作を適用する演算子です。for文によってn回シフトされるので、下図のように全ての桁のbitがたっているかどうかを調べることができます！
このビットを、その数値を取るか取らないかの2つの状態に当てはめることによって、全探索が行えます！具体的に言うと、C - Skill Upの問題で2冊の参考書が売っていたとするとき、「両方買わない」「１冊目を買う」「２冊目を買う」「１冊目と２冊目を買う」を、「00」「01」「10」「11」に当てはめて調べることができます。(ほら、全部で2のn乗の状態がありますね！)
実装しよう
C - Skill Upを解きます。
bit全探索を理解できると、やるだけですね！！
おしまい。
