問題タブ [fibonacci-heap]

Introduction to Algorithmsの疑似コードには、次のように記載されています。

しかし、各ルート ノードの部分を効率的に実装するにはどうすればよいでしょうか。元のルートは、統合のプロセスを通じて同程度の他のルートにリンクされます。これにより、ルート ノードの循環リストを通過することが難しくなります。すべてのルート ノードをチェックしたかどうかを判断するにはどうすればよいですか?

ここでは新しいですが、かなり長い間ゲストとして潜んでいました:)

さて、私はフィボナッチ ヒープ (Java で) を使用して、ダイクストラの最短パス アルゴリズムを実行しようとしています。いくつかの検索の後、フィボナッチ ヒープを表す 2 つの既製の実装に出くわすことができました。最初の実装は非常によくできていて、ここで見つけることができます。2 番目の実装は、あまり洗練されていないように見えますが、ここにあります。

さて、これはすべて見栄えがよく、うまく見えます。ただし、ダイクストラのアルゴリズムのバージョンにこれらの実装の1つを使用したいのですが、まだ運がありません。使用中のダイクストラの実装は次のとおりです。

明らかなように、この実装では Java ベースの PriorityQueue クラス (バイナリ ヒープ自体に基づいていると思われます) を使用します。Java の PriorityQueue の代わりに前述のフィボナッチ ヒープ実装のいずれかを使用するように、上記のコードを変更したいと考えています。

私は多くのことを試しましたが、数行のコードを置き換えるのと同じくらい簡単だと確信していますが、それを行う方法がわかりません。

私は十分に明確であることを願っています。これは文字通り、これらのボードでの私の最初の投稿です。

どんな助けでも大歓迎です。

編集:コメントに応えて、私は自分の試みのシナリオの 1 つを使用して投稿を拡張すると考えました。

以下は、前にリンクされた 2 番目のフィボナッチ ヒープ実装を使用した、上記のダイクストラ法の修​​正版です。

これはほとんど疑似コードから直接変換されたものです (したがって、正しく変換しなかった可能性は十分にあります)。「decreaseKey() の値が大きくなりました」というエラーが表示されます。最小値を削除しようとすると、NullPointerException が発生します。

私は何か間違ったことをしていると確信しています。それが何であるかを知りたいです。繰り返しますが、これは 2 番目の FHeap 実装を使用しています。私は最初の実装を使用してそれを行うことを好みましたが (それはより徹底的でプロフェッショナルに見えます)、残念ながらその方法を理解できませんでした。

「アルゴリズムの紹介」から f-heap を学んでいますが、「キーの減少」操作は本当に混乱します。なぜこれに「カスケードカット」が必要なのですか?

この操作が削除された場合:

1. make-heap()、insert()、minimum()、および union() のコストは明らかに変更されていません
2. O(n(H)) 'consolidate' 操作では、ほとんどのルート ツリーのコストは、ルート リストに追加されたときに支払うことができるため、extract-min() は引き続き O(D(n)) です。残りの費用 O(D(n))
3. 減少キー (): 明らかに O(1)

D(n) については、正確に説明することはできませんが、まだ O(lgn) であると思います。「cascading-cut」がないため、ノードは少し後でルート リストに移動される可能性があります。父親の下に隠れても効率には影響しません。少なくとも、これで状況が悪化することはありません。

私の下手な英語で申し訳ありません:(

誰でも助けることができますか？ありがとう

.

こんにちは、みんな、

私は Erel Segal の C++ STL FibonacciHeap http://ideone.com/9jYnvを使用していますが、increase_key() メソッドが欠けていると思います。

私はそれを自分で実装しようとしていますが、その理論的な実装に関する多くの参照は見つかりませんでした。

increase_key 操作をどのように行うべきかについてのヒントを教えてください。

プロジェクトでフィボナッチ ヒープを使用する必要があり、ブースト ライブラリから使用しようとしています。しかし、任意のデータ型に対してユーザー定義の比較関数を設定する方法がわかりません。次のように定義された構造体ノードの最小ヒープを構築する必要があります。

ドキュメントを調べたところ、比較クラスがありました。しかし、それには要素が含まれていませんでした。ユーザー定義の比較関数の設定方法を教えてください。前もって感謝します。

Haskell で使用できるフィボナッチ ヒープ/優先度キューはありますか? (または漸近的により良いものでしょうか?)この質問でさまざまな優先度キューの実装のリストを見つけましたが、それらのいずれかがフィボナッチ ヒープの償却実行時間を満たしているかどうかを見つけることができませんでした:

• Find-minimum はO(1)償却時間です。
• 操作の挿入、キーの減少、およびマージ (結合) 作業は、O(1)償却時間です。
• 操作の削除と削除の最小値は、O(log n)の償却時間です。

理論上の境界の比較を参照してください。

O(1)ヒープ内の要素の優先度を下げるときに、償却された時間の複雑さで優先度キューを実装するための効率的なデータ構造であることがわかりました。ただし、CLRS の教科書によると、優先順位を下げる操作は、ターゲット要素を保持しているノードが既知であることを前提としています。最小ノードではない場合、目的のノードを効率的に取得する方法に興味があります。単純な実装と分析O(n)では、フィボナッチ ヒープで検索操作を実行するために、最悪の場合の時間の複雑さが生じます。これは、他の操作と比較して効率的ではありません。私の質問は、フィボナッチヒープに効率的な検索操作があるか、それとも必要ですか?