搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。

深度优先搜索 (Depth First Search, DFS)

广度优先搜索 (Breadth First Search, BFS)

深度优先搜索 (DFS)

时间复杂度：$视具体情况，普遍极大$

代码实现模板：

type dfs(type x, ... ) // 可以存在多个变量
{
    if( ... ) // 达到目标状态
    {
        ... // 输出答案或判断最优解等等
        return;
    }
    if( ... ) // 达到搜索边界（即到边界了还没搜到，有时没有此步骤）
    {
        return;
    }
    for( ... ) // 遍历所有子节点
    {
        if( ... ) // 可以转移状态，一般用标志变量判断
        {
            ... // 修改标志变量，表明此节点不可转移
            dfs( ... ) // 搜索子节点，经常为x+1
            ... // 还原标志变量，表面此节点可转移
        }
    }
}

典型题型：

洛谷P1706 - 全排列问题: https://www.luogu.com.cn/problem/P1706

洛谷P1219 - [USACO1.5]八皇后 Checker Challenge: https://www.luogu.com.cn/problem/P1219

算法思路：

递归下去

先一直递归走到目标状态或达到边界条件

回溯上来

若碰到边界条件，则退回到上一步，再换其他路走

以“洛谷P1706 - 全排列问题”为例

例如我们要求 1 2 3 的所有排列方式，这四个数字存储在 num[ ] = {1, 2, 3}

  • 选 1，标记数组第零位，递归加深

    • 1 被标记，不选

    • 选 2，标记数组第一位，递归加深

      • 1 被标记，不选
      • 2 被标记，不选

      • 选 3，标记数组第二位，递归加深

        • 达到目标状态，输出答案 1 2 3
        • 函数结束，递归回溯
      • 取消标记数组第二位
      • 达到循环边界，函数结束，递归回溯
    • 取消标记数组第一位

    • 选 3，标记数组第二位，递归加深

      • 1 被标记，不选

      • 选 2，标记数组第一位，递归加深

        • 达到目标状态，输出答案 1 3 2
        • 函数结束，递归回溯
      • 取消标记数组第一位
      • 3 被标记，不选
      • 达到循环边界，函数结束，递归回溯
    • 取消标记数组第二位
    • 达到循环边界，函数结束，递归回溯

  • 选 2，标记数组第一位，递归加深

    • 选 1，标记数组第零位，递归加深

      • 1 被标记，不选
      • 2 被标记，不选

      • 选 3，标记数组第零位，递归加深

        • 达到目标状态，输出答案 2 1 3
      • 取消标记数组第零位
      • 达到循环边界，函数结束，递归回溯
    • 2 被标记，不选

    • 选 3，标记数组第二位，递归加深

      • 选 1，标记数组第零位，递归加深

        • 达到目标状态，输出答案 2 3 1
      • 取消标记数组第零位
      • 2 被标记，不选
      • 3 被标记，不选
      • 达到循环边界，函数结束，递归回溯
    • 取消标记数组第一位
    • 达到循环边界，函数结束，递归回溯
  • 选 3，标记数组第二位，递归加深

​ $\vdots$ 3 1 2 和 3 2 1 两组答案省略不写

广度优先搜索 (BFS)

时间复杂度：$视具体情况$

代码实现模板：

type start // 搜索起点
type ans // 答案
bool vis[ ] // 标记是否搜索过
int depth[ ] // 储存搜索深度
queue<type> que // STL队列

type bfs()
{
    que.push(start); // 起点入队
    depth[start] = 0; // 起点深度0
    vis[start] = true; // 标记起点
    while (!que.empty())
    {
        type now = que.front(); // 当前节点设置为队首
        que.pop(); // 弹出队首
        if ( ... ) // 如果达到目标条件
        {
            ans = depth[now]; // 储存答案
            return; // 搜索结束
        }
        for( ... ) // 遍历now节点的所有子节点，可用数组表示方向
        {
            type next = ... // 计算出子节点
            if (!vis[next] && ... ) // 如果子节点未搜索过，且范围符合题目条件
            {
                vis[next] = true; // 标记子节点
                depth[next] = depth[now] + 1; // 子节点深度+1
                que.push(next); // 子节点入队
                // 有时题目还需输出具体路径，可用一个数组储存每个节点的上一个节点，然后在此处对数组赋值。输出时，从结尾递归反向输出即可获得具体的路径。
            }
        }
    }
}

典型题型：

POJ3984 - 迷宫问题: http://poj.org/problem?id=3984

算法思路：

选取节点

从起点开始，选取当前节点的子节点

标记深度

标记当前子节点的深度，并且标记此节点已经搜索过

以“POJ3984 - 迷宫问题”为例

（以样例输入为例）

设定一个方向数组pair<int, int> dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}} 代表右、下、左、上，这样就能方便用 for 循环来遍历上下左右四个方向。

  • 起点入队，当前队列包含 $(0,0)$，标记 $(0,0)$ 已经搜索过

  • 开始正式搜索循环，当队列空时停止搜索，即当所有节点搜完时停止搜索

    • 设置当前节点为队首 $(0,0)$
    • 弹出 $(0,0)$，队列空
    • $(0,0)$ 不是终点，因此不结束

    • 进入子节点遍历循环

      • i = 0，方向数组代表右
      • 计算子节点为 $(1,0)$
      • $(1,0)$ 是迷宫墙，因此此子节点不符合条件
      • i = 1，方向数组代表下
      • 计算子节点为 $(0,1)$

      • $(0,1)$ 未搜索过，不是迷宫墙，未超出迷宫范围，因此此子节点符合条件

        • 标记 $(0,1)$ 已经搜索过
        • $(0,1)$ 入队，队列: $(0,1)$
      • i = 2，方向数组代表左
      • 计算子节点为 $(-1,0)$
      • $(-1,0)$ 是迷宫墙，因此此子节点不符合条件
      • i = 3，方向数组代表上
      • 计算子节点为 $(0,-1)$
      • $(0,-1)$ 以标记搜索过，因此此子节点不符合条件
    • 进入下一次循环
    • 设置当前节点为队首 $(0,1)$
    • 弹出 $(0,1)$，队列空

​ $\vdots$

标签: 深度优先搜索, 广度优先搜索

添加新评论