如何使用广度优先搜索在迷宫中找到最短路径

Question

我意识到这个问题已经被问了好几次，但我只是想了解如何将其置于上下文中。我正在尝试弄清楚如何使用广度优先搜索在迷宫中找到最短路径。我得到了一个创建迷宫的程序，我试图找到通过它的最短路径。

package solver;
import java.awt.Point;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class BreadthFirstSearch extends AbstractSolver {  
    @Override
    public List<Point> solve(int[][] maze, Point start, Point goal) {
        LinkedList<Point> path = new LinkedList<Point>();
        List<Point> prevPoints = new LinkedList<Point>();
        Queue<Point> agenda = new LinkedList<Point>();
        List<Point> visited = new LinkedList<Point>();
        agenda.add(start);
        visited.add(start);
        while(!agenda.isEmpty()) {
            Point current = agenda.remove();
            for(Point neighbour : getNeighbours(current, maze)) {
                if(!visited.contains(neighbour)) {
                    visited.add(neighbour);
                    agenda.add(neighbour);
                }
            }
        }
        return null;
    }
}

我试图弄清楚将父节点连接到子节点，以便我可以将连接追溯到起点并返回路径。

Answer 1

广度优先搜索可能不是查找最短路径的最有效方法（参见 Dijkstra 的最短路径算法）。但是如果你坚持，我想你会想为每个可能的路径配置创建一个列表，然后选择最短的路径。

当然，这将是很多路径！你可以做的是基于bfs实现你自己的Dijkstra算法（实际上，它一开始是基于bfs的）。这大致需要创建您自己的点类并添加一个名为 next 的字段，该字段指向您的下一个点，以及每次您访问未探索的点时，您都会更新到该点的最短路径。有关详细信息，只需访问wiki或在Youtube上搜索（维基百科有时可能很难理解，但那里的伪代码非常有用;)！