[数据结构与算法]4.4 DFS

4.4 DFS

黑书的这一章节和上一章节一样汇总了DFS部分的知识和内容。

4.4.1 DFS和递归

上一章已经介绍过了BFS和DFS两种算法思想，我们这里就直接看hdu1312使用DFS的解法。

void DFS(int dx,int dy){room[dx][dy]='#'; num++;//标记已经搜索过的区域防止重复遍历 
	for (int i=0;i<4;i++){int newx=dx+dir[i][0],newy=dy+dir[i][0];//向四个方向进行深搜 
		 if (CHECK(newx,newy)&&room[newx][newy]=='.') DFS(newx,newy);		
	}//遇到满足要求的新节点向下进行深搜
} 

肉眼可见的可以发现DFS的代码要比BFS的代码简单一些。

4.4.2 回溯与剪枝

还记得我之前手绘的DFS运行的概念图么？DFS搜索的基本操作是选取一个方向的路径进行不断地扩展。

但是在很多情况下，用递归枚举所有的路径可能会因为路径上的结点个数太大而超时。由于很多子节点是不符合条件的，于是可以在递归时遇到肯定没法得到正确结果的结点而撤退，即向前回溯。

BFS中最经典的问题是八数码问题，DFS中最经典的即是八皇后问题。但是这个问题，我们在紫书上面的回溯法已经做过详细的讨论，并且黑书这里和紫书并没有太大的区别，于是我们只贴个代码，有需要的回顾那章内容。

//书上这里需要得到的是方案总数和方案的具体路径,所以这里的算法思想倾向于dfs 
//大家可以想一想如果是需要得到字典序最小(某个条件最优)的一种方案,算法思想会倾向于哪种 
void search(int cur){//cur表示当前解答树的层数 
	if (cur==n) tot++;//tot表示答案总数
	else for (int i=0;i<n;i++){
		//此时cur表示行,i表示列 
		//这里的vis是书上这个编写方法的精髓,vis[0][i]表示第i列是否存在棋子,我们是按行递归的所以不用考虑行
		//比较困难的是两个对角线,我们将从左上指向右下的对角线记作主对角线,左上指向右下的对角线记作副对角线
		//对于一个格子(x,y)x+y可以标识所在的副对角线,y-x可以标识主对角线
		//于是我们可以用vis[1][]和vis[2][]分别表示某条主对角线和副对角线是否存在棋子
		//不会有人要问这里加n的问题吧,不会吧不会吧 
		if (!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n]){
			C[cur]=i;//如果需要打印解,C用于存储整个方案路径 
			vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=1;//表示当前棋子落下对整个棋盘造成的影响
			search(cur+1);  vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=1;//回溯回原本的状态 
		}
	} 
} 

如果只需要一个可行的方案，有较为不同的写法，后面有对这种问题的介绍。

poj 2531 “Network Saboteur”

给你n个点以及n个点两两之间的间距，求最优的方案将n个点分为两组A，B两组，使得∑Cij (i∈A,j∈B,Cij表示点i与点j之间的距离)最大。

分析：这道题确实可以用深搜去做······，但是事实上用深搜去做就是将所有的方案枚举出来求出∑Cij (i∈A,j∈B,Cij表示点i与点j之间的距离)的值找到一个最大值。

然而我们发现这里所有的方案有多少种？2²⁰/2≈520000种，这意味着什么呢？意味着直接枚举子集就能解决这个问题了。

但还是写了深搜的做法。

#include<iostream>
using namespace std;
int n,dis[21][21],vis[21]={0},ans=0;//vis[i]表示第i个点是否在集合A中 
void dfs(int pos,int s){vis[pos]=1; int t=s;//当第i个结点从集合B移动到集合A中
	//总距离和的值减小该点到集合A原先点的距离和,增加该点到集合B原先点的距离和 
    for (int i=1;i<=n;i++) t+=dis[pos][i]*(0.5-vis[i])/0.5;//我喜欢的一种写法,大家自己看一下咯 
    if (t>ans) ans=t;//更新ans的值 
    if (t>s) for (int i=pos+1;i<=n;i++) dfs(i,t);//保留当前的总距离和考虑当前元素后面的元素 
    vis[pos]=0;//回退到原本的结点 
}
int main(){cin>>n; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) cin>>dis[i][j]; 
	dfs(1,0); cout<<ans; return 0;//默认最开始所有的点都在集合B中 
} 

(我除了枚举子集的做法还看到有一个图论的做法，恐怖如斯emmm)

poj 1416 “Shredding Company”

