スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

最小全域木の特集

Competitive Programming Advent Calendar Div2012 の 17 日目の記事です。

はじめに

最小全域木を求めるアルゴリズムをいくつか紹介します。
第 2~4 節は蟻本[1]の初級編程度の知識があれば読めます。第 5 節は少し難しいです。

目次

  1. 問題定義
  2. プリム法 (Prim's algorithm)
  3. クラスカル法 (Kruskal's algorithm)
  4. ブルーフカ法 (Borůvka's algorithm)
  5. round robin algorithm
  6. 余談

1. 問題定義

この記事では、辺に実数の重みがついた無向グラフ $G=(V, E)$ を考えます。
$V$ は頂点の集合、$E$ は辺の集合です。
辺 $e$ の重みを $cost(e)$ と書くことにします。

$G$ の全域木 $T=(V, E')$ に対して、
$$T \ \text{の重み} := \sum_{e \in E'} cost(e)$$と定めます。

以下では、与えられた $G$ に対して、$G$ の重み最小の全域木 ( minimum spanning tree:以下 MST ) を求める問題を考えます。$G$ が連結でないときには明らかに $G$ は全域木を持たないので、$G$ が連結であることを仮定します。また、$G$ によっては MST が複数存在することがありえますが、どれか一つを求められればよいことにします。

2. プリム法 (Prim's algorithm)

プリム法は、Jarník (1930)・Prim (1957)・Dijkstra (1959) によって、それぞれ独立に発見されました。

これは、始点を一つ固定して、そこから広がるように全域木を求めるアルゴリズムです。
擬似コードを示します。
u0 ∈ V を一つ選んで固定 // 始点
H := {u0} // 訪問済みの頂点を入れる集合
M := φ // 求めたい MST の辺集合
while H≠V // すべての頂点を訪れるまでくり返す
u ∈ H かつ v ∈ V-H となるような辺 {u,v} ∈ E のうち
重み最小のものを e={u,v} とする
M := M ∪ {e} // e を MST に加える
H := H ∪ {v} // v を訪問済みにする
end

全域木は $|V|-1$ 本の辺を持つので while ループはちょうど $|V|-1$ 回実行されます。

このアルゴリズムの計算量は $e$ を選ぶ部分の実装によって変わります。

$e$ を求めるのに素直に $|V|$ 回のループを回すと、計算量は $O(V^2)$ になります。
$G$ が密のときは、これが計算量的な意味で最良です。
※ しつこいので、$O(|V|)$ のことを単に $O(V)$ などと書いています。

ヒープと呼ばれるデータ構造を使えば、もっと高速に処理することができます。ヒープにも色々種類がありますが、たとえば最も有名な二分ヒープ ( C++ の std::priority_queue はこれ ) を使えば、計算量は $O(E \log V)$ になります。

実装例:prim.cpp
( FC2 ブログの仕様でアップロードできるファイル名が制限されているので変な名前になっていますが、C++ のソースコードです。)
擬似コードのままだと実装しにくいので、最短経路を求めるダイクストラのアルゴリズムと似た感じで実装されることが多いようです。

3. クラスカル法 (Kruskal's algorithm)

クラスカル法は Kruskal (1956) によって発見されました。

これは、辺がない状態 ( $|V|$ 個の孤立点からなる森 ) から始めて、辺を追加していくことで木と木をつなげて大きくしていくアルゴリズムです。

擬似コードを示します。
F := E
M := φ // MST の辺集合
while |M|<|V|-1 // MST ができるまでくり返す
F に含まれる重み最小の辺を e={u,v} とする
F := F - {e} // F から e を取り除く
if M において u と v が異なる木に属する
then M := M ∪ {e} // e を MST に追加する
end

擬似コードを見ると、
・ 6 行目:二つの頂点が異なる木に属するかを判定
・ 7 行目:二つの頂点の間に辺を張る ( 二つの木をくっつける )
という二つの特別な処理が必要なことがわかります。
この処理を高速に行うために、Union-Find と呼ばれるデータ構造を用いることができます。

また、$F$ は軽い辺から順に取り出していくだけなので、最初にソートしておいて前から順番に参照するように書き換えても同じことです。

この二点を反映させた、より実装レベルに近い擬似コードは次のようになります。
E の辺を重みの小さい順にソートしたものを e1, e2, ..., e|E| とおく
M := φ // MST の辺集合
for i=1 to |E|
ei = {u,v} とする
F := F - {ei} // F から ei を取り除く
if find(u) ≠ find(v) // u と v が異なる木に属すなら
then union(u,v) // u と v をつなげる
M := M ∪ {ei} // ei を MST に追加する
end

計算量は
・ 最初のソートが $O(E \log V)$
・ for ループの内側が $O(\alpha(E,V))$
かかるので、合計で $O(E \log V + E\alpha(E,V)) = O(E \log V)$ になります。
ここで、$\alpha(m,n)$ は逆アッカーマン関数と呼ばれているとても緩やかに増加する関数です。定義は Wikipedia を見てください。

クラスカル法の計算量は二分ヒープを使ったプリム法と同じですが、いくつかの場合にはプリム法より有利です。たとえば、
・ ソートが高速にできる場合。辺の重みが小さい整数で radix sort が使える場合など
・ E の部分集合について何回も MST を求める場合。$E$ を一回だけソートしておけばいい
などが考えられます。

実装例:kruskal.cpp

4. ブルーフカ法 (Borůvka's algorithm)

ブルーフカ法は、Borůvka (1926)・Choquet (1938)・Łukasiewicz et al. (1951)・Sollin (1965) によって、それぞれ独立に発見されました。

プリム法では一点を決めてそこから木を拡大していきましたが、これをすべての点から始めるのがブルーフカ法です。

擬似コードを示します。
M := φ // MST
while |M|<|V|-1
F := φ // M に追加する辺の集合
foreach C in ( M の連結成分全体 )
u ∈ C かつ v ∈ V-C となるような辺 {u,v} ∈ E のうち
重み最小のものを e とする
F := F ∪ {e} // F に e を追加する
end
M := M ∪ F // M に F を追加する
end

$F$ に同じ辺が二回追加されることがありますが、そのときは単に一回だけ追加されたものとして扱います。

while ループ一回につき $M$ の連結成分の個数が半分以下に減ることに注目すれば、while ループは高々 $O(\log V)$ 回しか実行されず、ブルーフカ法の計算量は $O(E \log V)$ となることがわかります。

実装例:boruvka.cpp
この実装では、$F$ に 2 回含まれる辺に対処するために Union-Find を使いました。クリティカルな部分ではないので、計算量は上に書いたものと同じです。

5. round robin algorithm

上記 3 つのアルゴリズムを眺めてみると、どれも次の"貪欲法"の特別な場合であることに気づきます。
M := φ // MST
while |M|<|E|-1 // MST ができるまでくり返す
M の連結成分(木)を一つ以上選び C1, C2, ..., Ck とする.
for i=1 to k
u ∈ Ci かつ v ∈ V-Ci となるような辺 {u,v} ∈ E のうち
重み最小のものを e とする
M := M ∪ {e}
end
end

違いが出るのは 3 行目で、アルゴリズムによって $C_1, C_2, \ldots, C_k$ の選び方が異なります。
プリム法では $k = 1$ として、$C_1$ として始点 $u_0$ を含む木を選んでいます。
クラスカル法では $k = 1$ として、辺のコストを基準にして $C_1$ を選んでいます。
ブルーフカ法では $k = ( M \ \text{の連結成分の個数} )$ として、すべての木を選んでいます。

この節で紹介する round robin algorithm も、この"貪欲法"で $k = 1$ とした特殊なケースに相当します。
上記 3 つとの違いは $C_1$ をより賢く選ぶという点です。

round robin algorithm は Cheriton and Tarjan (1976) によって発見されました。
round robin という名前は [2] でそう呼ばれていたのでそれを真似しただけで、一般的ではないかもしれません。

擬似コードを示します。
M := φ // MST
h := φ // 2V から 2E への map
Q := φ // 頂点集合の列

/* h, Q を初期化 */
for v in V
Q := (Q, {v}) // Q の末尾に {v} を追加
h(v) := { {u,w} ∈ E | u = v } // v から出る辺の全体
end

/* 本処理 */
while |Q|>1
u ∈ h(Q[1]) かつ v ∈ V-h(Q[1]) となるような {u,v} ∈ E のうち
重み最小のものを e={u,v} とする // Q[1] は Q の先頭の意味
M := M ∪ {e}
j, k を u ∈ Q[j], v ∈ Q[k] となるよう定める
h(Q[j] ∪ Q[k]) := update(h(Q[j]),h(Q[k]))
Q := (Q, Q[j] ∪ Q[k]) // Q[j] ∪ Q[k] を Q の末尾に追加
Q := Q - {Q[j], Q[k]} // Q から Q[j] と Q[k] を削除
end

ここで、update は次のような関数。
update(F1, F2)
F := F1 ∪ F2
F から両端が M において同じ連結成分に属する辺を削除
return F

$Q$ は $V$ の分割になっていて、今どの頂点がつながっているかを表しています。ブルーフカ法ではこれを毎回計算しなおしていました。
$h$ は、$S \subset V$ に対して $h(S) = \{ \{u,v\} \in E \mid u \in S \ \ \text{かつ} \ v \in V\setminus S \}$ という辺集合を表しています。$C_1$ として $S$ を選んだとき、$h(S)$ の辺が $e$ の候補になります。

$Q$, $h$ としてどのようなデータ構造を選べばよいでしょうか。

まず、update 関数で同じ連結成分かどうかの判定が登場しているので、擬似コードには登場していませんが、頂点の連結情報を管理するために Union-Find を一つ用意しておきます。このあたりはクラスカル法と同じです。
すると、$Q$ には実際に頂点集合を入れる必要はなく、Union-Find の代表元を入れておけば十分であることに気づきます。$Q$ に必要とされる操作は
□ 先頭要素の参照
□ 末尾への追加
□ 任意の位置の要素の削除
です。擬似コード中の $j$, $k$ は $|V|$ 以下の小さい値なので、少し工夫すれば ( 逆写像みたいなものを持っておけば ) これはただの配列で実現できます。

一方、$h$ に必要とされる操作は
□ 最小値の取得
□ update
です。この操作を実現するのに、Cheriton and Tarjan は delete と meld を遅延評価した leftist heap を使いました。
delete の遅延評価は、すぐにそのノードを消すのではなくヒープ内に残しておいて、あとで findmin などで参照されたときに本当に削除する、というもの。
meld の遅延評価は、ダミーの根ノードを作ってその左右の子に meld したい heap をくっつける。ダミーの根は delete と同様、参照されたときに本当に処理する、というもの。

この手法を使えば、update は $O(1)$ で、findmin は $O\left(k \log\left(\frac{m}{k+1}\right)\right)$ で実施できることが知られています。
ここで、$m$ は leftist heap のノード数、$k$ は findmin の過程で削除されるノード数。

round robin algorithm の計算量を調べてみましょう。厳密にやるためには leftist heap の中身に踏み込まないといけないので、ここでは簡単にやるだけにとどめます。

○初期化について
$Q$ の初期化は、自明に $O(V)$ でできます。
$h$ の初期化は、( 自明ではないですが ) よく知られているように $O(E)$ でできます。

○本処理について
while ループ一回につき $Q$ の長さが $1$ 減るので、while ループは $|V|-1$ 回実行されることがわかります。
while ループの内部では、毎回、leftist heap の findmin が $1$ 回、update が $1$ 回、Union-Find の union が $1$ 回呼ばれます。
find については、削除すべきノードかどうかの判定をするために findmin の中で何度も呼ばれるので簡単にはわかりません。
update と union は $O(1)$ なので、あとは findmin にかかる時間 ( つまり find が呼ばれる回数 ) を評価すればよいことになります。

$i$ 回目の while ループにおいて、$h(Q[1])$ のノード数を $m_i$、findmin で削除されるノード数を $k_i$ とおきます。また $n = |V|$、$m = |E|$ とおきます。知りたいのは$$S := O\left(\sum_{i=1}^{n-1} k_i \log\left(\frac{m_i}{k_i+1}\right)\right)$$の評価です。$k_i$ の大小によって和を small part と large part に分けます。

◎ small part
すべての $i$ で $k_i \le m_i/(\log^2 n) - 1$ とします。このとき
$$\begin{align*}S &= O\left(\sum_i \frac{m_i}{\log^2 n} \log m_i\right)\\
&= O\left(\sum_i \frac{m_i}{\log n}\right)\\
&= O(m)\end{align*}$$となります。2 番目の等号で
$$\log m_i \le \log m \le \log(n^2) \le 2 \log n$$を使いました。また、最後の等号では
$$\sum_i m_i \le 2m \log n \tag{☆}$$となることを使いました。この不等式は比較的簡単な推論で示せますがここでは省略します。

◎ large part
すべての $i$ で $k_i \ge m_i/(\log^2 n) - 1$ とします。このとき
$$\begin{align*}S &= O\left(\sum_i k_i \log(\log^2 n)\right)\\
&= O\left(\sum_i k_i \log \log n\right)\\
&= O(m \log \log n)\end{align*}$$となります。最後の等号で $\sum_i k_i \le 2m$ を使いました。

以上で、while ループ全体を通して find が呼ばれる回数は
$$O(m + m \log \log n) = O(m \log \log n)$$で抑えられることがわかりました。

要素数 $N$ の Union-Find で $M$ 回の操作をしたときの計算量は $O(M\alpha(M, N))$ なので、全体の計算量は
$$O((m \log \log n) \alpha(m \log \log n, n))$$となります。さらに、逆アッカーマン関数の魔法「$M/N$ が増加すると $\alpha(M, N)$ は減少する」という性質を使えば、
$$O((m \log \log n) \alpha(m \log \log n, n)) = O(m \log \log n)$$が言えます。

以上より、round robin algorithm の計算量は $O(E \log \log V)$ であることがわかりました。やった!

「辺を追加して大きくなった木をリスト $Q$ の末尾に追加した」というのが重要なポイントなんじゃないかと思います。というのも、こうすることで各 while ループにおいて小さい木 $Q[1]$ が取り出されやすくなるからです。このことは ( 説明を省略してしまいましたが ) 不等式 (☆) に現れています。

実装もしてみたかったんですが時間切れでした。あとで普通のブログ記事として補完します。

6. 余談

参考にした本 [2] が古かったので、全体的に古めの内容になっています。
最小全域木問題の現在の最速は 2000 年に Chazelle が出した $O(E \alpha(E,V))$ とからしいです。soft heap というヒープを使うらしいんですが、詳しくは知りません。

参考文献

[1] プログラミングコンテストチャレンジブック
[2] Data Structures and Network Algorithms

記事のかなりの部分で [2] を参考にしました。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。