首页 文章

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

提问于
浏览 次
0

我已经多次问过这个问题，但我只是想了解如何将其置于上下文中 . 我试图找出如何使用广度优先搜索找到迷宫中的最短路径 . 我已经获得了一个创建迷宫的程序，我正试图找到通过它的最短路径 .

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

}

我正在试图找出将父节点连接到子节点，以便我可以将连接追溯到起始点并返回路径 .

java shortest-path breadth-first-search

1 回答

  • 1

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

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

    回复于

相关问题