探讨 Java 深搜算法的学习笔记

2024-11-01
北京
本文字数：3094 字
阅读完需：约 10 分钟

大家好，我是 V 哥。深度优先搜索（DFS）是一种图遍历算法，它优先深入到某条路径的尽头，再回溯到前一个节点继续探索其他路径，直到找到目标或遍历完整个图。DFS 的应用场景广泛，可以用于路径搜索、连通性判断、迷宫求解等。以下是一个典型的 DFS 实现示例以及分析它在不同业务场景中的应用。

1. 先来看一个案例

以下为一个 Java 实现的 DFS 算法示例，用于在一个二维矩阵中寻找从起点到终点的路径。该矩阵中 1 表示可以通过的点，0 表示障碍物。目标是找到从起点（0,0）到终点（m-1,n-1）的路径。

public class DFSMazeSolver {    private static final int[] DX = {-1, 1, 0, 0}; // 行移动方向：上，下    private static final int[] DY = {0, 0, -1, 1}; // 列移动方向：左，右
    public boolean dfs(int[][] maze, int x, int y, boolean[][] visited) {        int rows = maze.length;        int cols = maze[0].length;
        // 边界条件与目标判断        if (x < 0 || y < 0 || x >= rows || y >= cols || maze[x][y] == 0 || visited[x][y]) {            return false;        }
        // 到达终点        if (x == rows - 1 && y == cols - 1) {            return true;        }
        // 标记当前位置已访问        visited[x][y] = true;
        // 递归地探索四个方向        for (int i = 0; i < 4; i++) {            int newX = x + DX[i];            int newY = y + DY[i];            if (dfs(maze, newX, newY, visited)) {                return true;            }        }
        // 回溯        visited[x][y] = false;        return false;    }
    public boolean canSolveMaze(int[][] maze) {        int rows = maze.length;        int cols = maze[0].length;        boolean[][] visited = new boolean[rows][cols];        return dfs(maze, 0, 0, visited);    }
    public static void main(String[] args) {        int[][] maze = {                {1, 0, 0, 0},                {1, 1, 0, 1},                {0, 1, 0, 0},                {1, 1, 1, 1}        };
        DFSMazeSolver solver = new DFSMazeSolver();        if (solver.canSolveMaze(maze)) {            System.out.println("路径可达");        } else {            System.out.println("无可行路径");        }    }}

复制代码

代码说明

DFS 主逻辑：dfs方法用于在当前位置（x，y）开始深度优先搜索。
边界条件：包括是否越界、是否遇到障碍物以及是否已经访问。
终点判断：当到达矩阵右下角终点（rows-1，cols-1）时，返回true。
回溯处理：在搜索过程中，为了避免重复访问，将访问过的位置标记为已访问，若搜索失败则回溯重置。

2. 业务场景分析

迷宫或地图导航：DFS 可用于迷宫或地图路径导航，寻找从起点到终点的路径。在实际应用中，可以在机器人路径规划、无人机飞行路径规划中使用类似的 DFS 算法。
权限和连通性检测：在网络安全中，DFS 可以用于检测用户权限或系统连通性，例如检测某用户在权限网络中的访问路径，确保系统关键资源安全。
社交网络分析：在社交网络中，DFS 可以用于分析用户关系连通性，例如寻找两个人之间的关系链路、推荐相似好友。
数据爬取：DFS 算法也可用于数据爬取，从起始页面开始深度爬取相关页面信息。

在机器人路径规划和无人机飞行路径规划中，DFS 算法可以用来寻找从起点到目标点的可行路径。DFS 适合在地图较小且需要找到任意一条可行路径的场景。以下是一个在网格地图上实现 DFS 的完整 Java 代码示例，模拟机器人或无人机在二维平面上寻找从起点到目标点的路径。

如何实现无人机飞行路径规划

假设网格中的 0 表示障碍物，1 表示可通行区域。目标是从起点（0, 0）到终点（m-1, n-1）找到一条通路。

import java.util.ArrayList;import java.util.List;
public class RobotPathPlanner {    // 定义四个方向：上，下，左，右    private static final int[] DX = {-1, 1, 0, 0};    private static final int[] DY = {0, 0, -1, 1};    private static final String[] DIRECTION = {"Up", "Down", "Left", "Right"};
    // 存储路径    private List<String> path = new ArrayList<>();
    // 深度优先搜索算法    public boolean dfs(int[][] grid, int x, int y, boolean[][] visited) {        int rows = grid.length;        int cols = grid[0].length;
        // 边界条件：检查是否越界，是否遇到障碍物，是否已访问        if (x < 0 || y < 0 || x >= rows || y >= cols || grid[x][y] == 0 || visited[x][y]) {            return false;        }
        // 如果到达终点位置，路径规划成功        if (x == rows - 1 && y == cols - 1) {            path.add("(" + x + "," + y + ")");            return true;        }
        // 标记当前节点为已访问        visited[x][y] = true;        path.add("(" + x + "," + y + ")");
        // 遍历四个方向进行递归搜索        for (int i = 0; i < 4; i++) {            int newX = x + DX[i];            int newY = y + DY[i];            if (dfs(grid, newX, newY, visited)) {                path.add(DIRECTION[i]);                return true;            }        }
        // 回溯：撤销当前路径点的访问        path.remove(path.size() - 1);        visited[x][y] = false;        return false;    }
    public List<String> findPath(int[][] grid) {        int rows = grid.length;        int cols = grid[0].length;        boolean[][] visited = new boolean[rows][cols];
        if (dfs(grid, 0, 0, visited)) {            return path;        } else {            path.add("No Path Found");            return path;        }    }
    public static void main(String[] args) {        int[][] grid = {                {1, 0, 0, 0},                {1, 1, 0, 1},                {0, 1, 1, 0},                {1, 0, 1, 1}        };
        RobotPathPlanner planner = new RobotPathPlanner();        List<String> path = planner.findPath(grid);
        System.out.println("规划路径：");        for (String step : path) {            System.out.println(step);        }    }}

复制代码

来解释一下代码

方向定义：DX和DY分别代表在网格上移动的方向数组，DIRECTION数组用于记录方向名称，便于输出路径。
DFS 递归搜索：dfs方法从指定位置(x, y)开始搜索，检查越界、障碍物和访问状态。
终点判断：到达终点时返回true，并将路径记录到path列表。
回溯：如果当前路径无效，则回溯并撤销该路径点的访问状态。
路径输出：主函数findPath调用dfs，并根据 DFS 结果返回路径或“未找到路径”的提示。

机器人路径规划：在仓储物流中，机器人需要规划从起点到指定位置的路径，避开障碍物（如货架），通过 DFS 可以找到一条可行的路径。

无人机飞行路径规划：在室内或复杂地形中，无人机可以通过 DFS 找到安全飞行路线，避开障碍物，确保抵达目的地。DFS 适用于场地相对较小且只需找到一条路径的场景。

3. 最后的注意事项

性能：在较大区域或复杂地形中，DFS 可能导致大量回溯。可以用 A*或 Dijkstra 等启发式算法优化。
障碍动态性：如果障碍物可能移动，可以定期重新规划路径。

关注威哥爱编程，编码路上 V 哥陪你不寂寞。

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/8e35460d9b81c5efee881beb7】。文章转载请联系作者。

威哥爱编程

关注

华为 HDE、CSDN 博客专家、Java畅销书作者 2018-05-30 加入

全栈领域优质创作者（Java/HarmonyOS/AI），公众号：威哥爱编程

发布

暂无评论

创作场景