如何使用廣度優先搜索在迷宮中找到最短路徑？

我意識到這個問題已被問了好幾次，但我只是想了解如何把它放到上下文中。我試圖找出如何使用廣度優先搜索在迷宮中找到最短路徑。我得到了一個創建迷宮的程序，我試圖找到通過它的最短路徑。如何使用廣度優先搜索在迷宮中找到最短路徑？

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

如何使用廣度優先搜索在迷宮中找到最短路徑？

回答

相關問題