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）出现在顶点 (1,0) 上方，优先级为 870。这将导致项目以错误的顺序处理。

有没有办法在推送队列时替换队列中的项目而不是添加第二个项目？（像 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;

在这一行之后：

放（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 添加的索引调用者：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 映射？

score 1 · Accepted Answer

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

不幸的是，跟踪某种节点标识和优先级会使优先级队列变慢：对于 d-heap，必须跟踪节点移动的位置，这使得更新相对昂贵。对于基于节点的堆，例如，斐波那契堆，节点保持不变，但维护成本往往更高（斐波那契堆具有有趣的理论复杂性，但仅对不切实际大小的问题很重要）。尽管我实现了所有可以在书中找到的优先级队列方法，但我还没有提出任何中间立场。

score 0 · Accepted Answer

d_ary_heap_indirect 旨在仅允许增加优先级。如果在 update() 和 push_or_update() 函数中你改变了：

preserve_heap_property_up（索引）；

至

preserve_heap_property_up（索引）；preserve_heap_property_down();

它似乎允许在保持队列排序的同时增加或减少优先级。

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

2 回答 2

Related

Reference