在 C++ 中用 A* 解决 8-Puzzle 会导致死循环

Question

我目前正在尝试使用 A* 搜索算法解决 8 谜题，但我的程序陷入了无限循环。

我的主要搜索循环是：

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

向量"searched"只是为了让我看看A*做了什么，一旦算法生效我会立即删除它。

CostG 代表到目前为止完成的步骤数，CostH 是 "goal" 的估计最小（启发式）成本，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 的更改，link 是相同的。

Answer 1

问题在于，虽然您从边界中删除了 current 节点，但您从未将其添加到 explored 集合中，即您从未关闭它。以下代码应该有效。我的修改紧跟 Wikipedia's A* Pseudocode.

我还建议您在一个简单的谜题上使用简单的启发式算法（returns 所有值都为零的算法）测试您的算法，以验证您的算法是否正确实施。（有关此技术的简要说明，请参阅 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]);

    }
}

在 C++ 中用 A* 解决 8-Puzzle 会导致死循环

Solving 8-Puzzle in C++ with A* results in endless loop

c++

algorithm

a-star