深度优先搜索dfs

一、深度优先搜索

1、深搜概述

深度优先搜索dfs：按照深度优先的方式进行搜索，"一条路走到黑"。

深度优先搜索和递归的区别：深度优先搜索是一种算法，注重的是思想，而递归是一种基于编程语言的实现方式

2、迷宫问题

迷宫问题的解法就需要用到dfs。我们对上下左右四个方向，一个方向一个方向地尝试，如果沿着某个方向不能走到终点，我们就要原路返回，继续尝试其他方向，直到走出迷宫。这是一种最朴素的走迷宫方式，虽然效率也许比较低，但如果迷宫有解，就一定能走出终点。

dfs 算法：首先找到起点S，走到每个点时，按照左、下、右、上的顺序尝试。每走到下一个点以后，我们把这个点当做起点S，继续按顺序尝试。如果某个点上下左右四个方向都尝试过，便回到走到这个点之前的点，这一步我们称之为 回溯。继续尝试其他方向。直到所有点都尝试过上下左右四个方向。

样例

5 6 
....S*
.***..
.*..*.
*.***.
.T....

代码

/**
 * 迷宫问题dfs
 * @author  王铭颢
 * @Date  2022/11/25 14:02
 */

#include "iostream"

using namespace std;
int n, m;
string mp[110];
bool vst[110][110];
int dir[4][2] = {{1,  0},
                 {-1, 0},
                 {0,  -1},
                 {0,  1}};

bool in(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < m;
}


bool dfs(int x, int y) {
    if (mp[x][y] == 'T') {
        return true;
    }
    vst[x][y] = 1;
    mp[x][y] = 'm';
    for (int i = 0; i < 4; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (in(tx, ty) && mp[tx][ty] != '*' && !vst[tx][ty]) {
            if (dfs(tx, ty)) {
                return true;
            }
        }
    }
    mp[x][y] = '.';
    vst[x][y] = 0;
    return false;
}

int main() {
    cin >> n >> m;
    int x, y;
    for (int i = 0; i < n; i++) {
        cin >> mp[i];
        for (int j = 0; j < m; j++) {
            if (mp[i][j] == 'S') {
                x = i, y = j;
            }
        }
    }

    if (dfs(x, y)) {
        for (int i = 0; i < n; i++) {
            cout << mp[i] << endl;
        }
    } else {
        cout << "No!" << endl;
    }

    return 0;
}

3、迷宫最短路径

样例

5 6 
....S*
.**...
.*..*.
*..**.
.T....

7

代码

/**
 * 迷宫最短路径
 * @author  王铭颢
 * @Date  2022/11/25 14:02
 */

#include "iostream"

using namespace std;
int n, m;
string mp[110];
bool vst[110][110];
int dir[4][2] = {{1,  0},
                 {-1, 0},
                 {0,  -1},
                 {0,  1}};
int ans = 0x6f6f6f;

bool in(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < m;
}


void dfs(int x, int y, int step) {
    if (mp[x][y] == 'T') {
        ans = min(ans, step);
        return;
    }
    vst[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (in(tx, ty) && mp[tx][ty] != '*' && !vst[tx][ty]) {
            dfs(tx, ty, step + 1);
        }
    }
    vst[x][y] = 0;
}

int main() {
    cin >> n >> m;
    int x, y;
    for (int i = 0; i < n; i++) {
        cin >> mp[i];
        for (int j = 0; j < m; j++) {
            if (mp[i][j] == 'S') {
                x = i, y = j;
            }
        }
    }
    dfs(x, y, 0);
    cout << ans << endl;

    return 0;
}

二、抽象dfs

1、n个数的和

给定$n$个整数，要求选出$K$个数，使得选出来的数的和为$sum$。

二进制枚举：对于每一个数，枚举选或者不选两种情况，用 dfs 思想来完成枚举

/**
 * n个数的和
 * @author  王铭颢
 * @Date  2022/11/25 15:19
 */

#include "iostream"

using namespace std;
int n, k, sum, ans;
int num[1005];

void dfs(int i, int tmp, int cnt) {
    if (tmp > sum || cnt > k) return;
    if (i == n) {
        if (cnt == k && tmp == sum) ans++;
        return;
    }
    dfs(i + 1, tmp + num[i], cnt + 1);
    dfs(i + 1, tmp, cnt);
}

int main() {
    cin >> n >> k >> sum;
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    }
    dfs(0, 0, 0);
    cout << ans << endl;
    return 0;
}

三、dfs剪枝

1、可行性剪枝

剪枝：通过一些判断，砍掉搜索树上不必要的子树。有时候，我们会发现某个结点对应的子树的状态都不是我们要的结果，那么我们其实没必要对这个分支进行搜索，砍掉这个子树，就是剪枝。

可行性剪枝：找新的边界条件（选多，超范围...）

2、最优性剪枝

对于求最优解的一类问题，通常可以用最优性剪枝，比如在求解迷宫最短路的时候，如果发现当前的步数已经超过了当前最优解，那从当前状态开始的搜索都是多余的，因为这样搜索下去永远都搜不到更优的解。通过这样的剪枝，可以省去大量冗余的计算。

此外，在搜索是否有可行解的过程中，一旦找到了一组可行解，后面所有的搜素都不必再进行了，这算是最优性剪枝的一个特例。

3、重复性剪枝

对于某一些特定的搜索方式，一个方案可能会被搜索很多次，这样是没必要的。

给定n 个整数，要求选出 区 个数，使得选出来的区个数的和为 sum。

如果搜索方法是每次从剩下的数里选一个数，一共搜到第K层，那么1,2,3这个选取方法能被搜索到6次，这是没必要的，因为我们只关注选出来的数的和，而根本不会关注选出来的数的顺序，所以这里可以用重复性剪枝。