fibonacci-heap - フィボナッチヒープのプロジェクトのアイデア

Question

私は初心者レベルのコンピュータープログラミングクラスに参加しており、（他の3人の学生と一緒に）最終プロジェクトにフィボナッチヒープを実装したいと考えています。誰かがフィボナッチヒープのいくつかの良いアプリケーションを提案できますか？良いプレゼンテーション資料になるほど派手なものはありますか？

Answer 1

フィボナッチヒープは、実行時間を改善するために一部のグラフアルゴリズムで使用されます。これらのグラフアルゴリズムはかなり「派手」である可能性があるため、それらを紹介することができます。たとえば、ダイクストラのアルゴリズムでは、漸近的な実行時間を改善するためにフィボナッチヒープを使用することがあると思います。

Answer 2

フィボナッチ ヒープの効率から (理論的には) 恩恵を受ける多くのアルゴリズムがあります。その中で最も簡単なのは、最短経路問題に対するダイクストラのアルゴリズムと、最小スパニング ツリーに対するプリムのアルゴリズムです。

注意: フィボナッチ ヒープは理論的には最適ですが、上記の 2 つの問題ではバイナリ ヒープよりも優れている傾向があります。フィボナッチ ヒープを真に輝かせるには、次のいずれかのケースが必要です。b) 操作の大部分は updateKey/insert/delete です。フィボナッチ ヒープは次の extractMin まで更新を「グループ化」するため、「バッチ」が大きいほど効率的になります。