A* graph algorithm giving incorrect output

Question

I am writing a Graph version for A* to solve the 8 puzzle problem, I implemented a tree version tested it, and it is working fine. I did the graph version just by extending the tree version by keeping track of nodes that I visited.

Here is the original tree version:

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);

    }

}

and the graph version:

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); //<--
        }
    }
}

I added an arrow to indicate the differences between the two versions. Can anyone see what is going wrong?

Here is the test case, it is for solving the 8-puzzle:

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;

Output:

Tree solution 21
Graph solution 23

EDIT

here are the related details of the Node class:

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;
};

and here is how I overloaded the hash template:

namespace std {
    template <> struct hash<Node>
    {
        size_t operator()(const Node & t) const
        {
            return t.getHashValue();
        }
    };
}

Answer 1

I think your issue is here:

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

A* search works by maintaining a fringe of nodes and candidate distances for those nodes. The candidate distances of those nodes is not guaranteed to be accurate when the nodes are first inserted. As an example, think of a graph where there is a direct connection from the start node to the goal node with cost ∞, as well as another path that has distance 4 but passes through some other intermediary nodes. When the initial node is expanded, it will place the goal node into the priority queue with candidate distance ∞, since there's a direct edge from that node to the goal node. This is the wrong distance, but normally that's okay - later on, A* will discover the other route and lower the candidate distance of the goal from ∞ to 4 plus the heuristic.

However, the above code does not implement this correctly. Specifically, it ensures that nodes are only inserted into the priority queue once. This means that if you have an incorrect initial candidate distance, you will not update the priorities in the queue to reflect the updated candidate distance at the time that you find the better path. In the tree-based version, this isn't a problem because you will just insert a second copy of the goal node into the priority queue later on with the correct priority.

There are several ways to fix this. The simplest approach is the following - don't mark a node as visited until you've actually dequeued it from the priority queue and processed it. This means that any time you see a path to some node, you should add that node into the queue with the estimated distance. This might result in you putting multiple copies of the same node into the priority queue, which is fine - you'll get the correct distance when you dequeue it for the first time. The updated code looks like this:

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);
    }
}

The above code might have bugs depending on how the successors are implemented, but conceptually it's correct.

Hope this helps!