Skip to content

Latest commit

 

History

History
230 lines (148 loc) · 11.8 KB

搜索算法.md

File metadata and controls

230 lines (148 loc) · 11.8 KB

搜索算法

0. 概念

搜索算法主要是 深度优先搜索 和 广度优先搜索：

深度优先搜索 算法（英文：Depth-First-Search，DFS）是一种用于 遍历或搜索树或图 的算法。这个算法会 尽可能深 的搜索树的分支。当结点 v 的所在边都己被探寻过，搜索将 回溯 到发现结点 v 的那条边的起始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被访问为止。

回溯经常使用 DFS 实现，两者之间有着千丝万缕的联系，具体可以看看 回溯算法

广度优先搜索 算法（英语：Breadth-First Search，缩写为BFS），又叫宽度优先搜索，或横向优先搜索，是一种图形搜索演算法。简单的说，BFS 是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。

1. DFS 和 BFS 模板

在 二叉树路径问题 那篇文章已经给出了典型的 DFS/BFS 模板，不过那个主要是针对二叉树的，这里我们主要关注 网格问题 或者 岛屿问题，典型题目就是 200. 岛屿数量

1.1 DFS

DFS 一般使用递归实现，二叉树的 DFS 有两个要素：

① 访问相邻节点：二叉树的相邻节点就是左右子节点，递归左右子树即可

② 判断 base case：二叉树的 base case 一般是root == nullptr

网格的 DFS 问题可以参照二叉树的 DFS 总结如下要素：

① 访问相邻格子：网格的“相邻节点”就是上下左右四个格子，可以理解为“四叉树”

② 判断 base case：类似二叉树，网络 base case 就是判断格子是否越界

🔥要知道一次 DFS 只是标记当前节点以及相邻同类的节点，所以如果要统计连通块的个数还需要一个二层循环枚举所有不同的节点值

// 网格 DFS 模板
void dfs(vector<vector<int>>& grid, int r, int c) {
    // 判断 base case
    // 如果坐标 (r, c) 超出了网格范围，直接返回
    if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size()) {
        return;
    }
    
    // 如果格子不是不是“陆地”直接返回
    if (grid[r][c] != 1) {
        return;
    }
    
    // 标记已经遍历过的“陆地格子”
    grid[r][c] = 2;
    
    // 访问上、下、左、右四个相邻结点
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

在一些题解中，可能会把「已遍历过的陆地格子」标记为和海洋格子一样的 0，美其名曰「陆地沉没方法」，即遍历完一个陆地格子就让陆地「沉没」为海洋。这种方法看似很巧妙，但实际上有很大隐患，因为这样我们就**无法区分「海洋格子」和「已遍历过的陆地格子」**了。如果题目更复杂一点，这很容易出 bug。

1.2 BFS

BFS 一般使用 队列 实现，二叉树的 BFS 一般用队列维护根节点：

① 队列不空条件下维护根节点

② 如果左右节点不为空就入队处理

类似地，对于网格问题也就是处理格子坐标：

① 队列中基本元素：队列不空条件下维护当前网格坐标

② 边界条件：如果格子是没有遍历过的并且未出界就入队处理上下左右四个格子

void bfs(vector<vector<int>>& grid, int r, int c) {
    queue<pair<int, int>> qu;
    qu.push({r, c});
    while (!qu.empty()) {
        auto [i, j] = qu.front();
        qu.pop();
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) {
            continue;
        }
        if (grid[i][j] != '1') {
            continue;
        }
        grid[i][j] = '2';
        qu.push({i+1, j});
        qu.push({i-1, j});
        qu.push({i, j+1});
        qu.push({i, j-1});
    }
}

2. 相关问题

典型网格

题目 说明 题解
200. 岛屿数量 基础BFS/DFS，遍历过的陆地格子标记为2 DFS BFS
695. 岛屿的最大面积 和 LC.200 类似，只是求所有岛屿面积的最大值 通过
827. 最大人工岛 要区分不同岛屿，set记录下标然后统计面积:fire: 图解
463. 岛屿的周长 在 DFS 遍历中，从一个岛屿方格走向一个非岛屿方格，周长就加 1 图解
  • 先污染后治理：先处理上下左右四个格子，然后判断边界条件

