广度优先搜索

问题背景迷宫问题是一个经典的算法问题，指标是找到从迷宫的终点到起点的最短门路，在程序中能够简略的形象成一个M*N的二维数组矩阵，而后咱们须要从这个二维矩阵中找到从终点到起点的最短门路。其中，通常应用 0 示意可行走的路，用 1 示意障碍物，终点和起点别离标记为 S 和 E。例如，下图是一个简略的迷宫问题： 0 0 0 0 0 00 1 0 1 1 00 1 0 0 0 00 0 1 1 0 00 1 0 1 0 0S 0 0 0 E 0在这个迷宫中，数字 0 示意可行走的路，数字 1 示意障碍物，S 示意终点，E 示意起点。 利用场景迷宫问题在现实生活中有很多理论利用例子： 机器人导航：在机器人导航中，机器人须要依据传感器获取的信息来布局门路，从终点到起点。这个过程能够应用迷宫问题的算法来实现，如应用 A* 算法来找到最短门路。游戏设计：迷宫问题能够利用于各种类型的游戏中，如谜题解决游戏和角色扮演游戏。在这些游戏中，玩家须要找到一条从终点到起点的门路，同时防止遇到障碍物或危险。主动驾驶：在主动驾驶汽车中，汽车须要遵循交通规则、防止障碍物并找到最短门路。这也能够应用迷宫问题的算法来实现，如应用 A* 算法来找到最短门路。网络路由：网络路由器须要在各种网络拓扑中寻找最佳门路，以确保数据包在网络中传输时尽可能疾速和牢靠。这也能够应用迷宫问题的算法来实现，如应用 A* 算法来找到最短门路。地图利用：在地图利用中，用户须要依据终点和起点寻找最佳门路。这能够应用迷宫问题的算法来实现，如应用 A* 算法来找到最短门路。罕用算法求解迷宫问题的算法有多种，其中最常见的是深度优先搜寻（DFS）算法、广度优先搜寻（BFS）算法和A*搜索算法。本文将别离介绍这两种算法的实现形式及其优缺点。 深度优先搜寻（DFS）算法深度优先搜寻（DFS）是一种基于栈或递归的搜索算法，从终点开始，一直地往深处遍历，直到找到起点或无奈持续往下搜寻。在迷宫问题中，DFS 会先选取一个方向往前走，直到无奈后退为止，而后返回上一个节点，尝试其余方向。 DFS 的核心思想是回溯，即在走到绝路时，返回上一个节点，从而摸索其余方向。具体实现上，能够应用递归函数或栈来保护待拜访的节点。 import java.util.*;public class MazeSolver { // 迷宫的行数和列数 static final int ROW = 5; static final int COL = 5; // 迷宫的地图，0 示意能够通过的路，1 示意墙壁，2 示意曾经走过的路 static int[][] map = new int[][]{ {0, 1, 1, 1, 1}, {0, 0, 0, 1, 1}, {1, 1, 0, 0, 1}, {1, 1, 1, 0, 1}, {1, 1, 1, 0, 0} }; // 迷宫的终点和起点 static final int startX = 0; static final int startY = 0; static final int endX = 4; static final int endY = 4; // 存储搜寻门路 static List<int[]> path = new ArrayList<>(); // DFS 搜寻迷宫 public static void dfs(int x, int y) { // 如果以后地位是起点，则搜寻实现 if (x == endX && y == endY) { // 打印搜寻门路 for (int[] p : path) { System.out.print("(" + p[0] + "," + p[1] + ") "); } System.out.println("(" + x + "," + y + ")"); return; } // 标记以后地位曾经走过 map[x][y] = 2; // 将以后地位退出搜寻门路 path.add(new int[]{x, y}); // 别离搜寻以后地位的上下左右四个方向 if (x > 0 && map[x-1][y] == 0) { dfs(x-1, y); } if (y > 0 && map[x][y-1] == 0) { dfs(x, y-1); } if (x < ROW-1 && map[x+1][y] == 0) { dfs(x+1, y); } if (y < COL-1 && map[x][y+1] == 0) { dfs(x, y+1); } // 如果没有找到起点，将以后地位从搜寻门路中移除 path.remove(path.size()-1); } public static void main(String[] args) { dfs(startX, startY); }}深度优先搜寻（DFS）的长处： ...