如果存在某个结构成员，如何检查多集，而不是使用for循环

Question

我正在修改一个轻松的a*程序，改为使用a*。作为A*算法的一部分，有一个检查：

if neighbor not in openSet
openSet.add(neighbor)

openSet是一个：

multiset<cells> OPL;

细胞为：

struct cells {
int currentCell;
float fCost;
};  

因此，我想在我的代码中添加这个检查邻居是否已经存在于openSet中。然而，multiset中的结构是我以前从未使用过的。我现在得到的解决方案受到了这个线程的启发，并且是这样工作的：

for (std::multiset<cells>::iterator it = OPL.begin(); it != OPL.end(); it++)
{
cells const & f = *it;
if(f.currentCell==neighborCell){
return false;
}
}
return true;

然而，这似乎效率低下。起初，我试着看看是否可以使用OPL.find((或其他什么东西，而不必每次都运行整个openSet，但我无法让它发挥作用。

所以我来这里是想看看一些聪明人是否有更好的解决方案，我可以使用并从中学习^^？

Answer 1

openSet应该是从currentCell到fCost的multimap。那么你的问题就简单了。

更重要的是，我不确定multi能给你带来什么——在做A*时，你通常不在乎次优路径。

您也可以在fCost字段中使用带有-INF和+INF的cells，并对它们进行下限/上限运算(假设fCost必须是有限的(，从而形成与currentCell匹配的条目范围。

下限可能更容易，然后进行线性搜索，直到你在列表的末尾，或者找到一个与你想要的匹配/不匹配的currentCell。

cells tmp = neighborCell;
tmp.fCost = -std::numeric_limits<double>::infinity();
auto it = OPL.lower_bound(tmp);
if (it == OPL.end()) return false;
return it->currentCell == tmp.currentCell;

此外，在C++的后期版本中，您可以使用所谓的"；透明比较器"；。这个人可以聪明地知道"；我只想要当前单元格"；，直接做CCD_ 11。