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

我意识到这个问题已被问了好几次，但我只是想了解如何把它放到上下文中。我试图找出如何使用广度优先搜索在迷宫中找到最短路径。我得到了一个创建迷宫的程序，我试图找到通过它的最短路径。如何使用广度优先搜索在迷宫中找到最短路径？

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

}

我试图找出客场父节点连接到孩子，所以我可以跟踪连接返回到起点和返回的路径。

来源

2015-04-17 user2001375

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

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

来源

2015-04-17 23:51:48

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

回答

相关问题