java - 如何使用广度优先搜索找到迷宫中的最短路径？

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

广度优先搜索可能不是查找最短路径 ( See Dijkstra's shortest path algorithm ) 的最有效方法。但如果您坚持，我想您会想要为每种可能的路径配置创建一个列表，然后选择最短的一个。

当然，这将是很多路径!你能做的就是基于 bfs 实现你自己的 Dijkstra 算法(实际上，它一开始就是基于 bfs 的)。这大致需要创建您自己的点类并添加一个名为 next 的字段，该字段指向您的下一个点，并且每次访问未探索的点时，您都​​会更新到该点的最短路径。详情请访问wiki或search it up on Youtube (维基百科有时很难理解，但是那里的伪代码非常有用；)!