Java-Maze广度优先搜索最短路径-Java 学习之路

我似乎在理解如何检索我正在实现的广度优先搜索算法发现的最短路径时遇到问题 . 目前，算法可以正常工作，因为它可以找到迷宫的出口，如果它可以到达它 . 在另一篇文章中，有人提到在节点被标记为已访问后保持对父进程的攻击 . 我尝试了一个简单的实现，试图通过在Point结构中包含一个父Point来跟踪父项，但是当我在Grid上标记路径时它标记了它迄今为止已经过去的所有路径，我相信我可能搞砸了以某种方式跟踪父母 .

任何人都知道我哪里出错了 . 也许我错过了一些简单的东西？该守则包含在下面作为参考 .

迷宫是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;
}

1 回答

1
看起来 old 在多次迭代后不再是父级 . 您可以在将该点添加到队列时设置父级，例如：
```
Point next = new Point(Cur.getX()-1,Cur.getY());
next.setParent(Cur);
Path.enqueue(next);
```
然后，当您找到结束时，您应该能够通过调用getParent（）将路径返回到开头，直到它为 null .
回复于 2024-05-05T15:08:48+08:00

Java-Maze广度优先搜索最短路径

1 回答

相关问题