C ++ A级明星的实现 - 确定节点是否已在清项目的优先级队列 [英] C++ A-star implementation -- determining whether a node is already in the priority queue of open items

问题描述

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

One step in the A* pathfinding algorithm requires searching the list of open nodes for the node you're currently interacting with, and adding that node to the list if it isn't already there, or updating its value and parent, if it's present but with a higher weight than the current version of the node.

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

These behaviors aren't supported in the STL priority_queue structure. How should I implement that step?

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

Updates since this question is getting a lot of views:

• 的std :: priority_queue可能看起来像一个很好的选择，但事实并非如此。

• std::priority_queue may look like a good choice for this, but it isn't.

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

Implementing A* yourself is an enormous confidence-booster, but after you've done it, you should try to switch to using the one provided by boost. I was nervous about installing it when I asked this question, but installation is very easy and won't produce any complications; and A* isn't the only useful functionality that boost provides. (In particular, if you don't use their string-processing functionality, you'll end up writing your own copy of it; I speak from personal experience...)

推荐答案

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

You can use a plain vector or array to store the elements and then use std::make_heap, std::push_heap, std::pop_heap, std::sort_heap, std::is_heap and std::is_heap_until to manage it.

这可以让你打破围堵和执行优先级队列的自定义操作，而不必自己实现的标准操作。

This allows you to break containment and implement custom operations on a priority queue, without having to implement the standard operations yourself.

这篇关于C ++ A级明星的实现 - 确定节点是否已在清项目的优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！