信息学赛培 | 08 不可不知的搜索与回溯——深度优先搜索算法与实例详解
戳一戳！和我一起走进信息学的世界
导读
信息学能够有助于孩子未来工作发展，提升孩子的综合能力。
前面我们提到了图的深度优先遍历，图的深度优先遍历是深度优先搜索算法在图论场景中的应用，今天这节课，我们从理论角度来学习搜索与回溯，了解深度优先搜索算法，并通过实例来感受深度优先搜索。
往期回顾
【NOIP竞赛/CSP认证】
【信息学精华帖】
▶
▶
▶
▶
▶
【信息学集训】
【信息学集训】
▶
▶
▶
▶
▶
▶
【数据结构前导课】
▶
【C++提高班教程】
【C++基础班教程】
1 深度优先遍历回顾
首先我们先来复习一下数组吧。
1 举个例子来理解深度优先遍历
大家都玩过迷宫游戏，我们在找路的时候，我们就从一个路口开始，一直找，当我们发现走到死胡同的时候，我们就要返回去重新走。
这个过程就像是深度优先遍历一样，我们先考虑能走得路，一直走，走到不能走为止，然后返回找新的路。例如下图：
假设我们从1开始走，比如我们先走2，然后继续往里面走，到3，然后再走到4，然后再走到5，和5相邻的有3，发现3走过了，就返回走4，发现4页走过了，再返回走6。
深度优先遍历是说我们先尽可能往里面走，当我们走到已经到达的位置的时候，我们就返回来重新走。
我们以深度优先搜索下图为例：
首先是图结构的存储。邻接节点是不需要边的起点的，我们在这里就不写啦。
struct Edge {
int v; //边的终点
int next; //当前边在邻接表中的下一条边
}e[100];
int vFirst[100]; //每个节点指向的第条边，没有存为-1，邻接表指针
int vis[100]; //表示节点是否被访问过然后我们编写输入节点的代码，这个输入的过程其实就是单链表头插法的插入过程，先输入的边会后访问，后输入的边会先访问，我们把这种现象称为“后来者居上”：
void e_push_back(int u,int v)
{
e[k].v=v; //输入终点
e[k].next=vFirst[u]; //以u为起点，指向的next是vFirst[u]。
vFirst[u]=k; //更新u的目前第一个指向的边
k++; //k为边的序号
}这里需要我们定义一个变量k来保存第k条边。我们也需要如下几个变量：
n：顶点个数m：边的个数x和y：存在边的两个顶点
定义如下：
int n,m,k;
int x,y;然后是输出我们的邻接表，为了看起来效果更好，我们在输出语句中可以做些适当的调整：
void print(){ //从顶点的角度输出
for(int i = 1;i<=n;i++){
cout<<"["<<i<<"]->"<<e[vFirst[i]].v;
k = vFirst[i];
while(e[k].next != -1){
k = e[k].next;
cout<<"->"<<e[k].v;
}
cout<<endl;
}
}例如我们将上图输入，就会得到下面的结果：
通过上面的代码，我们就能够知道，我们已经成功存储了邻接表，然后就是基于邻接表，我们来深度优先遍历图了。深度优先遍历最经常用的方式是递归。递归过程本质上就是在不断地入栈和出栈，也就是说递归自动实现栈，就不需要我们自己定义栈结构和相关操作了。
深度优先遍历，我们从某一个顶点开始，流程描述如下：
从某个顶点开始访问如果这个顶点访问过，那就跳过；如果这个顶点没有访问过，就执行如下操作：（1）访问该顶点并标记访问；（2）深度优先遍历每一个相邻的顶点
我们通过这种递归的方式，会先一直深度遍历下去，当遍历到某个顶点已经访问过了，我们就返回遍历下一个相邻的顶点。
代码如下：
void dfs(int x) {
if(vis[x]) return ; //访问过，就退回去
vis[x]=1; //没访问过就访问
cout<<x<<endl; //简单的访问操作
for(int i=vFirst[x]; i!=-1; i=e[i].next){//遍历每一个相邻的顶点，保证回溯
dfs(e[i].v); //深度优先遍历每一个
}
}全部代码如下：
#include<string.h>
#include<iostream>
using namespace std;
int n,m,k;
int x,y;
struct Edge {
int v; //边的终点
int next; //当前边在邻接表中的下一条边
}e[100];
int vFirst[100]; //每个节点指向的第条边，没有存为-1，邻接表指针
int vis[100]; //表示节点是否被访问过
void e_push_back(int u,int v)
{
e[k].v=v; //输入终点
e[k].next=vFirst[u]; //以u为起点，指向的next是vFirst[u]。
vFirst[u]=k; //更新u的目前第一个指向的边
k++; //k为边的序号
}
void print(){ //从顶点的角度输出
for(int i = 1;i<=n;i++){
cout<<"["<<i<<"]->"<<e[vFirst[i]].v;
k = vFirst[i];
while(e[k].next != -1){
k = e[k].next;
cout<<"->"<<e[k].v;
}
cout<<endl;
}
}
void dfs(int x) {
if(vis[x]) return ; //访问过，就退回去
vis[x]=1; //没访问过就访问
cout<<x<<endl; //简单的访问操作
for(int i=vFirst[x]; i!=-1; i=e[i].next){//遍历每一个相邻的顶点，保证回溯
dfs(e[i].v); //深度优先遍历每一个
}
}
int main() {
memset(vFirst,-1,sizeof(vFirst)); //-1表示空
cin>>n>>m;
for(int i=0;i<m;i++) {
cin>>x>>y;
e_push_back(x,y);
e_push_back(y,x); //无向图要存两次
}
print();
cout<<"***********************"<<endl;
dfs(1); //默认从第一个顶点开始访问
}执行结果如下：
2 搜索与回溯
接下来我们来看搜索与回溯！
搜索与回溯是计算机解题中常用的算法。常常在一起出现。深度和回溯的结合其实就是深度优先搜索的过程。让我们先来简单了解一下搜索与回溯吧！
1 搜索
前面遍历的过程其实就是搜索的过程，我们可以在这个过程中判断当且节点和我们要搜索信息的关系。
遍历只需要将节点输出就可以了。搜索的就是将输出代码改成搜索代码即可。
我们的深度优先搜索算法在搜索过程中到达死胡同的时候，就会返回上一层，也就是在递归过程中退出内层递归到达外层递归，这个过程叫回溯。
3 深度优先搜索理论
了解了搜索与回溯，我们来看一下深度优先搜索！
1 深度优先搜索算法
深度优先搜索算法和深度优先遍历的思想和过程是一致的，深度优先遍历是深度优先搜索算法在图论中的独有的名称。
也就是说，当我们把深度优先搜索算法应用到图论中遍历图的时候，我们将其称之为深度优先遍历。
深度优先搜索不仅可以用到图论中，还能应用到各个领域。也就是说，深度优先搜索不一定是图中的问题。我们首先来看一下深度优先搜索算法的思想。
搜索每一种情况如果不满足某些搜索条件，就跳出；如果满足某些搜索条件：1、搜索这种情况2、递归搜索和这种情况相关的其他情况3、回溯
根据上面的思想，我们可以实现简单的深度优先搜索算法。在这里，我们给出两个比较常用的框架：
int Search(int k){for (i=1;i<=情况数;i++)if (满足条件){保存结果if (到目的地) 输出解;else Search(k+1);恢复：保存结果之前的状态}}
int Search(int k){if(到目的地) 输出解;else for(i=1;i<=情况数;i++)if(满足条件){保存结果;Search(k+1);恢复：保存结果之前的状态}}
4 深度优先搜索实战
下面我们通过实战来真正了解深度优先搜索吧！
1 素数环
素数环是一个非常有意思的环。
如果我们的整数序列首尾相连构成环，任意相邻两个整数的和是素数，我们就说这个序列能够构成素数环。
现在，要求输入一个整数n，判断从1到n的所有整数能够构成素数环的不同的整数序列的个数。
例如：1,2,3,4这四个数能够组成的构成素数环的整数序列如下：
1 2 3 41 4 3 22 1 4 32 3 4 13 2 1 43 4 1 24 1 2 34 3 2 1
一共有八种情况，输出8。
【分析】
我们要通过不断地遍历这些情况，一种方式是我们可以使用枚举。但是枚举代价太大了，例如：1234和1243这两个，如果使用枚举，12两部分的判断过程是重复的，我们不需要再计算。深度优先搜索，可以保证前面的运算过的结果后面可以直接用，所以使用深度优先搜索效率更高。
在讲如何搜索之前，我们要先写一个判断素数的函数，方便我们在搜索过程中判断。
对于本题来说，要判断两个数的和是否为素数，我们可以跳过1和2，因为序列中任意两个正整数是不同的，最小的和是1+2=3。所以我们判断素数直接判断奇数即可。具体代码思想，我们前面已经讲过很多，这里直接给出代码：
bool isP(int x,int y) {
int s = x+y;
if(s%2==0) return false; //除2外的偶数不是素数
for(int i = 3;i*i<=s;i+=2){
if(s%i==0) return false; //有因数不是素数
}
return true;
}
使用深度优先搜索也是考虑所有情况。所以我们要使用循环：
void search(int t) {
for (int i=1;i<=n;i++){ }
}上面是深度优先搜索的框架。其 从1遍历到n中t表示我们开始搜索的位置，一般都是从1开始，n表示的是最大的那个整数，我们要从1遍历到n。
在循环内，我们要判断每一个新放进去的数有没有使用过，和前面的一个数的和是不是素数，如果没有使用过并且和是素数，我们就可以将其先存下来。
这种情况会出现一个问题，就是第一个数据不好存。我们不知道最后一个存的是什么，所以我们可以假设第一个数和最后一个数已经是素数了，最后我们判断一下最后一个数加第一个数是不是素数就可以了。
所以，当我们访问第一个位置的时候，我们认为是素数，当我们访问后面的位置的时候，要考虑他们和前面一个位置上的数据的和是否是素数。
代码如下：
int search(int t) {
for (int i=1;i<=n;i++) { //有20个数可选
if(t==1||isP(a[t-1],i)&&(!vis[i])) {
}
}
}其中：
t==1代表我们考虑第一个位置，并假设其为素数，满足条件；isP(a[t-1],i)表示我们新放入的整数i和已经存下来的最后一个数a[t-1]之和是否是素数；(!vis[i])表示第i个位置是否前面已经使用，如果使用，vis[i]=1.
所以上面的判断的含义就是，第一个位置，我们认为是素数，可行。非第一个位置，要满足新加入的数据不能使用过，并且和前一个位置的数据之和是素数。
当我们满足了上面要求，就可以将新的数据i加入到序列中了，然后我们需要标记我们的数据i已经被使用过了。对应代码如下：
int search(int t) {
for (int i=1;i<=n;i++) { //有20个数可选
if(t==1||isP(a[t-1],i)&&(!vis[i])) {
a[t]=i; //将i放入序列中
vis[i]=1; //标记i已经使用
}
}
}我们还要考虑，如果新插入的位置t是最后一个位置，那我们还要满足该位置和第一个位置上的数据的和是素数，如果是，我们就可以计数一次。
int search(int t) {
for (int i=1;i<=n;i++) { //有20个数可选
if(t==1||isP(a[t-1],i)&&(!vis[i])) {
a[t]=i;
vis[i]=1;
if (t==n) {
if(isP(a[n],a[1])) total++;
}
}
}
}如果不是素数，那我们就要回溯回去，找下一个数据。
int search(int t) {
for (int i=1;i<=n;i++) { //有20个数可选
if(t==1||isP(a[t-1],i)&&(!vis[i])) {
a[t]=i;
vis[i]=1;
if (t==n) {
if(isP(a[n],a[1])) total++;
}
else search(t+1);
}
}
}不管如何，一轮判断已经完成，等后续判断其他情况，又需要用到数据i，所以做完上面的，我们要让i的访问变为未访问。不影响其他情况的计数：
int search(int t) {
for (int i=1;i<=n;i++) { //有20个数可选
if(t==1||isP(a[t-1],i)&&(!vis[i])) {
a[t]=i;
vis[i]=1;
if (t==n) {
if(isP(a[n],a[1])) total++;
}
else search(t+1);
vis[i]=0;
}
}
}如果我们想输出所有的满足要求的情况，我们可以在计数的时候输出，我们可以写如下输出函数，并将计数写在total中：
int print() {
total++;
cout<<"第"<<total<<"组 : ";
for (int j=1;j<=n;j++) cout<<a[j]<<" ";
cout<<endl;
}上面的深度优先搜索代码，把total++改为调用print（）函数。
全部代码如下：
#include<iostream>
using namespace std;
bool vis[21];
int total,a[21],n;
bool isP(int x,int y) {
int s = x+y;
if(s%2==0) return false; //除2外的偶数不是素数
for(int i = 3;i*i<=s;i+=2){
if(s%i==0) return false; //有因数不是素数
}
return true;
}
int print() {
total++;
cout<<"第"<<total<<"组 : ";
for (int j=1;j<=n;j++) cout<<a[j]<<" ";
cout<<endl;
}
int search(int t) {
for (int i=1;i<=n;i++) { //有20个数可选
if(t==1||isP(a[t-1],i)&&(!vis[i])) {
a[t]=i;
vis[i]=1;
if (t==n) {
if(isP(a[n],a[1])) print();
}
else search(t+1);
vis[i]=0;
}
}
}
int main()
{
cin>>n;
search(1);
cout<<total<<endl;
return 0;
}执行结果如下：
6 作业
本节课的作业，就是复习上面的所有知识，并完成下面的题目！
1 整数的拆分
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。
例如3可以拆成如下两种情况：
3=1+1+13=1+2（1+2和2+1我们认为是同一种）
4可以拆成如下四种情况：
4=1+1+1+14=1+1+24=1+34=2+2
现在要求输入一个整数n，输出整数n能够拆分的情况数m。
AI与区块链技术
长按二维码关注