最近在写一个机器人寻路的算法,感觉蛮有趣的来分享给大家.
题目是这样的, 在一个矩阵内(二维数组)内, 机器人位于某一个起点,寻找迷宫的出口. 机器人可以上下左右移动(且不能越界). 并且机器人不能越过墙壁.
用数组可以表示为下面的样式:
0 是可以移动的路径, 3 是我们假设的终点. 1 则是墙壁
假设机器人位于0,0. 那么机器人可以向右,下移动. 假设机器人位于0,1 那么机器人可以向下移动或者向左移动.
那么怎么能让机器人找到迷宫的出口呢?
这里有两种搜索策略,第一种是uninformed 搜索, 另一种叫做informed 或者启发式搜索.
今天我们简单的介绍下 uninformed搜索中的 BFS(Breadth-first search)搜索算法.
这里有一棵树, 比如说机器人现在处于1号节点. 它可以发现并且移动的节点是 2 , 3 , 4. 那么机器人怎么决定下一个移动顺序呢?
当然 你可以选择从 2 开始 或者从 4 开始. 这并不影响你使用BFS算法.
我们假设你是从2 开始. 那么在bfs中, 2 的下一个搜索的节点将是3, 然后是4 . 这也就是广度优先算法的由来.
在第二层节点搜索完之后呢. 由于是从左边的二开始,那么我们需要遍历2的子节点也就是 5 和 6 . 之后 检查3 是否存在子节点. 发现并不存在.
然后去查看4是否存在子节点. 毫无疑问4是存在子节点的 然后我们就继续遍历7 和 8
在第三层遍历完了之后就该第四层了 分别是9, 10 , 11 ,12 .
于是这个BFS算法就算完成了.
这里还存在一个算法的效率问题. 实际上比如说现在你处于2 号节点. 那么你可以选择移动的节点还有1号节点. 因此如果你的程序不判断当前的节点是否已经被访问过的话,那么可能会出现重复被访问的情况. 也有可能找不到出口.
我们来看下代码怎么实现
定义了一个数组来确定当前机器人的移动方向, 数组的index 0 也就是 0,1(Y+1) 那么就是向右移动. 0 ,- 1 (y-1) -1,0 (x-1) 向左. 1,0(x+1 向右)
首先,定义了一个机器人的起点,然后定义了一个要寻找的目标节点数组. 为了提升算法的效率我们不访问已经被访问过的节点. 所以定义了一个已经被访问过的节点数组
之后我们便可以对目标节点进行BFS搜索.
因为当前的节点存在着多个子节点,那么子节点的访问顺序我们可以使用一个队列来维护.
先将当前的节点加到队列中来执行算法相关,
标记当前的节点已经被访问过来避免被二次访问
A: 如果当前的节点中的队列不为空的话,那么执行poll出队列操作,拿到队列中的第一个元素.
B:并且将第一个元素加到被访问过的路径中
C:判断当前的元素是否等于目标节点, 如果等于目标节点则返回结果
D:如果不等于目标节点的话,那么判断当前目标的子节点 按照 上下左右的顺序进行判断(.我这里题目有要求必须右上左右,实际上可以自定义)
E:然后将当前节点可被访问子节点加入到当前的队列中
重复执行 A
BFS的算法输出结果
代码如下:
- public static void main(String[] args) {
- int startX = 0, startY = 1;
- List<int[]> goals = new ArrayList<>();
- //添加目标节点
- goals.add(new int[]{3, 7});
- goals.add(new int[]{2, 3});
- //已经访问过的节点
- boolean[][] visited = new boolean[numRows][numCols];
- //所有的节点
- List<int[]> path = new ArrayList<>();
- //对目标节点进行搜索
- for (int[] goal : goals) {
- int goalX = goal[0];
- int goalY = goal[1];
- //起点 X 起点Y. 访问过的节点. 访问路径 目标节 点
- if (bfs(startX, startY, visited, path, goalX, goalY)) {
- System.out.println("Robot can reach the goal at (" + goalX + ", " + goalY + ").");
- System.out.println("Path:");
- for (int[] point : path) {
- System.out.println("(" + point[0] + ", " + point[1] + ")");
- }
- //清空当前的路径
- path.clear();
- } else {
- System.out.println("Robot cannot reach the goal at (" + goalX + ", " + goalY + ").");
- }
- //清空当前已经访问过的节点
- visited = new boolean[numRows][numCols];
- }
- }
- }
- private static boolean bfs(int x, int y, boolean[][] visited, List<int[]> path, int goalX, int goalY) {
- Queue<int[]> queue = new LinkedList<>();
- // 将起始点加入队列
- queue.offer(new int[]{x, y});
- visited[x][y] = true;
- while (!queue.isEmpty()) {
- //获取当前节点
- int[] current = queue.poll();
- int currX = current[0];
- int currY = current[1];
- // 将当前节点加入到路径
- path.add(new int[]{currX, currY});
- //如果当前节点等于目标节点
- if (currX == goalX && currY == goalY) {
- return true;
- }
- for (int[] dir : directions) {
- int nextX = currX + dir[0];
- int nextY = currY + dir[1];
- //判断数组是否越界和当前节点是否被访问过
- if (nextX >= 0 && nextX < numRows && nextY >= 0 && nextY < numCols && grid[nextX][nextY] != 1 && !visited[nextX][nextY]) {
- //记录当前节点的子节点
- queue.offer(new int[]{nextX, nextY});
- //当前节点标记为True
- visited[nextX][nextY] = true;
- }
- }
- }
- path.clear(); // Clear the path if goal not found
- return false;
- }
- //假设存在的数据
- private static final int[][] grid = {
- {0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1},
- {0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
- {0, 0, 1, 0, 0, 0, 0, 0, 3, 1, 0},
- {0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0}
- };
- // 右 上 左 下
- public static final int[][] directions = {{0, 1},{0, -1},{-1, 0}, {1, 0}};
- private static final int numRows = grid.length;
- private static final int numCols = grid[0].length;
|
