DFS:深度优先搜索

暴力算法和 DFS 有什么区别？剪枝，回溯又是什么？

这是一篇给我自己看的笔记，用以备忘

在做蓝桥杯的题目时候遇到一个题目，它的描述如下

小明是个急性子，上小学的时候经常把老师写在黑板上的题目抄错了。

有一次，老师出的题目是：36 * 495 = ?

他却给抄成了：396 * 45 = ?

但结果却很戏剧性，他的答案竟然是对的！！

因为 36 * 495 = 396 * 45 = 17820

类似这样的巧合情况可能还有很多，比如：27 * 594 = 297 * 54

假设 a b c d e 代表 1~9 不同的 5 个数字（注意是各不相同的数字，且不含 0）

能满足形如： ab * cde = adb * ce 这样的算式一共有多少种呢？

请你利用计算机的优势寻找所有的可能，并回答不同算式的种类数。

满足乘法交换律的算式计为不同的种类，所以答案肯定是个偶数。

人话来说，就是找出满足ab * cde = adb * ce的所有a b c d e，并且他们数值不会重复，且他们是处于 1-9 这个区间的

解决方案

一共存在两种解决方案，暴力枚举和 DFS。

暴力枚举能比较简单的解决问题，但是它需要走所有的可能才能得出结果，优点在于思想简单容易理解

DFS 解决它的方法可能相对复杂，但是它不不想要知道所有的可能，他会在触碰边界后回退到上一步尝试下一种可能。

重点讲解理解 DFS

跳出这种可能，即为剪枝。

回退到上一步尝试下一种可能，即为回溯。

暴力枚举

我们假设一共有a，b，c，d，e五个循环，其中初始化数据均为 1，包裹顺序为 a 包裹 b 包裹 c 包裹 d 包裹 e，代码如下

for (int a = 1; a < 10; a++) {
    for (int b = 1; b < 10; b++) {
        for (int c = 1; c < 10; c++) {
            for (int d = 1; d < 10; d++) {
                for (int e = 1; e < 10; e++) {
                    // 跳出条件
                }
            }
        }
    }
}

能暴力枚举出所有可能，但是这个不是我们的最佳解法——它的范用性非常的差

DFS，深度优先搜索

DFS 一般和全排列在一起，它也能列举出所有的可能并且会尽可能深的访问数据结构，但是它有剪枝和回溯能力以及固定的代码格式，相比之下它有了更强的范用性

它的关键字为：回溯，递归，剪枝

以下为它的伪代码表示

// 这是当前的数据数组，需要看情况调整
ArrayList<Integer> numCombine = new ArrayList<>();
// 需要假设最远步数
int maxStep;

void dfsRun(int step) {
    // 边界，maxStep为步数边界
    if (step == this.maxStep) {
        // 已经到达了边界，需要跳出这一条线路
        dfsCheck();
        return;
    }
    // 递归条件
    // for语句中填充初始化条件
    for (;;) {
        // 跳出条件，意味着当前分支已经失败
        // 这里就是剪枝操作
        if()
            continue;
        this.numCombine.add(i);
        // 走下一步
        this.dfsRun(step + 1);
        // 回溯，因为这个条件已经判断过了，需要回退一步
        this.numCombine.remove(this.numCombine.size() - 1);
    }
}

void dfsCheck() {
    // 这里写检查条件
    // 当检查成功时，可以把它储存起来
}

这就是 DFS 的模板代码了。

用文字的方法来理解它：

1.首先将根节点放入 stack 中。 2.从 stack 中取出第一个节点，并检验它是否为目标。

如果找到目标，则结束搜寻并回传结果。 否则将它某一个尚未检验过的直接子节点加入 stack 中。

3.重复步骤 2。 4.如果不存在未检测过的直接子节点。

将上一级节点加入 stack 中。 重复步骤 2。

5.重复步骤 4。 6.若 stack 为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

理解起来很困难对吧，没关系来看下面资料继续理解 XD

• WikiPedia：深度优先搜索
• 我的代码仓库：L4B2

用到的资源 由 Alexander Drichel - 自己的作品，CC BY-SA 3.0，https://commons.wikimedia.org/w/index.php?curid=3791979