6

一種の高度な優先度キューイングをサポートするデータ構造を探しています。考え方は以下の通りです。いくつかのアイテムを順番に処理する必要があり、任意の時点で、次に実行する「最適な」アイテムを知っています (何らかのメトリックに基づいて)。問題は、アイテムを処理すると、他のいくつかのアイテムのメトリックが変更されるため、静的キューではうまくいかないことです。

私の問題では、優先度を更新する必要があるアイテムを知っているので、探しているデータ構造にはメソッドが必要です

  • enqueue(アイテム、優先度)
  • デキュー()
  • requeue(item, new_priority)

理想的には、O(log n) 時間で再キューイングしたいと考えています。何か案は？

4

4 に答える 4

3

必要なものと同様の時間の複雑さを持つアルゴリズムがありますが、必要な場合は平均時間O(log n)でのみ実行されます。このアルゴリズムでは、関数なしで既存のプライオリティ キューを使用できます。requeue()

グラフ内のノードと優先キュー内の要素の間に接続があると仮定します。プライオリティ キューの要素には、 と呼ばれる余分なビットも格納しますignore。dequeue変更された実行のアルゴリズムは次のとおりです。

  1. 電話dequeue()
  2. 要素のignoreビットが true の場合は 1 に戻り、それ以外の場合はアイテム ID を返します。

enqueue変更された実行のアルゴリズムは次のとおりです。

  1. エンキューを呼び出す(項目、優先度)
  2. グラフ内の項目の隣接ノードvを 1 つずつ 訪問する
    • ignoreキュー内の現在リンクされている要素のビットを true に変更します。v
    • enqueue(v, new_priority(v))
    • ノードの接続をv新しくエンキューされた要素に変更します。
    • num_ignore++
  3. 無視要素( num_ignore)の数が非無視要素の数よりも多い場合、プライオリティ キューを再構築します。
    • dequeueすべての要素、保存、およびenqueue無視されない要素のみを再び

このアルゴリズムでは、ignoreビットの設定に一定の時間がかかるため、基本的に無視要素O(log n)が蓄積されるまで「リキュー」を遅らせます。O(n)次に、それらすべてを 1 回クリアしますO(n log n)。したがって、平均して、各「再キューイング」にはO(log n).

于 2012-12-28T17:31:37.320 に答える
1

要素を更新するとき、複雑さは更新された要素の数にも依存する必要があるため、求めている複雑さを達成することはできません。

ただし、特定のステップで更新される要素の数がほとんどであると仮定するとp、ヒープの典型的な実装のほとんどは、O(1)max-element の値を取得するための複雑さ、O(log(n))deque、およびO(p * log(n))更新操作に対して行われます。実装がかなり簡単で、あなたが求めているものに対して機能するので、私は個人的にバイナリヒープを選びます。

于 2012-12-28T17:54:11.450 に答える
1

プライオリティ キューはまさにこのためのものです。たとえば、max-heapを使用して実装できます。

于 2012-12-28T09:31:41.130 に答える
0

http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdfでは、increaseKey()、decreaseKey()、および remove() 操作について説明しています。これにより、やりたいことができるようになります。C++ stdlib の実装がまだサポートしているかどうかはわかりません。

さらに、バージョン: http://theboostcpplibraries.com/boost.heapは一部のサブクラスの update() をサポートしているようですが、完全なリファレンスはまだ見つかりません。

于 2015-10-10T01:19:56.597 に答える