给定两个数n和m，要把m拆开成若干个数，求所有拆法中若干个数的和小于n的最大值。其中如果n与m相同，则不必拆分；如果任何拆法都会使得和大于n，输出“error”；如果有多于1种拆法取得最大值，则输出“rejected”。

分析：也是暴力搜索，我在别人博客看到一个暴力搜索的搜索树：

省略号为未列出的结点。

相当于将每两个数之间的空隔看作上一个问题的位数。代码类似就不多做复写了。

poj 2676 “Sudoku”

简而言之，解决数独问题。

分析：不断找0填空的深搜，这个问题就是我前面提到的只输出一种答案的结果，dfs返回的类型为bool型，对全局变量进行操作，当遇到一种可行的结果直接返回true。

#include<iostream>
#include<cstring>
using namespace std;
char a[10][10];//row[i][num]表示第i行是否有num,col[j][num]表示第j列是否有num 
int row[10][10],col[10][10],group[4][4][10];//group将9*9的格子分成了3*3的group板块 
bool dfs(int x,int y){if (x==10) return true;//如果深搜到了不存在的第十行,表示前面的全部填满,返回true 
	if (a[x][y]!='0') return dfs(x+y/9,(y==9)?1:y+1);//深搜到为0的方格进行填充
	//num表示填充进的数字,填充进的数字需要满足同行同列同板块没有相同的数字 
	for (int num=1;num<=9;num++) if(!row[x][num]&&!col[y][num]&&!group[(x-1)/3+1][(y-1)/3+1][num]){		
		row[x][num]=1; col[y][num]=1; group[(x-1)/3+1][(y-1)/3+1][num]=1; a[x][y]=char(a[x][y]+num);
		if (!dfs(x+y/9,(y==9)?1:y+1)){//如果深搜的结果不成功,回溯到前面进行修改 
			row[x][num]=0; col[y][num]=0; group[(x-1)/3+1][(y-1)/3+1][num]=0; a[x][y]=char(a[x][y]-num);
		}else return true;//成功则直接返回true,dfs在if的括号里面进行了 
	}return false;//9个数字都不成功返回false 
}
int main(){int n; cin>>n; for (int x=1;x<=n;x++) {
		memset(row,0,sizeof(row)); memset(col,0,sizeof(col)); memset(group,0,sizeof(group));
		for (int i=1;i<=9;i++) for (int j=1;j<=9;j++){cin>>a[i][j];//初始化 
			row[i][a[i][j]-'0']=1; col[j][a[i][j]-'0']=1; group[(i-1)/3+1][(j-1)/3+1][a[i][j]-'0']=1; 
		} 
		if (dfs(1,1)) for (int i=1;i<=9;i++){
			for (int j=1;j<=9;j++) cout<<a[i][j]; cout<<endl;
		}	
	} return 0;
} 

除了返回bool型，还有用void，返回NULL，用一个全局变量flag的写法，但相较起来会复杂一点。

poj 1129 “Channel Allocation”

给定n个节点的无向图，求最少的颜色数量对无向图的节点染色，保证图中相邻的节点颜色不重复。(原题不是这样表述的，我也是翻看的别人的翻译和解析)

分析：这个问题的求解和DFS没什么关系，实际上是一个典型的图着色问题，最优的求解方法不是DFS回溯暴搜，而是贪心：

将无向图的结点按照度数(相邻点个数)递减的次序排列.

用第一种颜色对第一个结点着色，并按照结点排列的次序，对与前面着色点不相邻的每一点着以相同颜色。

用第二种颜色，第三种颜色······对尚未着色的点重复步骤，直到所有点着色完为止。

hdu 1175 “连连看”

题面请点击这里

分析：这个问题我开始的时候想复杂了，以为是要消除掉“连连看”中所有的格子，事实上只是给定你个图，问你这个图中某两个点是否存在一条不超过两个转弯的路径能够连通。

由于需要判断路径转弯的个数，需要增加两个属性，一个属性保存路径上一个节点的运动方向，另一个属性保存路径已有的转弯个数，通过上一个结点的运动方向，修改已有的转弯个数。

这里的写法就是使用全局变量的写法，测了一下比bool函数的写法要快不少：

