C ++中星实现 - 确定一个节点是否已经在清项目的优先级队列(C++ A-star impleme

在A *寻路算法中的一个步骤需要搜索开放节点的列表供您目前正与交互的节点，并添加该节点到列表中，如果它已不存在，或更新它的价值和家长，如果它的存在但比该节点的当前版本更高的权重。

这些行为不是在STL priority_queue结构支撑。我应该如何实现这一步？

因为这个问题的更新是获得了很多的观点：

的std :: priority_queue可能看起来像这个一个不错的选择，但事实并非如此。
实施A *自己是一个巨大的信心助推器，但你做了之后，你应该尝试切换到使用升压提供的一个。我很紧张，有关安装它，当我问到这个问题，而且安装非常方便，不会产生任何并发症; 和A *是不是提高提供了唯一有用的功能。（特别是，如果你不使用它们的字符串处理功能，你写出来的它自己的副本，我从个人的经验说...）

Answer 1:

可以使用一个普通的载体或阵列来存储中的元素，然后使用std::make_heap ， std::push_heap ， std::pop_heap ， std::sort_heap ， std::is_heap和std::is_heap_until来管理它。

这可以让你打破遏制并实现对优先级队列的自定义操作，而不必自己实现的标准操作。

Answer 2:

如果仅限于STL，你可以使用STL集合不断擦除并重新插入的元素（使用新的优先级）。

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（日志N），但它可能会花费更多的时间大集。

Answer 3:

STL priority_queue不适合对A *的实现。你需要支持堆结构， increase操作来更改已插入项目的优先级。使用Boost.Heap许多经典堆的实现。

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

Answer 4:

下面是我用这个，如果你真的想使用std :: priority_queue的解决方案：

当您需要更新已在优先级队列中的一个节点，只需插入具有相同的状态和新的成本值和家长到队列中的新节点。该节点的最近更新的副本会先脱落队列，并添加到您的访问设置。为了应对老重复，检查脱落的队列中的任何节点对您的访问组处理它。如果是在参观了设置，则通过该节点的最低成本路径已经见到的，所以就忽略它，处理下一个节点。