20

私はプリムのアルゴリズムとその実装を知っていますが、いつも私が今聞きたい部分をスキップします。フィボナッチヒープを使用したプリムのアルゴリズムの実装は次のとおりであると書かれておりO(E + V log(V))、私の質問は次のとおりです。

  • 簡単にフィボナッチヒープとは何ですか?
  • それはどのように実装されていますか？と
  • Prim のアルゴリズムをフィボナッチ ヒープでどのように実装できますか?
4

3 に答える 3

32

フィボナッチ ヒープはかなり複雑な優先キューであり、そのすべての操作で優れた償却漸近動作を行います。挿入、検索分、キーの減少はすべて O(1) 償却時間で実行され、削除と抽出分は償却 O で実行されます。 (lg n) 時間。この件に関する優れたリファレンスが必要な場合は、CLRS の「Introduction to Algorithms, 2nd Edition」を手に取り、その章を読むことを強くお勧めします。それは非常によく書かれており、非常に説明的です。 Fredman と Tarjan によるフィボナッチ ヒープに関する元の論文はオンラインで入手できるので、ぜひチェックしてみてください。密度が高いですが、素材の扱いが良いです。

フィボナッチ ヒープと Prim のアルゴリズムの実装を見たい場合は、私自身の実装に恥知らずなプラグインを提供する必要があります。

  1. フィボナッチ ヒープの私の実装。
  2. フィボナッチ ヒープを使用した Prim のアルゴリズムの実装。

これらの実装の両方のコメントは、それらがどのように機能するかについてかなり適切な説明を提供するはずです。明確にするために私にできることがあれば教えてください！

于 2011-01-28T08:13:39.617 に答える
12

Prim のアルゴリズムは、既に選択されている頂点のグループと残りの頂点の間で重みが最小のエッジを選択します。
したがって、プリムのアルゴリズムを実装するには、最小限のヒープが必要です。エッジを選択するたびに、既に選択した頂点のグループに新しい頂点が追加され、隣接するすべてのエッジがヒープに入ります。
次に、ヒープから最小値を持つエッジを再度選択します。

フィボナッチ
:
最小エッジの選択 = O(最小値を削除する時間) = O(log(E)) = O(log(V))
ヒープへのエッジの挿入 = O(アイテムをヒープに挿入する時間) = 1

最小ヒープ:
最小エッジの選択 = O(ヒープから最小値を削除する時間) = O(log(E)) = O(log(V))
ヒープへのエッジの挿入 = O(ヒープへのアイテムの挿入時間) = O(log (E)) = O(log(V))

(E =~ V^2 ... だから log(E) == log(V^2) == 2Log(V) = O(log(V))

したがって、合計で E 個の挿入と V 個の最小選択があります (最終的にはツリーです)。

したがって、最小ヒープでは次のようになります。

O(Vlog(V) + Elog(V)) == O(Elog(V))

フィボナッチ ヒープでは次のようになります。

O(ブログ(V) + E)

于 2011-01-28T07:56:23.737 に答える
2

数年前にフィボナッチ ヒープを使用して Dijkstra を実装しましたが、問題はかなり似ています。基本的に、フィボナッチ ヒープの利点は、セットの最小値を一定の操作で見つけることができることです。これは、各ステップでこの操作を実行する必要がある Prim と Dijkstra に非常に適しています。

なぜそれが良いのか

二項ヒープ (より「標準的な」方法) を使用するこれらのアルゴリズムの複雑さは O(E * log V) です。新しい頂点を二項ヒープ (log V) に追加するか、そのキーを減らし (log V)、ヒープの最小値 (別の log V) を見つける必要があります。

代わりに、フィボナッチ ヒープを使用する場合、頂点を挿入したり、ヒープ内のキーを減らしたりするコストは一定であるため、そのための O(E) しかありません。ただし、頂点の削除は O(log V) であるため、最終的には O(V * log V) を追加するすべての頂点が削除され、合計 O(E + V * log V) になります。

したがって、グラフが十分に密集している場合 (例: E >> V)、フィボナッチ ヒープを使用する方が二項ヒープよりも優れています。

方法

したがって、アイデアは、フィボナッチ ヒープを使用して、既に構築したサブツリーからアクセスできるすべての頂点を格納し、そこにつながる最小のエッジの重みでインデックス付けすることです。別のデータ構造を使用して実装または Prim のアルゴリズムを理解していれば、代わりにフィボナッチ ヒープを使用することに実際の困難はありません。通常どおりヒープの insert メソッドと deletemin メソッドを使用し、decreasekeyメソッドを使用して頂点を更新します。それにつながるエッジをリリースするとき。

唯一難しいのは、実際のフィボナッチ ヒープを実装することです。

ここですべての実装の詳細を説明することはできません (ページが必要になります)。まだ持っていないが、アルゴリズムに興味がある場合は、入手することを強くお勧めします! 言語にとらわれず、すべての標準アルゴリズムとその証明に関する詳細な説明を提供し、それらすべてを使用して新しいアルゴリズムを設計および証明するための知識と能力を確実に向上させます。この PDF (リンクしたウィキペディアのページから) は、実装の詳細の一部を提供しますが、アルゴリズムの紹介ほど明確ではありません。

私はそれを行った後に私が書いたレポートとプレゼンテーションを持っています.コードはCaml（およびフランス語）で書かれているので、それが役立つかどうかはわかりません!!! そして、あなたがそれの何かを理解できるなら、甘やかしてください、私はプログラミングを始めたばかりだったので、当時の私のコーディングスキルはかなり貧弱でした...

于 2011-01-28T08:46:06.183 に答える