#include<iostream>
#include<cstring>
using namespace std;
int n,m,maze[1011][1011],dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}},vis[1011][1011],flag=0;//maze表示连连看的构图
//dir表示方向数组,vis表示是否到达,flag作为全局变量表示是否已经得到连通路 
bool judge(int x,int y){return (x>=1&&x<=n&&y>=1&&y<=m&&vis[x][y]==0);}//judge用于判断扩展的结点是否合法
//不过需要注意的是,如果将maze的判断添加到这里的判断会让整个dfs的时间复杂度增加很多(我也不知道为什么) 
//(a,b)表示当前位置坐标,(c,d)表示目标位置坐标(可以设置为全局变量),t表示已经进行的拐弯次数,di表示上一次运动的方向 
void dfs(int a,int b,int c,int d,int t,int di){if (flag||t>2) return;//已经找到通路了,return,拐弯次数大于2,return 
	if (a==c&&b==d) {flag++; return;}//找到目标结点 
	if (maze[a][b]!=0&&di!=-1) return;//路径上非起点和终点的结点上不能有值,起点对应的di为-1 
	if (t==2&&a!=c&&b!=d) return;//这里是一个剪枝,如果没有了多余的拐弯次数且当前位置和目标位置不在同一行或者同一列
	//代表没有可能在不改变方向的情况下到达目标节点,于是直接return 
	for (int i=0;i<4;i++) if (judge(a+dir[i][0],b+dir[i][1])){//扩展结点 
		vis[a+dir[i][0]][b+dir[i][1]]=1;//扩展出来的结点进行标记 
		dfs(a+dir[i][0],b+dir[i][1],c,d,t+(di!=-1&&i!=di),i);//如果di=-1表示当前在起点,不存在方向不一样的情况 
		vis[a+dir[i][0]][b+dir[i][1]]=0; if (flag) return;//回退到扩展之前的状态,这个flag的添加并没有太大的意义 
	} return;
}
int main(){
	while (cin>>n>>m&&n!=0&&m!=0){for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) cin>>maze[i][j]; 
		int q,x0,y0,x1,y1; cin>>q; 
  		for (int i=0;i<q;i++){cin>>x0>>y0>>x1>>y1; 
  		//预先判断一下初始节点和目标结点的值是否相等,如果不相等或者非法(为0)直接输出NO 
   		if (maze[x0][y0]!=maze[x1][y1]||!maze[x0][y0]||!maze[x1][y1]){cout<<"NO\n"; continue;}
			memset(vis,0,sizeof(vis)); vis[x0][y0]=1; flag=0;
	  		dfs(x0,y0,x1,y1,0,-1);  (flag)?cout<<"YES\n":cout<<"NO\n";
 		}
 	} return 0; 
} 

hdu 5113 “Black And White”

有N*M个格子的棋盘，用K种颜色去涂，相邻格子不能同色。给定每种颜色要涂的格子数，如果能满足题意，则输出YES和任意一种涂法，不能输出NO。

分析：从左到右从上到下深搜即可，问题在于如何回溯剪枝，如果对于某个颜色当前剩余的格子数不够进行染色，即当前剩余的格子数/2<某颜色剩余需要染色的格子数，直接return。

代码和上题几乎完全相等就不多做赘述，问题主要在于如何有效的剪枝。

4.4.3 迭代加深搜索

对于有些问题，它搜索树的某些分支非常深甚至可能到无穷，搜索树的宽度也极广。如果直接用DFS，可能会陷入DFS某个分支的递归无法返回，直接用BFS，队列空间可能会爆炸。

于是我们可以在每次进行DFS之前，限定DFS的深度，初始化为1，如果深度为1的DFS找不到答案，再进行最大深度为2的DFS······直到找到答案。

这个算法思想我们叫做IDDFS。

4.4.4 IDA*

首先要知道的是IDA*是IDDFS的优化，很多博客直接把IDDFS当作了IDA*，A*是BFS算法添加了一个启发函数的优化，IDA*则相当于A*算法思想在IDDFS中的应用。

说简单点就是给IDDFS中的DFS添加一个估价函数来进行剪枝。

poj 3134 “Power Calculus”

给定数x和n，求x的n次方，只能使用乘法和除法，算过的结果可以被利用，求最少算多少次。

分析：这道题如果用BFS或者A*求最短路会出现一个问题，就是新的值是指数级的增长，可扩展的方向指数级的增加。直接用DFS，由于没有步骤数的限定，深度很可能过长。

于是考虑用IDA*，估价函数即判断在当前的情况用最快的倍增能否得到n，这道题在紫书竞赛题目选讲那里做到过，不多作赘述。

