深度优先搜索算法笔记

深度优先搜索

今天我们来讲解的是深度优先搜索，这是我们大家学习信息是必不可少也是最总要的一个算法，那么深度优先搜索这个算法究竟是干了什么呢？这很简单。本质搜索搜索，就在于这二字，也就是一个一个查找。不过深度优先搜索，其实就是在这棵搜索树中以深度为先，也就是所谓的不撞南墙不回头，就是说我们可以把它认为是走迷宫，如果到了终点就没有关系，不然就继续走，碰到弯道一直往右，碰到死胡同再绕出来。就是怎么简单。那么接下来我们就来看一下一道比较经典的问题，也就是全排列问题。

全排列

首先，这类问题的一个特点就是跟数字有关，比如自然数的拆分这道题目，就是进行一个分解，并且数据范围的大小是我们可以接受的这种，因为搜索这种算法在现在通常是一种暴力骗分的一种手段。所以我们可以使用搜索进行一个获取部分分。所以我们先拿这道题目来举一个例子。

按照字典序输出自然数 $1$ 到 $n$ 所有不重复的排列，即 $n$ 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

那么这道题的思路就是从第一个数开始看，每一个位置都从 $1$ 到 $n$ 进行一个遍历的操作。同时要注意，因为排列每个数只能使用一次，所以另外再记录一个有没有使用过的数组进行存储。那么如果所有位置都遍历完毕，我们就进行一个输出。同时最重要的回溯也必不可少。那么回溯究竟是什么呢？再说回走迷宫，每次你走到死胡同里面，那么你是不是需要进行回到上一个路口走另一个弯道。所以这就是回溯。接下来给大家贴一下代码。

#include<bits/stdc++.h>
using namespace std;
int b[1000], a[1000], n;//b就是记录有没有使用过
void dfs(int x)
{
if(x==n+1)//说明所有位置都填好了
{
cout<<"    ";
for(int i=1;i<=n;i++)//输出
{
cout<<a[i]<<"    ";
if(i==n)
{
cout<<endl;
}
}
}
for(int i=1;i<=n;i++)
{
if(b[i]==0)//没有填过
{
a[x]=i;
b[i]=1;
dfs(x+1);
b[i]=0;//回溯
}
}
}
int main()
{
cin>>n;
dfs(1);
return 0;
}

剪枝

众所周知，搜索的时间复杂度是非常高的，比如刚刚拿到题目，每一个位置都是放或者是不放，时间复杂度就是次方式的样子。所以剪枝就是必不可少的。剪枝分为最优性剪枝和可行性剪枝。最优性剪枝就是说如果你的答案已经比你目前算出的答案大了或者是更劣的，我们就需要直接舍弃，避免浪费时间。这个比较好理解。不过可行性剪枝就比较难了，就是通过寻找题目中给你的一些条件，来将一写1无用的减掉。比如题目需要奇数，那么偶数就可以直接剪掉，所以可行性剪枝一般比最优性剪枝优化的更多。

原文地址：https://blog.csdn.net/mikeshizi1234/article/details/145230525

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！