我正在为A *写一个Graph版本来解决8个难题的问题，我实现了对它进行测试的树型版本，并且工作正常。我只是通过跟踪访问的节点来扩展树的版本来实现图形版本。
这是原始的树版本：
int AStarTreeVersion (Node initialState){
priority_queue<Node, vector<Node>, greater<Node> > fringe;
fringe.push(initialState);
while (true){
if (fringe.empty()) // no solution
return -1;
Node current = fringe.top();
fringe.pop();
if (current.isGoal())
return current.getDistance();
auto successors = current.getSuccessors();
for (auto s : successors)
if (s != current)
fringe.push(s);
}
}
和图形版本：
int AStarGraphVersion(Node initialState){
priority_queue<Node, vector<Node>, greater<Node> > fringe;
fringe.push(initialState);
unordered_set<Node> visited; // <---
visited.insert(initialState);// <---
while (true){
if (fringe.empty()) // no solution
return -1;
Node current = fringe.top();
fringe.pop();
if (current.isGoal())
return current.getDistance();
auto successors = current.getSuccessors();
for (auto s : successors){
auto pair = visited.insert(s); //<--
if (pair.second) //<--
fringe.push(s); //<--
}
}
}
我添加了一个箭头来指示两个版本之间的差异。谁能看到出什么问题了？
这是测试用例，用于解决8难题：
array<int, 9> a= {1, 6, 4, 8, 7, 0, 3, 2, 5};
Node ini(a);
cout<<"Tree solution "<<AStarTreeVersion(ini)<<endl;
cout<<"Graph solution "<<AStarGraphVersion(ini)<<endl;
输出：
Tree solution 21
Graph solution 23
编辑
以下是该Node课程的相关详细信息：
class Node {
public:
bool operator>(const Node& that) const
{return this->getHeuristicValue() > that.getHeuristicValue() ;}
friend inline bool operator==(const Node & lhs, const Node & rhs)
{ return lhs.board == rhs.board;}
friend inline bool operator!=(const Node & lhs, const Node & rhs)
{ return ! operator==(lhs,rhs) ;}
size_t getHashValue ()const{
size_t seed = 0;
for (auto v : board)
seed ^= v + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
private:
array<int, 9> board;
};
这是我如何重载hash模板：
namespace std {
template <> struct hash<Node>
{
size_t operator()(const Node & t) const
{
return t.getHashValue();
}
};
}
我认为您的问题在这里：
for (auto s : successors){
auto pair = visited.insert(s); //<--
if (pair.second) //<--
fringe.push(s); //<--
}
}
A *搜索通过维护节点的边缘和这些节点的候选距离来工作。首次插入节点时，不能保证这些节点的候选距离是准确的。例如，考虑一个图，其中存在一个从起始节点到目标节点的直接连接，成本为∞，以及另一条距离为4但通过其他中间节点的路径。扩展初始节点时，会将目标节点放入候选队列为∞的优先级队列中，因为从该节点到目标节点存在直接边缘。这是错误的距离，但是通常没关系-稍后，A *将发现另一条路线，并将目标的候选距离从∞降低到4加上启发式。
但是，上面的代码不能正确实现此目的。具体来说，它确保仅将节点插入一次优先级队列。这意味着，如果初始候选距离不正确，您将不会在队列中更新优先级以反映找到更好路径时的更新候选距离。在基于树的版本中，这不是问题，因为稍后您将以正确的优先级将目标节点的第二个副本插入优先级队列中。
有几种方法可以解决此问题。最简单的方法如下：在将节点从优先级队列中真正出队并进行处理之前，不要将其标记为已访问。这意味着，每当看到到某个节点的路径时，都应以估计的距离将该节点添加到队列中。这可能会导致您将同一节点的多个副本放入优先级队列，这很好-您第一次出队时会获得正确的距离。更新后的代码如下所示：
priority_queue<Node, vector<Node>, greater<Node> > fringe;
fringe.push(initialState);
unordered_set<Node> visited;
while (true){
if (fringe.empty()) // no solution
return -1;
Node current = fringe.top();
fringe.pop();
/* Mark the node as visited and don't visit it again if you already saw it. */
if (visited.insert(current).second == false) continue;
if (current.isGoal())
return current.getDistance();
auto successors = current.getSuccessors();
/* Add successors to the priority queue. This might introduce duplicate nodes,
* but that's fine. All but the lowest-priority will be ignored.
*/
for (auto s : successors){
fringe.push(s);
}
}
上面的代码可能有错误，具体取决于后续程序的实现方式，但从概念上讲是正确的。
希望这可以帮助！
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句