给出不正确输出的*图算法

Question

我正在为A*编写一个图形版本，以解决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();
        }
    };
}

Answer 1

我想你的问题是：

for (auto s : successors){
   auto pair = visited.insert(s); //<--
   if (pair.second) //<--
       fringe.push(s); //<--
   }
}

*搜索是通过维护这些节点的节点边缘和候选距离来完成的。当第一次插入这些节点时，并不保证这些节点的候选距离是准确的。例如，想象一个图，其中有一个从开始节点到目标节点与成本∞的直接连接，以及另一条距离为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);
    }
}

根据后续程序的实现方式，上面的代码可能有错误，但在概念上是正确的。

希望这能有所帮助！