Loading article…
コンピュータサイエンスにおいて、プリムのアルゴリズムは、重み付き無向グラフの最小全域木を見つける貪欲アルゴリズムです。つまり、ツリー内のすべての辺の合計重みが最小となる、すべての頂点を含むツリーを形成する辺のサブセットを見つけます。このアルゴリズムは、任意の開始頂点から一度に 1 つの頂点ずつこのツリーを構築し、各ステップでツリーから別の頂点への最も安価な接続を追加することで動作します。
このアルゴリズムは1930年にチェコの数学者ヴォイチェフ・ヤルニーク[1]によって開発され、後にコンピュータ科学者の ロバート・C・プリム[2]によって1957年に再発見され再発表されました。 [3]そのため、ヤルニークのアルゴリズム、[4]プリム–ヤルニークアルゴリズム、[5]プリム–ダイクストラアルゴリズム[6] またはDJPアルゴリズムと呼ばれることもあります。[7]
この問題に対する他のよく知られたアルゴリズムには、クラスカルのアルゴリズムとボルフカのアルゴリズムがあります。[8]これらのアルゴリズムは、切断されている可能性のあるグラフの最小全域木を見つけます。対照的に、プリムのアルゴリズムの最も基本的な形式は、接続されたグラフの最小全域木のみを見つけます。ただし、グラフの各接続コンポーネントに対して個別にプリムのアルゴリズムを実行すると、最小全域木を見つけるためにも使用できます。[9]漸近的な時間計算量の観点から、これら3つのアルゴリズムは疎なグラフでは同等に高速ですが、他のより洗練されたアルゴリズムよりも低速です。[7] [6]ただし、十分に密度の高いグラフでは、プリムのアルゴリズムを線形時間 で実行することができ、他のアルゴリズムの時間制限を満たすか、それを改善します。[10]
説明
このアルゴリズムは、非公式には次のステップを実行するものとして説明できます。
- グラフから任意に選択された単一の頂点を持つツリーを初期化します。
- ツリーを 1 つのエッジだけ成長させます。ツリーにまだ存在しない頂点にツリーを接続するエッジのうち、最小の重みのエッジを見つけて、ツリーに転送します。
- 手順 2 を繰り返します (すべての頂点がツリー内に含まれるまで)。
より詳細には、以下の疑似コードに従って実装できます。
- グラフの各頂点vに、数値C [ v ] ( vへの接続の最も安価なコスト) とエッジE [ v ] (その最も安価な接続を提供するエッジ) を関連付けます。これらの値を初期化するには、C [ v ] のすべての値を +∞ (または最大エッジ重みよりも大きい任意の数) に設定し、各E [ v ] を、 v を前の頂点に接続するエッジがないことを示す特別なフラグ値に設定します。
- 空のフォレストFと、 Fにまだ含まれていない頂点の集合Q (最初はすべての頂点) を初期化します。
- Qが空になるまで、次の手順を繰り返します。
- C [ v ]の最小値を持つ頂点vをQから探して削除します。
- Fにvを加える
- v を他の頂点wに接続する辺vw をループします。このような各辺について、wがまだQに属し、vw の重みがC [ w ] よりも小さい場合は、次の手順を実行します。
- C [ w ] を辺vwのコストに設定する
- E [ w ] が辺vwを指すように設定します。
- E 内の対応する辺を具体的に含むFを返す
上で説明したように、アルゴリズムの開始頂点は任意に選択されます。これは、アルゴリズムのメイン ループの最初の反復では、すべて等しい重みを持つQの頂点セットが保持され、入力グラフの各接続コンポーネントのスパニング ツリーが完成すると、アルゴリズムによってFで新しいツリーが自動的に開始されるためです。アルゴリズムは、 C [ s ] をCの他の値よりも小さい数値 (たとえば、ゼロ) に設定することで、特定の頂点sから開始するように変更できます。また、関連するエッジがないとフラグが付けられた別の頂点に遭遇するたびに停止することで、スパニング フォレスト全体ではなく単一のスパニング ツリーのみを検索するように変更できます (非公式の説明により一致します)。
アルゴリズムのさまざまなバリエーションは、集合Qの実装方法が異なります。頂点の単純なリンク リストまたは配列として、またはより複雑な優先キューデータ構造として実装されます。この選択によって、アルゴリズムの時間計算量が異なります。一般に、優先キューは最小コストで頂点v を見つけるのが速くなりますが、 C [ w ]の値が変化すると、よりコストのかかる更新が必要になります。
時間計算量
プリムのアルゴリズムの時間計算量は、グラフに使用されるデータ構造と、重みによるエッジの順序付け (優先度キューを使用して実行可能) によって異なります。次の表に、一般的な選択肢を示します。
隣接行列または隣接リストのグラフ表現を使用し、重みの配列を線形検索して追加する最小重みエッジを見つけるというプリムの単純な実装では、 O (|V| 2 ) の実行時間が必要です。ただし、ヒープを使用してアルゴリズムの内部ループで最小重みエッジの検索を実装すると、 この実行時間を大幅に短縮できます。
最初の改良版では、ヒープを使用して入力グラフのすべての辺を重み順に並べて格納します。これにより、最悪の場合の実行時間は O(|E| log |E|) になります。ただし、辺の代わりに頂点を格納すると、さらに改善されます。ヒープは、部分的に構築された最小全域木(MST) 内の任意の頂点に接続する最小の辺重み (そのような辺が存在しない場合は無限大) で頂点を順序付けます。頂点vが選択されて MST に追加されるたびに、部分的な MST の外側にあるすべての頂点wに対してキー減少操作が実行され、vはwに接続され、キーは以前の値と ( v、w )の辺コストの最小値に設定されます。
単純なバイナリヒープデータ構造を使用すると、プリムのアルゴリズムは、|E| が辺の数、|V| が頂点の数である場合、O (|E| log |V|) の時間で実行できることが示されます。より洗練されたフィボナッチヒープを使用すると、これをO (|E| + |V| log |V|)に短縮できます。これは、グラフが十分に密で|E| がω (|V|)である場合に漸近的に高速になり、 |E| が少なくとも |V| log |V| である場合に線形時間になります。さらに密度の高いグラフ ( c > 1に対して少なくとも |V| c の辺を持つ) の場合、フィボナッチヒープの代わりにd進ヒープ を使用することで、プリムのアルゴリズムをさらに簡単に線形時間で実行できます。[10] [11]
正しさの証明
P を連結された重み付きグラフとします。プリムのアルゴリズムの各反復において、サブグラフ内の頂点をサブグラフ外の頂点に接続する辺が見つかる必要があります。 P は連結されているため、すべての頂点へのパスが常に存在します。プリムのアルゴリズムの出力Y は、ツリーYに追加された辺と頂点が連結されているため、ツリーです。 Y 1 をグラフ P の最小全域木とします。 Y 1 = Yの場合、Yは最小全域木です。それ以外の場合、e をツリーYの構築中に追加された、ツリーY 1にない最初の辺とし、V を辺e の前に追加された辺によって接続された頂点の集合とします。この場合、辺eの一方の端点は集合Vに含まれますが、もう一方は含まれません。ツリーY 1はグラフPの全域木であるため、ツリーY 1には 2 つの端点を結合するパスが存在します。経路に沿って進むと、集合V内の頂点と集合Vにない頂点を結ぶ辺fに遭遇するはずです。ここで、辺eがツリーYに追加された反復で、辺fも追加される可能性があり、その重みがeより小さい場合は辺eの代わりに追加されます。辺fは追加されなかったため、次のように結論付けられます。
木Y 2 を、木Y 1から辺f を削除し、辺eを追加することによって得られるグラフとします。木Y 2は連結されており、木Y 1と同じ数の辺を持ち、辺の合計重みは木Y 1の重みより大きくないことは簡単に示せます。したがって、木 Y 2 はグラフPの最小全域木でもあり、辺eと、セットVの構築中にその前に追加されたすべての辺を含みます。上記の手順を繰り返すと、最終的に木Yと同一のグラフPの最小全域木が得られます。これは、 Yが最小全域木であることを示しています。最小全域木では、サブ領域の最初のサブセットを、最小であると想定されるより大きなサブセットXに拡張できます。
並列アルゴリズム
プリムアルゴリズムのメインループは本質的に順次的であるため、並列化できません。ただし、サイクルを形成しない最小の重みを持つ次のエッジを決定する内側のループは、利用可能なプロセッサ間で頂点とエッジを分割することで並列化できます。[12]次の疑似コードはこれを示しています。
- 各プロセッサに長さの連続する頂点のセットを割り当てます。
- 順次アルゴリズムと同様に C、E、F、Q を作成し、各プロセッサが頂点セットへの入力エッジを保持するように、すべてのプロセッサ間で C、E、およびグラフを分割します。 、は、プロセッサ に格納されているC、Eの部分を表すものとします。
- Qが空になるまで、次の手順を繰り返します。
- 各プロセッサで、 [ ]内の最小値を持つ頂点を見つけます(ローカル ソリューション)。
- 局所解を最小化して、 C [ v ]の最小値（全体解）を持つ頂点vを見つけます。
- 選択したノードをすべてのプロセッサにブロードキャストします。
- v をFに追加し、E [ v ] が特殊フラグ値でない場合は、E [ v ] もFに追加します。
- すべてのプロセッサで、順次アルゴリズムと同様に更新します。
- リターンF
このアルゴリズムは、一般に、分散マシン[12]と共有メモリマシン[13]に実装できます。実行時間は、reduceおよびbroadcast操作が で実行できると仮定すると、 です。[12]共有メモリマシン用の Prim アルゴリズムの変形も検討されており、この変形では、Prim のシーケンシャルアルゴリズムが異なる頂点から開始して並列に実行されます。[14]ただし、分散最小全域木問題をより効率的に 解決するための、より洗練されたアルゴリズムが存在することに注意する必要があります。
参照
- ダイクストラのアルゴリズム、最短経路問題に対する非常に類似したアルゴリズム
- グリードイドはプリムのアルゴリズムの正しさを理解するための一般的な方法を提供する
参考文献
- ^ Jarník, V. (1930)、「O jistém problému minimálním」[特定の最小限の問題について]、Práce Moravské Přírodovědecké Společnosti (チェコ語)、6 (4): 57–63、hdl :10338.dmlcz/500726。
- ^ Prim, RC (1957 年 11 月)、「最短接続ネットワークといくつかの一般化」、Bell System Technical Journal、36 (6): 1389–1401、Bibcode :1957BSTJ...36.1389P、doi :10.1002/j.1538-7305.1957.tb01515.x。
- ^ Dijkstra, EW (1959 年 12 月)、「グラフに関する 2 つの問題についてのメモ」(PDF)、Numerische Mathematik、1 (1): 269–271、CiteSeerX 10.1.1.165.7577、doi :10.1007/BF01386390、S2CID 123284777 。
- ^ セジウィック、ロバート、ウェイン、ケビン・ダニエル（2011）、アルゴリズム（第4版）、アディソン・ウェズリー、p. 628、ISBN 978-0-321-57351-3。
- ^ ローゼン、ケネス（2011）、離散数学とその応用（第7版）、マグロウヒルサイエンス、p.798。
- ^ ab Cheriton, David ; Tarjan, Robert Endre (1976)、「最小全域木の検索」、SIAM Journal on Computing、5 (4): 724–742、doi :10.1137/0205051、MR 0446458。
- ^ ab Pettie, Seth; Ramachandran, Vijaya (2002 年 1 月)、「最適な最小スパニング ツリー アルゴリズム」(PDF)、Journal of the ACM、49 (1): 16–34、CiteSeerX 10.1.1.110.7670、doi :10.1145/505241.505243、MR 2148431、S2CID 5362916 。
- ^ Tarjan, Robert Endre (1983)、「第 6 章 最小全域木 6.2. 3 つの古典的アルゴリズム」、データ構造とネットワーク アルゴリズム、CBMS-NSF 応用数学地域会議シリーズ、第 44 巻、産業応用数学協会、pp. 72–77。
- ^ ケプナー、ジェレミー、ギルバート、ジョン（2011）、線形代数、ソフトウェア、環境、ツールの言語によるグラフアルゴリズム、第22巻、産業応用数学協会、p.55、ISBN 9780898719901。
- ^ ab Tarjan (1983)、77ページ。
- ^ ジョンソン、ドナルド B. (1975 年 12 月)、「更新と最小スパニング ツリーの検索による優先キュー」、情報処理レター、4 (3): 53–57、doi :10.1016/0020-0190(75)90001-0。
- ^ abc Grama, Ananth; Gupta, Anshul; Karypis, George; Kumar, Vipin (2003)、『並列コンピューティング入門』、pp. 444–446、ISBN 978-0201648652
- ^ クイン、マイケル J.; デオ、ナーシン (1984)、「並列グラフアルゴリズム」、ACM コンピューティング調査、16 (3): 319–348、doi : 10.1145/2514.2515、S2CID 6833839
- ^ Setia, Rohit (2009)、「最小スパニング ツリー問題に対する新しい並列アルゴリズム」(PDF)、Proc. International Conference on High Performance Computing (HiPC)
外部リンク
- ランダムに分布した点におけるプリムのアルゴリズムの進行
ウィキメディア・コモンズにおけるプリムのアルゴリズムに関連するメディア