在C++中解決C++中的8難題*導致無限循環

Question

我目前試圖用A *搜索算法解決8-Puzzle，但是我的程序陷入了無限循環。

我的主要搜索循環是：

std::vector<Field> Search::AStar(Field &start, Field &goal){ 
std::cout << "Calculating..." << std::endl; 

std::unordered_map<Field, Field> explored; 
std::vector<Field> searched; 

if (Puzzle::finished(start)) 
    return MakePath(start, start); 

std::priority_queue<Field, std::vector<Field>, std::greater<Field>> frontier; 
frontier.push(start); 

Field current; 
Field child; 

size_t i = 0; 
while (!frontier.empty()) 
{ 
    current = frontier.top(); 
    frontier.pop(); 

    if (++i > 500) 
    { 
     std::cout << "Iteration Error" << std::endl; 
     return searched; 
    } 

    searched.push_back(current); 

    for (Direction d : Puzzle::Actions(current)) 
    { 
     child = Puzzle::Action(d, current); 

     if (Puzzle::finished(child)) 
     { 
      std::cout << "Found goal!" << std::endl; 
      return MakePath(explored[child], start); 
     } 

     child.CostG = current.CostG + 1; // Make a step 

     if (!isIn(child, explored) || child.CostG < explored[child].CostG) 
     { 
      child.CostH = Puzzle::Heuristic(child, goal); // Calculate Heuristic 
      child.CostF = child.CostG + child.CostH; // Calculate final costs 

      frontier.push(child); 
      explored[child] = child; 
      explored[child].setParent(&explored[current]); 
     } 
    } 
} 

std::cout << "Error: frontier Empty" << std::endl; 

return searched; 
} 

矢量「搜索」只是，這樣我可以看到*做什麼A，我會盡快刪除它的算法的工作。

CostG表示直到此時爲止完成的步驟數量，CostH是「目標」的估計最小值（啓發式）成本，CostF是這兩者的總和。

Field :: Boxes向量的索引是字段的編號，每個元素都包含位置。

我的啓發式功能如下：

inline int Heuristic(Field &goal) 
{ 
    size_t d = 0; 

    for (size_t i = 0; i < Boxes.size(); i++) 
    { 
     d += (std::abs(static_cast<int>(Boxes[i].x) - static_cast<int>(goal.Boxes[i].x)) 
      + std::abs(static_cast<int>(Boxes[i].y) - static_cast<int>(goal.Boxes[i].y))); 
    } 

    return d; 
} 

爲了更好的可讀性和東西，代碼也就是上Github。但是，要執行它，您需要在Visual Studio包含方向中使用SFML。

感謝您的幫助！

編輯1： 您現在不再需要SFML來執行&調試程序！我對github進行了更改，鏈接相同。

Answer 1

問題是，儘管您從邊界刪除了current節點，但您從未將其添加到explored集合，即您永遠不會關閉它。以下代碼應該工作。我的修訂嚴格遵循。

我還建議你用簡單的啓發式（對所有值返回零的那個）在簡單的謎題上測試你的算法，以驗證你的算法是否正確實現。 （請參閱this answer瞭解此技術的簡要說明。）

while (!frontier.empty()) 
{ 
    current = frontier.top(); 
    frontier.pop(); 

    if (++i > 500) 
    { 
     std::cout << "Iteration Error" << std::endl; 
     return searched; 
    } 

    // Check for goal here 
    if (Puzzle::finished(current) 
    { 
     std::cout << "Found goal!" << std::endl; 
     return MakePath(explored[current], start); 
    } 

    explored[current] = current; //close the current node 
    searched.push_back(current); 

    for (Direction d : Puzzle::Actions(current)) 
    { 
     child = Puzzle::Action(d, current); 

     if (isIn(child,explored)) 
     { 
      continue; //ignore the neighbor which is already evaluated 
     } 

     child.CostG = current.CostG + 1; // Make a step 

     if (!isIn(child, frontier)) //discovered a new node 
     { 
      frontier.push(child); 
     } 
     else if (child.CostG >= explored[child].CostG) 
     { 
      continue; //this is not a better path 
     { 

     //the path is best until now. Record it! 
     child.CostH = Puzzle::Heuristic(child, goal); // Calculate Heuristic 
     child.CostF = child.CostG + child.CostH; // Calculate final costs 

     //frontier.push(child); moved up to earlier point in code 
     explored[child] = child; 
     explored[child].setParent(&explored[current]); 

    } 
}