我第一次尝试在c++中编写A*搜索,但我以前在Java中编写过它们。
我在检查是否已经在openList中有问题。OpenList是Node的priority_queue,但我知道你不能简单地遍历一个优先级队列。
我的想法是,我将openList传递给一个函数,该函数将元素复制到临时向量中,然后我可以迭代这个临时向量。这显然不利于快速高效的运行,但我想不出其他解决办法。
闭链表非常简单,你可以看到只是遍历vector。
这是两个列表:
priority_queue<Node, vector<Node>, NodeCompare> openList;
vector<Node> closedList;
代码:bool checkInClosedList(std::vector<Node>& v,int x, int y){
for (std::vector<Node>::iterator iter = v.begin(); iter != v.end(); ++iter) {
if(iter->getX() == x && iter->getY() == y){
return true;
}
}
return false;
}
我怎么能做到以上,但对于一个priority_queue <Node, vector<Node>, NodeCompare>
?
优先级队列本身工作得很好,我已经测试过了,但我的A*陷入无限循环,因为它一直在检查它已经检查过的节点!
欢呼,克里斯。
底层数据容器是类的受保护成员std::priority_queue
,因此您可以在派生类中访问它。如果要添加前置或后置条件或不变量,请使用是正确的解决方案;你派生你自己的类强制不变量。
您可以使用std::list并对其调用unique()。此外,std::list允许您基于谓词进行排序,这将允许您模拟priority_queue正在进行的任何排序。
或者,std::map强制唯一键,并将删除重复键。