最小全域木のための並列アルゴリズム

グラフ理論における最小全域木（MST）${\displaystyle T}$グラフの${\displaystyle G=(V,E)}$と${\displaystyle |V|=n}$そして${\displaystyle |E|=m}$は、​​${\displaystyle G}$それはすべての頂点を含み、かつ最小の重みを持つ。

最小全域木（MST）は、実用的および理論的な幅広い分野で活用されている、有用かつ汎用性の高いツールです。例えば、単一の倉庫から複数の店舗に特定の商品を供給しようとする企業は、倉庫を起点とするMSTを用いて、各店舗への最短経路を計算することができます。この場合、店舗と倉庫は頂点として、それらの間の道路接続は辺として表されます。各辺には、対応する道路接続の長さがラベル付けされます。

もし${\displaystyle G}$エッジ重みなしの場合、すべての全域木は同じ数のエッジを持ち、したがって同じ重みを持ちます。エッジ重み付きの場合、すべての全域木の中でエッジの重みの合計が最も小さい全域木が、${\displaystyle G}$これは最小全域木（MST）と呼ばれます。必ずしも一意であるとは限りません。より一般的には、必ずしも連結ではないグラフには最小全域森が存在し、これは各連結成分のMSTの和集合で構成されます。

MST の探索はグラフ理論において広く行われている問題であるため、それを解くための逐次アルゴリズムが数多く存在する。その中には、プリムのアルゴリズム、クラスカルのアルゴリズム、ボルフカのアルゴリズムなどがあり、それぞれ MST の異なる特性を利用している。これらはすべて同様の方法で動作する。${\displaystyle E}$有効な MST が見つかるまで反復的に拡張されます。しかし、実際の問題はしばしば非常に大規模であるため (道路ネットワークには数十億のエッジがある場合もあります)、パフォーマンスが重要な要素となります。これを改善するオプションの 1 つは、既知のMST アルゴリズムを並列化することです。^{[ 1 ]}

このアルゴリズムは、最小全域木（MST）のカット特性を利用します。以下に、簡略化された高レベルの擬似コードによる実装例を示します。

${\displaystyle T\gets \emptyset }$${\displaystyle S\gets \{s\}}$どこ${\displaystyle s}$はランダムな頂点です${\displaystyle V}$繰り返す${\displaystyle |V|-1}$タイムズ 最も軽いエッジを見つける${\displaystyle (u,v)}$st${\displaystyle u\in S}$しかし${\displaystyle v\in (V\setminus S)}$${\displaystyle S\gets S\cup \{v\}}$${\displaystyle T\gets T\cup \{(u,v)\}}$Tを返す

各辺は正確に 2 回観測されます。つまり、各端点を調べるときに観測されます。各頂点は正確に 1 回だけ観測され、合計で${\displaystyle O(n+m)}$各ループ反復における最軽量エッジの選択以外の操作。この選択は、優先度付きキュー（PQ）を使用して実行されることが多い。各エッジに対して、最大で 1 つの decreaseKey 操作（償却済み）${\displaystyle O(1)}$）が実行され、各ループ反復で 1 つの deleteMin 操作が実行されます（${\displaystyle O(\log n)}$したがって、フィボナッチヒープを使用すると、プリムのアルゴリズムの総実行時間は漸近的に${\displaystyle O(m+n\log n)}$。

ループは本質的に逐次的であり、適切に並列化できないことに注意することが重要です。これは、1 つのエンドポイントを持つ最も軽いエッジが${\displaystyle S}$そしてさらに${\displaystyle V\setminus S}$エッジの追加により変化する可能性があります${\displaystyle T}$したがって、最も軽いエッジの選択を2つ同時に行うことはできません。ただし、並列化を試みる試みはいくつか存在します。

考えられるアイデアの一つは、${\displaystyle O(n)}$PQアクセスをサポートするプロセッサ${\displaystyle O(1)}$EREW-PRAMマシンでは、^{[ 2 ]}合計実行時間を短縮して${\displaystyle O(n+m)}$。

クルスカルの最小全域木アルゴリズムは、最小全域木のサイクル特性を利用します。以下に、その概要を示す擬似コードを示します。

${\displaystyle T\gets }$各頂点がそれぞれ独自のサブツリーを持つ森 foreach${\displaystyle (u,v)\in E}$重量の昇順 で${\displaystyle u}$そして${\displaystyle v}$異なるサブツリーで${\displaystyle T}$${\displaystyle T\gets T\cup \{(u,v)\}}$Tを返す

サブツリー${\displaystyle T}$はunion-findデータ構造に格納されるため、償却されたデータ構造では 2 つの頂点が同じサブツリーにあるかどうかをチェックすることが可能です。${\displaystyle O(\alpha (m,n))}$どこ${\displaystyle \alpha (m,n)}$は逆アッカーマン関数です。したがって、アルゴリズムの総実行時間は です。${\displaystyle O(sort(n)+\alpha (n))}$。 ここ${\displaystyle \alpha (n)}$これは、単一値の逆アッカーマン関数を表し、現実的な入力値に対しては5未満の整数値が得られます。