#include<cstdio>
int n,maxd,A[1010];//存储得到值的上标 
bool IDA(int d,int now){//d表示准备扩展的结点的搜索深度,now表示经过d次运算得到的结果 
    if (d>maxd||now<=0||now<<(maxd-d)<n) return false;//now<<(maxd-d)<n就可以理解为估价函数
	//如果当前的上标,剩余的步骤数全部进行翻倍也无法得到最终的目标,就直接进行剪枝 
    if (now==n||now<<(maxd-d)==n) return true;//这里还进行了一个小小的剪枝,和上面的剪枝是一样的 
	A[d]=now;//将d次运算得到存储到A数组里面去,A[i]表示在当前分支下进行i次运算得到的结果(上标) 
    for (int i=0;i<=d;i++){//扩展结点,对前面的结果进行相乘或者相除
		//由于这里将赋值的过程放到扩展结点之前,于是不需要进行回退 
        if (IDA(d+1,now+A[i])) return true; if (IDA(d+1,now-A[i])) return true;
    } return false;
}
int main(){//maxd表示IDDFS限定的最大搜索深度,当某个深度可以得到n时,直接打印深度 
    scanf("%d",&n); for (maxd=0;!IDA(0,1);maxd++); printf("%d",maxd); return 0;
}

属于比较简单的一个IDA*。

hdu 1560 “DNA sequence”

找到一个最短的序列，使得输入的所有序列都能在这个序列中按照原本序列的顺序依次找到。输出最短序列的长度。

假设给定的“ACGT”，“ATGC”，“CGTT”，“CAGT”，得到的序列如下：

分析：同样的，用DFS不能确定某个分支的深度，至于BFS和A*······(DNA序列只会由ACGT四个字母组成，我也不太清楚有没有优秀的A*解法，搜到一个解法效率好像不如IDA*)。

估价函数比较简单，即是n个序列还没有匹配的位数的最大值。代码如下：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;//pos[i]存储第i个DNA序列匹配了多少位,maxd为限制的最大搜索深度 
int n,maxd,pos[10]; string dna[10]; char c[]="ATCG";//c数组相当于方向数组 
int f(){int x=0;//f为估价函数,将每个序列的长度减去对应的pos值,得到还需要匹配多少位 
	for (int i=0;i<n;i++) x=(dna[i].size()-pos[i]>x)?dna[i].size()-pos[i]:x;
	return x;//估价函数返回n个序列中还需要匹配的最多位数 
}
bool IDA(int d){int max_x=f(); if (d+max_x>maxd) return false;//如果剩余的步骤数不够匹配直接false 
	if (!max_x) return true;//如果需要匹配的最大位数为0,即相当于需要匹配的位数全为0,该长度匹配成功 
	int tmp[10],flag; for (int i=0;i<n;i++) tmp[i]=pos[i];//这里的回退状态不太简单,考虑新建一个tmp数组存储原始状态 
	for (int i=0;i<4;i++){flag=0;//flag表示新添的一位对匹配是否有效
	//否则可能会出现类似于"AAAAAAAAA···"的情况降低效率
	//接下来对每一个序列的下一位进行匹配,如果相等pos值+1 
		for (int j=0;j<n;j++) if (c[i]==dna[j][pos[j]]) {pos[j]++; flag=1;}
		if (flag){
			if (!IDA(d+1)) for (int j=0;j<n;j++) pos[j]=tmp[j];//回退到原本状态 
			else return true;
		}
	}return false;//我仔细想了一下这个问题的这种情况基本不存在 
}
int main(){int t; scanf("%d",&t);
	while (t--){scanf("%d",&n); maxd=0;
		for (int i=0;i<n;i++) {cin>>dna[i]; maxd=(maxd>dna[i].size())?maxd:dna[i].size();}
		//由于得到的序列的长度一定大于等于n个序列的长度,将限制的最大搜索长度设置为n个序列长度的最大值 
		memset(pos,0,sizeof(pos));//IDDFS深度不断迭代 
		for (;!IDA(0);maxd++); printf("%d\n",maxd);
	} return 0;	
} 

还有一道例题也在竞赛题目选讲那里介绍过了IDA*的解法(我当时还吐槽了一下)，也不多做赘述了。

总结

总结一下就是，如果要求最优路径考虑用A*(前提是你写的出估价函数)，如果需要求出全部的结果考虑用DFS。

如果这个问题搜索树庞大，又宽而且很多分支的深度无法确定，考虑用IDA*(前提也是你写得出估价函数)。

很多博客将IDA*记作A*的优化，事实上A*相当于BFS和贪心的结合，IDDFS相当于不断扩展长度的DFS，即DFS和BFS的结合(我觉得这么说很牵强)，IDA*和A*没有太大的关系，只是相当于在IDDFS的DFS过程中添加了一个类似于A*的估价函数来进行剪枝。

我个人认为，如果不是搜索树过宽并且深度不确定，就不要考虑用IDA*了。