0

我正在研究 C++ 中的 A* 寻路算法。我有下面的简单代码，现在我需要找到 F 最低的对象。我知道如何通过迭代向量并手动比较它来做到这一点，但我认为可能还有其他更简单的方法来请求更少的代码。感谢您的回答

struct Node
{
    int f;
};

void func()
{
    std::vector<Node> nodes;
    //fill nodes with some objects
    //now find Node object with smallest F
}
4

3 回答 3

2

std::min_element和 lambda 比较器似乎最简洁。顺便说一句，使用普通向量似乎违背了使用 A* 等快速搜索算法的目的。在开发过程中可以，但是对于最终版本，您应该使用快速优先级队列，例如基于堆的std::priority_queue。

于 2013-08-30T15:37:16.287 回答
0

您可以保留一个临时 int 变量，并在此变量中记录向量的最小值索引。每次将新值推送到向量时，可以将其与带有临时索引的向量值进行比较，并记录新的最小值索引。

于 2013-08-30T15:40:29.057 回答
0

我在实现 A* 算法时遇到了同样的问题。

查看 boost::multi_index。它允许您拥有一个包含许多键的地图。因此，您可以同时拥有：按 F 对节点“排序”（当其中一个键为 F 时）和按节点位置快速查找（当第二个键为“节点”时）A* 中所需的内容。

对于“F”作为键，您需要指定该键是非唯一的，因为可以有许多具有相同 F 值的项目（因此对于该键，multi_index 需要表现为 std::multimap）。否则对于这种情况，multimap 将表现得像一个地图，并且不会存储具有相同“F”的节点。

当使用 multi_index 时，您可以通过键“F”获取第一个项目，这将是具有最低“F”值的项目。（AFAIR可以指定排序顺序）

于 2013-08-30T15:55:40.963 回答