3

私が実装している幅優先探索アルゴリズムによって発見された最短パスを取得する方法を理解するのに問題があるようです。現在、アルゴリズムは、迷路に到達できれば、迷路の出口を見つけることができるように機能します。別の投稿で、ノードが訪問済みとしてマークされた後、親の追跡を維持することに誰かが言及しました。Point 構造内に親 Point を含めることで親を追跡しようとする簡単な実装を試みましたが、グリッド上のパスをマークすると、これまでに通過したすべてのパスがマークされます。どういうわけか親の追跡。

私がどこで間違ったのか、誰もが手がかりを持っています。多分私は単純なものを見逃していますか？コードは参考として以下に含まれています。

迷路は 2D 整数グリッドです。1 を壁、0 を可動パスとします。

Point クラスには以下が含まれます。 Point Parent int x, y; そしてそれ以上のものはありません。

public Point BFS(int x, int y){
    Queue<Point> Path = new Queue<>();

    Path.enqueue(new Point(x,y));//push current on queue

    Point Cur = Path.front();//make current point
    //test code for recursive backcall of path
        Cur.setParent(null);
    //test code for recursive backcall of path


    Point end = new Point(mWidth-2, mHeight-2);//set goal

    while((!Path.isEmpty())){
        Point old = Cur;

        Cur = Path.dequeue();
        Cur.setParent(old);

        if(Cur.compareto(end)){
            return Cur;//return Point then traverse up from here calling Cur.Parent to get path.
        }
        else if(Maze[Cur.getX()][Cur.getY()]==1){//Enque all possible paths

            Maze[Cur.getX()][Cur.getY()] = 2;//mark as visitied
            if(Cur.getX()-1>=0)
                if(Maze[Cur.getX()-1][Cur.getY()]==1)
                    Path.enqueue(new Point(Cur.getX()-1,Cur.getY()));

            if(Cur.getX()+1<mWidth)
                if(Maze[Cur.getX()+1][Cur.getY()]==1)
                    Path.enqueue(new Point(Cur.getX()+1,Cur.getY()));

            if(Cur.getY()-1>=0)
                if(Maze[Cur.getX()][Cur.getY()-1]==1)
                    Path.enqueue(new Point(Cur.getX(),Cur.getY()-1));

            if(Cur.getY()+1<mHeight)
                if(Maze[Cur.getX()][Cur.getY()+1]==1)
                    Path.enqueue(new Point(Cur.getX(),Cur.getY()+1));
        }

    }
    return null;
}
4

1 に答える 1

1

old複数回繰り返した後、親ではなくなったようです。代わりに、ポイントをキューに追加するときに親を設定できます。次に例を示します。

Point next = new Point(Cur.getX()-1,Cur.getY());
next.setParent(Cur);
Path.enqueue(next);

次に、終わりを見つけたら、 getParent() を呼び出すことで、パスを最初に戻すことができるはずですnull。

于 2013-05-21T21:42:57.223 に答える