DFS深度优先搜索从入门到入坟

今天药忘吃喽~ 2022-11-22 12:58 146阅读 0赞

# DFS深度优先搜索与回溯入门讲解——不见南墙不死心 #

深度优先（DFS，Deep First Search）和回溯计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：**为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。**

如迷宫问题：*进入迷宫后，**先随意选择一个前进方向，一步步向前试探前进（搜索）**，如果碰到死胡同，说明前进方向已无路可走，这时，首先看其他方向是否还有路可走，如果有路可走，则沿该方向继续试探；如果无路可走，**则返回一步到上一步（回溯）**，再看看其他方向是否还有路可走；如果有沿方向试探。这是回溯原则，按此原则不断搜索、回溯，直到找到出口或者没有出口为止。*

## 例题：全排列 难度：★★☆☆☆ ##

> 输入一个数，输出1~n的全排列。
> 
> Input: 3
> 
> Output:
> 
> 123  
> 132  
> 213  
> 231  
> 312  
> 321

首先形象化问题，我们拿n=3来举例子。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]

假设这里有3个盒子，一个人拿着3个牌往这些盒子里放，看有几种放法。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]

那么深度优先的过程如下：（给这人起名叫小明，希望能看懂）

1.  小明，走到一号盒子面前，“我们放牌要有一个顺序”小明想，于是规则是**每到一个盒子，能先放1先放1，否则2，再否则3**
2.  于是小明将1号牌放在1号盒子里。
3.  他拿着2和3走到2号盒子，放下了2号。
4.  在3号盒子放下了3号。
5.  于是他发现没有下一个盒子了，手中也没有牌了。所以他记录下这个排列`123`
6.  他开始回溯，收回了一个3，但是只剩一个三号盒子，他还没有选择，只能再收回一个2号牌。
7.  他站在2号盒子面前，手中有两张牌，2已经放过了，于是放下了3，现在是`13_`。
8.  他来到3号盒子，只能放下2，新的排列产生了，`132`。
9.  撤回2，再撤回3，发现剩下的两个盒子也已经穷尽了，于是把1也撤回了。现在是`___`。
10. 第一个盒子放过1，所以按照规定放下2，第二个盒子按照规定放1，第三个放3。现在是`213`
11. 回溯，继续搜索，`231`
12. 以此类推……`312`、`321`
13. 最后3也回溯完成，山穷水尽，结束递归，搜索完成。
14. （不知道博客里大家能不能看懂，反正我看懂了）

逻辑说完下面编程。

先定义变量；

int n; // 总量
    int nums[11]; // 存贮单次结果
    int marks[11]; // 标记数组
    // 由于下标只定义了11个，所以n不能太大

下面是核心函数：（没有递归基础的估计看不懂，可以认识一下递归）

void dfs(int num)
    { 
        if (num == n + 1) {  // 也就是产生了新的排列
            for (int j = 1; j <= n; j++)
                cout << nums[j];  // 输出结果
            cout << endl;
            return; // 返回上一层（回溯）
        }
        for (int i = 1; i <= n; i++)
        { 
            if (marks[i] == 0) // 这个牌还没有被用过，比如1__，不可以再使用1
            { 
                nums[num] = i;
                marks[i] = 1; // 标记此牌已经用过
                dfs(num + 1); // 继续下一个数 比如 12_，去找第三个数
                marks[i] = 0; // 非常重要，收回牌才能继续放置（回溯步骤）
            }
        }
        return; // 结尾散花！
    }

主程序只需要这么点：

int main()
    { 
        cin >> n;
        dfs(1);
        return 0;
    }

完整程序：

#include <iostream>
    using namespace std;
    int n;
    int nums[11];
    int marks[11];
    void dfs(int num)
    { 
        if (num == n + 1) { 
            for (int j = 1; j <= n; j++)
                cout << nums[j];
            cout << endl;
            return;
        }
        for (int i = 1; i <= n; i++)
        { 
            if (marks[i] == 0)
            { 
                nums[num] = i;
                marks[i] = 1;
                dfs(num + 1);
                marks[i] = 0;
            }
        }
        return;
    }
    int main()
    { 
        // 最多n=10
        cin >> n;
        dfs(1);
        return 0;
    }

核心代码很短，却饱含深度优先搜索的基本模型。理解深度优先搜索的关键在于解决“当下该如何做”。至于“下一步要怎么做”则与“当下该如何做”是一样的。这不光是深度优先的逻辑，也是递归乃至分治算法的逻辑——将大问题分解成更小的相同的问题，直到分解为最小。

## DFS基本框架 ##

框架\[1\]

void dfs(int step)
    { 
    	判断边界
    	尝试每一种可能 for (i = 1; i <= n; i++)
    	{ 
    		继续下一步 dfs(step + 1);
    	}
    	返回
    }

框架\[2\]

int search(int k)
    { 
    	for(i = 1; i <= 算符种数; i++)
    	{ 
    		if (满足条件)
    		{ 
    			保存结果
    			if (到目的地) 输出解;
    				else search(k + 1)
    		}
    	}
    }

## 练习题：□□□+□□□=□□□ 难度：★★★☆☆ ##

一个三位数+一个三位数=一个三位数，输出所有结果。

## 资源 ##

*  《信息学奥赛一本通-C++篇》
 *  《啊哈！算法》

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/8f6db38843f6458f8bd744f9164db546.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201104163708955.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ==,size_16,color_FFFFFF,t_70#pic_center