3

フィボナッチ ヒープを理解するのは難しいことがわかっています。しかし、いくつかの質問は私には本当に不明確です:

  • t + 2m のような潜在的な関数を選択するのはなぜですか? 理由は何ですか？
  • ノードのマーキングの背後にある理由は何ですか?ノードをルート リストなどに配置すると便利だと思いますが、なぜそのようなスキームを考え出すのでしょうか?

ありがとう！

4

1 に答える 1

4

潜在的な機能を選択する理由は、さまざまな要因の組み合わせに関係しています。通常、ポテンシャルは t + 2m として選択されます。ここで、t はツリーの数、m はマークされたノードの数です。これらの部分を個別に分析できます。

第 1 に、可能な関数には at term が含まれます。これは、delete-min ステップが、リンクされたリスト内の異なるツリーを繰り返しマージすることによって機能するためです。これを行うのに必要な時間は、ツリーの数によって異なり、反復ごとにツリーの数がおよそ O(log n) の数まで減少します。ここで、n はヒープ内のノードの数です。可能性のある関数に用語を含めることにより、すべてのツリーを折りたたむために行われた作業を、最初にこのリストにツリーを追加した以前の操作にバックチャージできます。

同様の理由で、ポテンシャル関数には 2m の項が含まれています。減少キーを呼び出すと、ノードをその親から切り離し、親をマークします。親がすでにマークされている場合は、それを切り取り、その親にもマークを付けます。ここで行われる作業量は、ノードを切断し続けるパスの長さに比例しますが、関連するすべてのノードのマークが解除されます。したがって、マークされたノードの数を考慮に入れる潜在的な関数がある場合、単一の長い一連のカットはコストがかかるかもしれませんが、その作業は以前の操作にバックチャージされ、より均等に分散できると言えます。この項が m ではなく 2m である理由は、カットされたノードの数を減らしてポテンシャルを下げると、リンクされたリストにツリーを追加して t ポテンシャルも増加させるためです。

マーキングを行う理由については、ほとんどの場合、フィボナッチ ヒープに残すことができるツリーの数とサイズを決定する際に、数学が正しく機能するようにするためです。これは、そもそもフィボナッチ ヒープを考え出すために必要な真の天才的なステップであったと言えます。本質的に、各ツリーからあまりにも多くの子を切り取ることができる場合、ヒープはバランスを失い、十分に切り取ることができない場合は、減少キーを効率的に実装できません。「子供を 1 人失う可能性がある」という言い方のバランスを見つけることは良い妥協点であり、結果として得られる計算は非常にうまくいきます。

お役に立てれば！

于 2012-01-31T21:48:12.630 に答える