非典型网格

题目 说明 题解
547. 省份数量 连通分量个数，典型的并查集，另外 DFS/BFS 也可以标记节点 DFS BFS
934. 最短的桥 BFS/DFS 找岛都可以，最短路径一般使用 BFS，双 DFS 会超时 图解
1971. 寻找图中是否存在路径 判断节点是否连通，典型并查集，DFS/BFS 需要邻接表建图（无权重） DFS BFS

3. 记忆化 DFS 🔥

这类问题一般使用「数组」保存 DFS 过程得到的中间结果，避免重复计算，一般可以等价转换成动态规划，重点思考原问题和子问题，两者之间是如何转换的，进而转换成 DP

以 剑指 Offer 47. 礼物的最大价值 为列说明思考过程：

1. 从回溯到记忆化搜索

思考回溯

dfs(i, j) 表示从左上角到第 i 行第 j 列的最大价值和：

  • 从左边过来，dfs(i, j) = dfs(i, j-1) + grid[i][j]
  • 从上边过来，dfs(i, j) = dfs(i-1,j) + grid[i][j]

两者取最大值：dfs(i, j) = max(dfs(i, j−1), dfs(i−1, j)) + grid[i][j]

最终答案为：dfs(m-1, n-1)，边界条件：i < 0 || j < 0

记忆化 DFS

单纯回溯过程存在大量重复递归调用，由于递归函数没有副作用，无论调用 dfs(i, j) 多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：

int maxValue(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    
    // 加入哈希表记忆中间结果，避免重复计算
    int memo[m][n];
    memset(memo, 0, sizeof memo);
    
    function<int(int, int)> dfs = [&](int i, int j) -> int {
        if (i < 0 || j < 0)
            return 0;
        if (memo[i][j]) return memo[i];
        int ret = max(dfs(i, j - 1), dfs(i - 1, j)) + grid[i][j];
        memo[i] = ret;
        return ret;
    };
    return dfs(grid.size() - 1, grid[0].size() - 1);
}

说明：

  1. grid[i][j] 都是正数，所以 memo 可以初始化为0，表示没有计算过，如果 grid 中有0，需要将 memo 初始化为 -1，如果有负数，memo 可以初始化为 INT_MIN
  2. 注意加法运算发生在递归返回后，即递归的「归」的时候我们才开始计算最大价值和，所以计算顺序是从左上角到右下角

2. 1:1翻译成递推

去掉递归中的「递」，只保留「归」：

  • dfs 换成 dp 数组
  • 递归改程循环，每个参数对应一层循环
  • 递归边界改程 dp 数组的初始化

即有 dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + grid[i][j]，考虑到 i=0 || j=0 时出现负数下标，对 dp 数组下标整体 +1 处理，dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]) + grid[i][j]

dp(i+1, j+1) 表示从左上角到第 i 行第 j 列的最大价值和

dp[i][0] 和 dp[0][j] 都可以初始化为 0

int maxValue(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    int dp[m+1][n+1];
    memset(dp, 0, sizeof dp);

    // dp[i+1][j+1]表示从grid[0][0]到grid[i][j]时的最大价值
    for (int i = 0; i < m; ++ i) {
        for (int j = 0; j < n; ++ j) {
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]) + grid[i][j];
        }
    }

    return dp[m][n];
}

例题 更多参考动态规划

题目 说明 题解
剑指 Offer 47. 礼物的最大价值 比较简单的DP，重点思考从回溯到记忆化搜索到递推的过程 0x3F
2585. 获得分数的方法数 n-1 种题目，恰好组合 target-types[n-1][1] * k 分的方案数，实际上是分组背包，转成一维DP需要逆序枚举 target 0x3F
最优二叉树II memo[l][r][k] 表示以 w[l:r] 为子节点， w[k] 为根节点的树开销，转换成DP还未想到 分治
139. 单词拆分 记忆化顺着 DFS，逆着 DFS 都可以，注意使用含义处理边界，也可以看成有顺序的完全背包问题 DFS

4. 参考