A *圖算法給出不正確的輸出

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

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

上面的代碼可能有錯誤取決於如何後繼的實施，但在概念上它是正確的。

希望這會有所幫助！