搜索与回溯算法（深搜算法）——不撞南墙不回头

he188 / 2023-07-20 / 原文

基本概念

DFS全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是每次都想往更深的节点走。DFS通常用来指代用递归函数实现的搜索，但实际上两者并不完全一样。

优点：代码量小，可读性强，更容易实现。

缺点：若深度过高，容易栈溢出。

易超时。

使用场景：大量用于图论。

实在没有办法时用来骗分。

搜索
搜索是计算机程序设计中一种最基本、最常用的算法。搜索算法是直接基于计算机高速运算的特点而使用的计算机求解方法。它是从问题的初始状态出发，根据其中的约束条件，按照一定的策略，有序推进，不断深入，对于达到的所有目标状态（解空间），一一验证，找到符合条件的解（可行解），或者找出所有可行解中的最优解。

回溯
“回溯法”也称“试探法”。它是从问题的某一状态出发，不断“试探”着往前走一步，当一条路走到“尽头”，不能再前进（拓展出新状态）的时候，再倒回一步或者若干步，从另一种可能的状态出发，继续搜索，直到所有的“路径（状态）”都一一试探过。这种不断前进、不断回溯，寻找解的方法，称为“回溯法”。深度优先搜索求解的时候，当找到目标结点之后，还要回头寻找初始结点到目标结点的解路径。而回溯法则不同，找到目标结点之后，搜索路径就是一条从初始结点到目标结点的解路径。回溯法实际上是状态空间搜索中，深度优先搜索的一种改进，是更实用的一种搜索求解方法。

搜索与回溯的关系

深度优先搜索包含回溯，或者说回溯法是深度优先搜索的一种。
深度优先搜索需要控制如何实现状态之间的转移（拓展），回溯法就是深度优先搜索的一种控制策略。
回溯的过程中，并不需要记录整棵“搜索树”，而只需记录从初始状态到当前状态的一条搜索路径，是“线性链状”的，其最大优点是占用空间少。
深度优先搜索可以采用递归（系统栈）和非递归（手工栈）两种方法实现。递归搜索是系统栈实现一部分的回溯（如果需要记录一些特殊信息或较多的信息，还需要另外手工记录），而非递归是自己用手工栈模拟回溯的过程，所以实现起来略为复杂一点。

下图生动地体现了深搜的思想

基本模型

这里给大家展示一个递归（DFS）的模板（伪代码）：

void dfs(int argument){

if(结束条件满足){

如果有，就操作；

return;

}

当层要做的事情；

递归到下一层；

}

通过上面的基本模型我们可以解决一些简单的递归（DFS）问题，下面上例题。

例题分析

斐波那契数列
求斐波那契数列的第n项，第一项为0，第二项为1。

这是一道经典的递归题，可以直接套用上面的模板。

#include <bits/stdc++.h>
using namespace std;
int cnt=2,temp;
int fbi(int m){
if(m<=2) return m-1;//这句运用了一些技巧，不明白的朋友可以手算推理
return fbi(m-1)+fbi(m-2);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",fbi(n));
return 0;
}

最大公约数

求两个正整数a和b的最大公约数。学过编程的朋友一定知道这里运用到的小技巧——辗转相除法。不了解的朋友可以出门右转至百度百科。稍稍加以思考边会发现，辗转相除法其实就是递归的过程。

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
if(b==0)return a;
return gcd(b,a%b);
}
int main()
{
int m,n;
scanf("%d%d",&m,&n);
printf("gcd=%d",gcd(m,n));
return 0;
}

真题演练

1317：【例5.2】组合的输出

【题目描述】

排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。

现要求你用递归的方法输出所有组合。

例如n＝5，r＝3，所有组合为：

1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

【输入】

一行两个自然数n、r(1<n<21，1≤r≤n)。

【输出】

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

【输入样例】

5 3

【输出样例】

  1  2  3
  1  2  4
  1  2  5
  1  3  4
  1  3  5
  1  4  5
  2  3  4
  2  3  5
  2  4  5
  3  4  5
本题网址：http://ybt.ssoier.cn:8088/problem_show.php?pid=1317
本题就是一个十分明显的递归（DFS）问题，废话少说，直接上代码。

#include <bits/stdc++.h>
using namespace std;
int n[1005],a,b;
void dfs(int dep,int pre){

//dep代表层数

//pre代表上一个数

if(dep==b+1){ //如果层数=个数+1，则输出答案

for(int i=1;i<=b-1;i++)

{
cout<<setw(3)<<n[i];
}
cout<<setw(3)<<n[b]<<endl;
return ;
}
for(int i=pre+1;i<=a;i++){ //因为后面的数大于前面的数，所以要从pre+1开始
n[dep]=i;
dfs(dep+1,i);
}
}
int main()
{
cin>>a>>b;//输入两个自然数
dfs(1,0);
return 0;
}