0

在过去的几个小时里，我一直被这个棘手的错误所困扰，我想知道这里是否有人可以帮助我。

基本上我通过递归实现 A*，并且我希望每个节点（在代码中称为 tile）存储一个整数值，该整数值表示它通过的先前节点的数量。这样一来，一旦算法找到出口，它就可以返回并返回最短的路线。

但是，每次循环通过该功能时都会重置轮数计数器。但是，如果我删除该行：

map[y][x].setID(path);

它计算得很好，但当然会产生堆栈溢出错误，但我真的不明白为什么这会导致问题。

代码的主要部分在这里：

private static Tile[][] findSquares(IntVector v, Tile[][] map, int wall, int empty, int end, int start, int path, int turns)
{
    // System.out.println(turns);
    if (!isHit)
    {
        for (int y = v.y - 1; y <= v.y + 1; y++)
        {
            for (int x = v.x - 1; x <= v.x + 1; x++)
            {
                if (map[y][x].id == end)
                {
                    isHit = true;
                }
                else if (map[y][x].id != wall && map[y][x].id != path && map[y][x].id != end && !isHit && map[y][x].id != start)
                {
                    map[y][x].turns++;
                    System.out.println(map[y][x].turns); //Always Results in 1

                    map[y][x].setID(path);
                    findSquares(new IntVector(x, y), map, wall, empty, end, start, path, turns);
                    break;
                }
            }
        }
    }
    return map;
}

瓦片代表一个节点。这是瓷砖类：

static private class Tile
{
    int id;
    int turns = 0;

    Tile(int id)
    {
        this.id = id;
    }

    public void addTurn()
    {
        turns++;
    }

    public void setID(int id)
    {
        this.id = id;
    }

    public int getTurns()
    {
        return turns;
    }

    public Tile setTurns(int turns)
    {
        this.turns = turns;
        return this;
    }
}

也许这与 tile 类是静态的有关？

4

1 回答 1

0

问题不在于轮数计数器正在“重置”，而在于您永远不会多次增加它。递增的分支turns仅在 时发生id != path，但您随后立即设置id为，因此它永远不会再次递增。path

你可能想要的是 map[y][x].turns = map[v.y][v.x].turns + 1;

无论如何，即使你修正了距离计算，你的代码也几乎不像 A*。看起来您的代码实际上在做的是深度优先搜索，您的搜索堆栈隐式维护在程序调用堆栈上。

A* 算法涉及维护要搜索的节点的优先级队列，并使用启发式函数加上当前距离来计算插入节点的新优先级。

于 2013-04-07T19:21:10.947 回答