1

d_ary_heap_indirect を優先度キューとして使用しています (優先度が最も高い項目を最初に処理するため)、プロパティ マップを使用して優先度を格納しています。ただし、優先順位プロパティ マップの値を変更し、既にキューにある頂点を再度キューにプッシュすると、頂点が異なる位置で 2 回キューに表示されるような無効な状態になります。

ここにデモがあります：

#include <iostream>
#include <iomanip>

#include <boost/graph/grid_graph.hpp>
#include <boost/graph/detail/d_ary_heap.hpp>
#include <boost/property_map/property_map.hpp>

#include <cstdlib>

template <typename TQueue>
static void OutputQueue(TQueue queue);

int main(int, char*[])
{
  srand((unsigned int)time(NULL));
  srand48((unsigned int)time(NULL));

  boost::array<std::size_t, 2> lengths = { { 2,2 } };
  typedef boost::grid_graph<2> GraphType;
  GraphType graph(lengths);
  typedef boost::graph_traits<GraphType>::vertex_descriptor Vertex;
  typedef boost::property_map<GraphType, boost::vertex_index_t>::const_type GridIndexMapType;
  GridIndexMapType gridIndexMap(get(boost::vertex_index, graph));

  typedef boost::vector_property_map<std::size_t, GridIndexMapType> IndexInHeapMap;
  IndexInHeapMap index_in_heap(gridIndexMap);

  typedef boost::graph_traits<GraphType>::vertex_iterator VertexIteratorType;

  typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType;
  PriorityMapType priorityMap(gridIndexMap);
  VertexIteratorType vertexIterator, vertexIteratorEnd;

  typedef std::greater<float> ComparisonFunctor;
  typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, PriorityMapType, ComparisonFunctor > MutableQueueType;

  ComparisonFunctor comparisonFunctor;
  MutableQueueType mutableQueue(priorityMap, index_in_heap, comparisonFunctor);

  std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;

  // Add random values to the vertices and add them to the queue
  for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  {
    put(priorityMap, *vertexIterator, rand() % 1000);
  }

  for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  {
    mutableQueue.push(*vertexIterator);
  }

  std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;

  std::cout << "The priority queue is: " << std::endl;
  OutputQueue(mutableQueue);

  // Insert another set of random values for each vertex
  for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  {
    float newPriority = rand() % 1000;
    std::cout << "New priority for " << vertexIterator->operator[](0) << ", " << vertexIterator->operator[](1) << " " << newPriority << std::endl;
    put(priorityMap, *vertexIterator, newPriority);
  }

  for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  {
    //mutableQueue.push(*vertexIterator); // This makes sense that the queue would not end up sorted
    mutableQueue.push_or_update(*vertexIterator); // I thought this one should work
    //mutableQueue.update(*vertexIterator); // This one actually seems to UNsort the queue?
  }

  std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;

  std::cout << "The priority queue is: " << std::endl;
  OutputQueue(mutableQueue);

  std::cout << std::endl;

  return 0;
}

template <typename TQueue>
static void OutputQueue(TQueue queue)
{
  while( ! queue.empty() )
  {
    typename TQueue::value_type u = queue.top();

    // These two lines are equivalent
    std::cout << "vertex: " << u[0] << " " << u[1] << " priority: " << get(queue.keys(), u) << std::endl;

    queue.pop();
  }
}

そしてデモ出力：

There are 0 items in the queue.
There are 4 items in the queue.
The priority queue is: 
vertex: 1 1 priority: 445
vertex: 0 0 priority: 150
vertex: 0 1 priority: 84
vertex: 1 0 priority: 0
New priority for 0, 0 769
New priority for 1, 0 870
New priority for 0, 1 99
New priority for 1, 1 211
There are 8 items in the queue.
The priority queue is: 
vertex: 0 0 priority: 769
vertex: 1 0 priority: 870
vertex: 1 0 priority: 870
vertex: 0 0 priority: 769
vertex: 1 1 priority: 211
vertex: 1 1 priority: 211
vertex: 0 1 priority: 99
vertex: 0 1 priority: 99

デモでは、頂点ごとにランダムな優先度値を設定し、それらすべてをキューにプッシュするだけです。その後、まったく同じことを繰り返します。出力を見ると、いくつかのアイテムが異なる位置でキューに表示されていることがわかります (PriorityMap で同じ優先度値を参照しているため、予想どおり連続ではありません)。

問題は、アイテム (0,0) (新しい優先度 769) が優先度 870 の頂点 (1,0) の上に表示されることです。これにより、アイテムが間違った順序で処理される可能性があります。

2 つ目のアイテムを追加する代わりに、プッシュされたときにキュー内のアイテムを置き換える方法はありますか? (std::multiset のような現在の動作ではなく、std::set のように)?

