プリム法
プリム法は、グラフ理論において、重み付き連結グラフの最小全域木を求めるための貪欲法アルゴリズムの一つです。最小全域木とは、グラフ内のすべての頂点を含み、かつ辺の重みの合計が最小となる木のことを指します。このアルゴリズムは、1930年に数学者のVojtěch Jarníkによって最初に発見され、その後、1957年に計算機科学者のロバート・C・プリムが独立に再発見しました。さらに1959年には、エドガー・ダイクストラが自身の論文の中でこのアルゴリズムについて言及したため、DJP法、Jarník法、Prim-Jarník法など、複数の名前で呼ばれることもあります。
プリム法の基本的な考え方は、一つの頂点から出発し、徐々に最小全域木を拡大していくというものです。具体的には、以下のステップを繰り返します。
1. グラフの任意の頂点を開始点として選択します。
2. 現在構築中の木に接続されている頂点と、まだ木に含まれていない頂点を結ぶ辺の中で、最も重みの小さい辺を選択します。
3. 選択された辺と、その辺によって結ばれる頂点を木に追加します。
4. 木がグラフ内のすべての頂点を含むまで、ステップ2と3を繰り返します。
このプロセスを繰り返すことで、最終的に最小全域木が構築されます。このアルゴリズムは、常に局所的な最適解を選択していくため、貪欲法に分類されます。
以下にプリム法の擬似コードを示します。
Vnew = {x} // xは任意の開始頂点
Enew = {} // 空の辺集合
while (Vnew ≠ V) // 全ての頂点がVnewに含まれるまで
(u, v) をEから選択。uはVnewに含まれる頂点、vはVnewに含まれない頂点。辺(u, v)は重みが最小
Vnewにvを追加
Enewに(u, v)を追加
プリム法の計算量は、グラフの表現方法と最小の辺を探索する方法によって異なります。
隣接行列を用いた場合: 各ステップで重み最小の辺を探索するためにすべての辺を調べる必要があるため、計算量はO(V^2)となります。ここで、Vは頂点の数を表します。
二分ヒープと隣接リストを用いた場合: 二分ヒープを使って最小の重みの辺を効率的に探索できるため、計算量はO((V+E)logV)となります。Eは辺の数を表します。
フィボナッチヒープを用いた場合: より高度なフィボナッチヒープを用いることで、計算量をO(E + VlogV)に改善できます。これは、辺の数が頂点数に対して十分に多い場合(E が Ω(VlogV) のオーダーである場合)に有効です。
プリム法によって得られる木が最小全域木であることの証明は、帰納法によって行うことができます。アルゴリズムの各ステップで、木に追加される辺は、常に現在の木とまだ木に含まれていない頂点を結ぶ最小の重みの辺です。この性質により、アルゴリズムが終了したときに得られる木は、最小全域木であることが保証されます。より具体的には、最小全域木であると仮定した木に対し、プリム法で得られた木が異なる辺を一つ含んでいた場合、その辺を取り除きプリム法で選ばれた辺を追加しても、必ず同じかより小さい重みの全域木となるため、矛盾が発生します。
最小全域木問題を解くアルゴリズムとしては、プリム法の他にクラスカル法やブルーフカ法などがあります。クラスカル法は、辺を重みの小さい順にソートし、閉路を形成しないように木に追加していく方法です。一方、ブルーフカ法は、複数の木を同時に成長させていく方法です。これらのアルゴリズムは、それぞれ異なる特徴を持っており、グラフの形状や規模によって使い分けることができます。
プリム法は、グラフ理論における基本的なアルゴリズムであり、最小全域木問題を効率的に解くことができます。その実装の容易さから、さまざまな分野で広く利用されています。ネットワーク設計やクラスタリングなど、現実世界の問題を解決するための強力なツールとして、今後も活用されていくでしょう。
V. Jarník: O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57-63.
R. C. Prim: Shortest connection networks and some generalisations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401
Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. In Numerische Mathematik, 1 (1959), S. 269 ～ 271.
D. Cherition and R. E. Tarjan: Finding minimum spanning trees. In: SIAM Journal of Computing, 5 (Dec. 1976), pp. 724–741
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.
最小木問題: プリムのアルゴリズム
クラスカル法とプリム法で迷路を生成して解く at cut-the-knot
プリム法のアニメーション
Prim's Algorithm Java アプレット
アルゴリズムの概要
プリム法の基本的な考え方は、一つの頂点から出発し、徐々に最小全域木を拡大していくというものです。具体的には、以下のステップを繰り返します。
1. グラフの任意の頂点を開始点として選択します。
2. 現在構築中の木に接続されている頂点と、まだ木に含まれていない頂点を結ぶ辺の中で、最も重みの小さい辺を選択します。
3. 選択された辺と、その辺によって結ばれる頂点を木に追加します。
4. 木がグラフ内のすべての頂点を含むまで、ステップ2と3を繰り返します。
このプロセスを繰り返すことで、最終的に最小全域木が構築されます。このアルゴリズムは、常に局所的な最適解を選択していくため、貪欲法に分類されます。
アルゴリズムの擬似コード
以下にプリム法の擬似コードを示します。
Vnew = {x} // xは任意の開始頂点
Enew = {} // 空の辺集合
while (Vnew ≠ V) // 全ての頂点がVnewに含まれるまで
(u, v) をEから選択。uはVnewに含まれる頂点、vはVnewに含まれない頂点。辺(u, v)は重みが最小
Vnewにvを追加
Enewに(u, v)を追加
計算量
プリム法の計算量は、グラフの表現方法と最小の辺を探索する方法によって異なります。
隣接行列を用いた場合: 各ステップで重み最小の辺を探索するためにすべての辺を調べる必要があるため、計算量はO(V^2)となります。ここで、Vは頂点の数を表します。
二分ヒープと隣接リストを用いた場合: 二分ヒープを使って最小の重みの辺を効率的に探索できるため、計算量はO((V+E)logV)となります。Eは辺の数を表します。
フィボナッチヒープを用いた場合: より高度なフィボナッチヒープを用いることで、計算量をO(E + VlogV)に改善できます。これは、辺の数が頂点数に対して十分に多い場合(E が Ω(VlogV) のオーダーである場合)に有効です。
正当性の証明
プリム法によって得られる木が最小全域木であることの証明は、帰納法によって行うことができます。アルゴリズムの各ステップで、木に追加される辺は、常に現在の木とまだ木に含まれていない頂点を結ぶ最小の重みの辺です。この性質により、アルゴリズムが終了したときに得られる木は、最小全域木であることが保証されます。より具体的には、最小全域木であると仮定した木に対し、プリム法で得られた木が異なる辺を一つ含んでいた場合、その辺を取り除きプリム法で選ばれた辺を追加しても、必ず同じかより小さい重みの全域木となるため、矛盾が発生します。
他のアルゴリズムとの比較
最小全域木問題を解くアルゴリズムとしては、プリム法の他にクラスカル法やブルーフカ法などがあります。クラスカル法は、辺を重みの小さい順にソートし、閉路を形成しないように木に追加していく方法です。一方、ブルーフカ法は、複数の木を同時に成長させていく方法です。これらのアルゴリズムは、それぞれ異なる特徴を持っており、グラフの形状や規模によって使い分けることができます。
まとめ
プリム法は、グラフ理論における基本的なアルゴリズムであり、最小全域木問題を効率的に解くことができます。その実装の容易さから、さまざまな分野で広く利用されています。ネットワーク設計やクラスタリングなど、現実世界の問題を解決するための強力なツールとして、今後も活用されていくでしょう。
参考資料
V. Jarník: O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57-63.
R. C. Prim: Shortest connection networks and some generalisations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401
Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. In Numerische Mathematik, 1 (1959), S. 269 ～ 271.
D. Cherition and R. E. Tarjan: Finding minimum spanning trees. In: SIAM Journal of Computing, 5 (Dec. 1976), pp. 724–741
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.
外部リンク
最小木問題: プリムのアルゴリズム
クラスカル法とプリム法で迷路を生成して解く at cut-the-knot
プリム法のアニメーション
Prim's Algorithm Java アプレット
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。