2

A* 寻路算法中的一个步骤需要在打开节点列表中搜索您当前正在与之交互的节点，如果该节点尚不存在，则将该节点添加到列表中，或者更新其值和父节点（如果存在）但权重高于当前版本的节点。

STL priority_queue 结构不支持这些行为。我应该如何实施该步骤？

更新，因为这个问题得到了很多意见：

  • std::priority_queue 看起来可能是一个不错的选择，但事实并非如此。

  • 自己实现 A* 可以极大地增强信心，但是在完成之后，您应该尝试切换到使用 boost 提供的那个。当我问这个问题时，我对安装它感到紧张，但安装非常容易，不会产生任何并发症；A* 并不是 boost 提供的唯一有用的功能。（特别是，如果你不使用他们的字符串处理功能，你最终会编写自己的副本；我是根据个人经验说的......）

4

5 回答 5

2

STLpriority_queue不适合 A* 实现。您需要一个堆结构来支持increase更改已插入项的优先级的操作。使用Boost.Heap来实现许多经典堆。

编辑： Boost.Graph 库也有A* 搜索的实现。

于 2012-08-11T07:18:28.710 回答
2

如果您仅限于 STL，则可以使用 STL Set 并不断擦除和重新插入元素（具有新的优先级）。

Set< pair<int,int> > s; // < priority,value >
s.insert( make_pair(0,5) );

// Decrease Key operation //
s.erase( s.find( make_pair(0,5) ) );
s.insert( make_pair(1,5) );

时间复杂度仍然是 O(log N)，但对于大型集合可能需要更多时间。

于 2012-08-11T08:04:59.903 回答
2

如果您真的想使用 std::priority_queue，这是我用于此的解决方案：

当您需要更新已经在优先级队列中的节点时，只需将具有相同状态和新成本值和父节点的新节点插入队列中即可。该节点的最新更新副本将首先退出队列并添加到您访问的集合中。要处理较旧的重复项，请在处理之前检查任何从队列中出来的节点与您访问的集合。如果它在访问集中，则已经看到通过该节点的最低成本路径，因此忽略它并处理下一个节点。

于 2015-10-04T21:53:22.030 回答
1

您可以使用普通向量或数组来存储元素，然后使用、std::make_heap、std::push_heap、std::pop_heap和std::sort_heap来管理它。std::is_heapstd::is_heap_until

这允许您打破限制并在优先级队列上实施自定义操作，而无需自己实施标准操作。

于 2012-08-11T08:15:27.307 回答
0

对此有三种可能的解决方案：

  1. 独立于优先级队列跟踪当前打开的节点列表。尝试以与封闭节点相同的方式创建节点列表。

  2. 创建节点映射（按坐标）到开闭状态。

  3. 安装 Boost 库，其中包括 A* 的模板实现（我认为在 中<graph>）。

于 2012-08-11T07:04:05.243 回答