--------- 編集 ------------ 「//頂点ごとに別のランダム値のセットを挿入する」ループで、「mutableQueue.push(*vertexIterator)」を置き換えました' と ：

mutableQueue.push_or_update(*vertexIterator);

残念ながら、それは私が期待することをしません-出力は次のようになります:

There are 0 items in the queue.
New priority for 0, 0 150
New priority for 1, 0 522
New priority for 0, 1 27
New priority for 1, 1 883
There are 4 items in the queue.
The priority queue is: 
vertex: 1 1 priority: 883
vertex: 1 0 priority: 522
vertex: 0 0 priority: 150
vertex: 0 1 priority: 27
New priority for 0, 0 658
New priority for 1, 0 591
New priority for 0, 1 836
New priority for 1, 1 341
There are 7 items in the queue.
The priority queue is: 
vertex: 0 1 priority: 836
vertex: 0 1 priority: 836
vertex: 0 0 priority: 658
vertex: 0 0 priority: 658
vertex: 1 0 priority: 591
vertex: 1 0 priority: 591
vertex: 1 1 priority: 341

さらに、 push() を update() だけに置き換えると、次のようになります。

There are 0 items in the queue.
New priority for 0, 0 806
New priority for 1, 0 413
New priority for 0, 1 592
New priority for 1, 1 861
There are 4 items in the queue.
The priority queue is: 
vertex: 1 1 priority: 861
vertex: 0 0 priority: 806
vertex: 0 1 priority: 592
vertex: 1 0 priority: 413
New priority for 0, 0 175
New priority for 1, 0 642
New priority for 0, 1 991
New priority for 1, 1 462
There are 4 items in the queue.
The priority queue is: 
vertex: 1 1 priority: 462
vertex: 0 1 priority: 991
vertex: 1 0 priority: 642
vertex: 0 0 priority: 175

現在、アイテムは 4 つしかありませんが (予想どおり)、並べ替えられていません。

----------- 編集 - 詳細情報 -------------- index_in_heap マップに問題があると思います。追加した：

std::cout << "Index added: " << get(index_in_heap, v) << std::endl;

この行の後:

put (index_in_heap, v, インデックス);

d_ary_heap_indirect::push(Value) で。

私も追加しました

std::cout << "Index added caller: " << get(index_in_heap, v) << std::endl;

キューに値を追加する最初のラウンドの後 (この行の後: mutableQueue.push(*vertexIterator);

出力は次のとおりです。

0、0 の元の優先度 641 インデックスが追加されました: 0 インデックスが追加された呼び出し元: 0 1、0 の元の優先度 40 インデックスが追加されました: 1 インデックスが追加された呼び出し元: 0、1 400 の元の優先度for 1, 1 664 インデックス追加: 3 インデックス追加呼び出し元: 0

この最後のインデックスが push() 関数内では 3 であるのに、呼び出し元から照会すると 0 になる理由がわかりません。

update() 関数内の同じものを見ると、index_in_heap がガベージを返しているように見えます。つまり、size_type index = get(index_in_heap, v); の値を調べます。update() で、頂点 (0,0) で呼び出された場合、「インデックス」の値は 4294967295 です (範囲 [0,3] にあると予想される場合)。

誰でもこれを説明できますか？おそらく index_in_heap マップの設定が間違っているのでしょうか?

4

2 に答える 2

1

ノードの優先順位を変更しただけでは、優先キューはその構造を更新しません。ノードが挿入されたら、その優先度定数を考慮する必要があります。優先度を更新する必要がある場合は、優先度キューにこれを伝える必要があります。この目的のために、どのノードが新しい優先度を取得するかを伝える必要があります。

残念ながら、ある種のノード ID と優先度を追跡すると、優先度キューが遅くなります。d ヒープの場合、ノードがどこに移動したかを追跡する必要があり、更新が比較的高価になります。フィボナッチヒープなどのノードベースのヒープの場合、ノードは配置されたままになりますが、維持費が高くなる傾向があります (フィボナッチヒープには興味深い理論的複雑性がありますが、これは非現実的なサイズの問題に対してのみ重要です)。本で説明されているプラ​​イオリティ キューへのすべてのアプローチを実装しましたが、妥協点は思いつきませんでした。

于 2012-09-03T18:46:51.967 に答える
0

d_ary_heap_indirect は、優先度の増加のみを許可するように設計されています。update() および push_or_update() 関数で変更した場合:

preserve_heap_property_up(インデックス);

に

preserve_heap_property_up(インデックス); preserve_heap_property_down();

キューをソートしたまま、優先度を増減できるようです。

于 2012-09-05T17:18:30.090 に答える