c++ - 在 boost::d_ary_heap_indirect 中更新优先级

Question

我使用 d_ary_heap_indirect 作为优先级队列(首先处理具有最高优先级的项目)，使用属性映射来存储优先级。但是，当我更改优先级属性映射中的值并将已在队列中的顶点再次插入队列时，会导致一种无效状态，即顶点在队列中的不同位置出现两次。

这是一个演示:

#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) 上方。这会导致项目以错误的顺序处理。

有没有办法在推送时替换队列中的项目而不是添加第二个项目？ (像 std::set 而不是像 std::multiset 这样的当前行为)？

------------ 编辑------------在“//为每个顶点插入另一组随机值”循环中，我将“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, index);

在 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索引添加调用者:1原始优先级为 0, 1 400添加的索引:2索引添加调用者:2原始优先级为 1, 1 664添加的索引:3索引添加调用者:0

我不明白为什么最后一个索引在 push() 中是 3函数，但是当我从调用者查询它时为 0？

当我查看 update() 函数中的相同内容时，index_in_heap 似乎只是返回垃圾。也就是说，我看size_type index = get(index_in_heap, v) 的值；在 update() 和当用顶点 (0,0) 调用时，'index' 的值为4294967295(我希望它在 [0,3] 范围内)。

谁能解释一下？也许我没有正确设置 index_in_heap 映射？

Answer 1

当你只是改变节点的优先级时，优先级队列不会更新它的结构。插入节点后，您需要考虑其优先级常量。如果您需要更新优先级，您需要将此告知优先级队列。为此，您需要告诉它哪个节点获得什么新优先级。

不幸的是，跟踪某种节点标识和优先级会使优先级队列变慢:对于 d-heap，必须跟踪节点移动的位置，从而使更新相对昂贵。对于基于节点的堆，例如 Fibonacci 堆，节点保持不变但维护起来往往更昂贵(Fibonacci 堆具有有趣的理论复杂性，然而，这只对不切实际的大小问题有影响)。尽管我实现了所有可以在书中描述的优先级队列方法，但我还没有想出任何中间立场。