filterKruskal(${\displaystyle G}$）： もし${\displaystyle m<}$KruskalThreshold: return kruskal(${\displaystyle G}$） pivot = chooseRandom(${\displaystyle E}$） ${\displaystyle (E_{\leq }}$、${\displaystyle E_{>})\gets }$パーティション（${\displaystyle E}$、ピボット） ${\displaystyle A\gets }$filterKruskal(${\displaystyle E_{\leq }}$） ${\displaystyle E_{>}\gets }$フィルター（${\displaystyle E_{>}}$） ${\displaystyle A\gets A}$${\displaystyle \cup }$filterKruskal(${\displaystyle E_{>}}$） 戻る${\displaystyle A}$ パーティション（${\displaystyle E}$、ピボット): ${\displaystyle E_{\leq }\gets \emptyset }$${\displaystyle E_{>}\gets \emptyset }$foreach${\displaystyle (u,v)\in E}$: 重量(${\displaystyle u,v}$）${\displaystyle \leq }$ピボット： ${\displaystyle E_{\leq }\gets E_{\leq }\cup {(u,v)}}$それ以外${\displaystyle E_{>}\gets E_{>}\cup {(u,v)}}$戻る（${\displaystyle E_{\leq }}$、${\displaystyle E_{>}}$） フィルター（${\displaystyle E}$): ${\displaystyle E_{filtered}\gets \emptyset }$foreach${\displaystyle (u,v)\in E}$: find-set(u)の場合${\displaystyle \neq }$find-set(v): ${\displaystyle E_{filtered}\gets E_{filtered}\cup {(u,v)}}$戻る${\displaystyle E_{filtered}}$

ボルフカのアルゴリズムの基本的な考え方は、エッジの収縮です。${\displaystyle \{u,v\}}$まず削除することで契約が成立する${\displaystyle v}$グラフから各エッジをリダイレクトする${\displaystyle \{w,v\}\in E}$に${\displaystyle \{w,u\}}$これらの新しいエッジは、以前のエッジの重みを保持します。MSTの重みだけでなく、それがどのエッジで構成されているかも決定することが目的である場合、エッジが縮約された頂点のペアを特定する必要があります。高レベルの擬似コード表現は次のとおりです。

${\displaystyle T\gets \emptyset }$その間${\displaystyle |V|>1}$${\displaystyle S\gets \emptyset }$のために${\displaystyle v\in V}$${\displaystyle S\gets S}$${\displaystyle \cup }$最も軽い${\displaystyle \{u,v\}\in E}$のために${\displaystyle \{u,v\}\in S}$ 契約${\displaystyle \{u,v\}}$${\displaystyle T\gets T\cup S}$Tを返す

収縮によって、2 つの頂点間に複数のエッジが生じる可能性があります。最も軽いエッジを選択する直感的な方法は、${\displaystyle O(m)}$しかし、頂点を共有するすべての縮約を並列に実行すれば、これは可能です。再帰は、頂点が1つだけ残ったときに停止します。つまり、アルゴリズムは最大で${\displaystyle \log n}$反復処理により、合計実行時間は${\displaystyle O(m\log n)}$。

その間${\displaystyle |V|>1}$ 最も軽い入射エッジを見つける //${\displaystyle O({\frac {m}{p}}+\log n+\log p)}$ 各頂点に、対応するサブグラフを割り当てる //${\displaystyle O({\frac {n}{p}}+\log n)}$ 各サブグラフを収縮させる //${\displaystyle O({\frac {m}{p}}+\log n)}$

${\displaystyle v\gets }$探す（${\displaystyle {\frac {im}{p}}}$、${\displaystyle \Gamma }$） のために${\displaystyle e\gets {\frac {im}{p}};e<{\frac {(i+1)m}{p}}-1;e++}$もし${\displaystyle \Gamma [v+1]=e}$${\displaystyle v++}$もし${\displaystyle c[e]<c[pred[v]]}$${\displaystyle pred[v]\gets e}$

並列処理${\displaystyle v\in V}$${\displaystyle w\gets pred[v]}$もし${\displaystyle pred[w]=v\land v<w}$${\displaystyle pred[v]\gets v}$

その間${\displaystyle \exists v\in V:pred[v]\neq pred[pred[v]]}$すべての人へ${\displaystyle v\in V}$${\displaystyle pred[v]\gets pred[pred[v]]}$

${\displaystyle k\gets }$サブグラフの数 ${\displaystyle V'\gets \{0,\dots ,k-1\}}$ 全単射関数を見つける${\displaystyle f:}$スタールート${\displaystyle \rightarrow \{0,\dots ,k-1\}}$${\displaystyle E'\gets \{(f(pred[v]),f(pred[w]),c,e_{old}):(v,w)\in E\land pred[v]\neq pred[w]\}}$

MST を見つける問題を扱う並列アルゴリズムは他にも複数あります。線形数のプロセッサを使用すれば、これを次のように実現できます。${\displaystyle O(\log n)}$[ ^{8 ] [ 9 ] BaderとCongは、}最適な逐次アルゴリズムよりも8コアで5倍速いMSTアルゴリズムを発表した。^{[ 10 ]}

もう一つの課題は外部メモリモデルです。Dementievらによって提案されたアルゴリズムは、内部メモリのみを使用するアルゴリズムよりも2～5倍遅いだけだとされています^{[ 11 ]。}