0

私は過去数時間、このトリッキーなバグに悩まされていました。

基本的に、私は再帰によって A* を実装しており、各ノード (コードではタイルと呼ばれます) に、それが通過した以前のノード数の整数値を格納したいと考えています。これは、アルゴリズムが出口を見つけたら、元に戻って最短ルートを返すことができるようにするためです。

ただし、ターン カウンターは関数をループするたびにリセットされます。ただし、次の行を削除すると:

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

おそらく、タイルクラスが静的であることと関係がありますか?

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 に答える