DFS

深度优先搜索（ \(Depth\) \(First\) \(Search\) ）其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.

特点

  • 每次寻找下一个节点的过程是重复的
  • 如果当前节点没有未访问过的后继节点，则需要回溯到有未访问过的后继节点的一个先驱节点，继续遍历

形象化描述：不撞南墙不回头

\(DFS\) 一般通过递归来实现，本质上用栈来维护。

大部分 \(DFS\) 算法分为三部分：

  1. 判断当前位置是否合法（是否为边界）
  2. 处理信息
  3. 访问下一个位置

剪枝

最优化剪枝

设 \(g(x)\) 表示从起点走到节点 \(x\) 能获得的价值，估价函数 \(f(x)\) 为从节点 \(x\) 走到终点能获得的最大价值。

如果 \(g(x)+f(x)<\) 当前的已经找到的解，则说明从节点 \(x\) 走下去一定得不到最优解，可剪去此分支。

洛谷P1074 [NOIP2009 提高组] 靶形数独

靶形数独每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）

每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。

求出对于给定的靶形数独，能够得到的最高分数。

对于 \(100\%\) 的数据，数独中非 \(0\) 数的个数不少于 \(24\)。

如果当前得到的分值+之后可能得到的最大的分值还是小于之前的最优答案，结束

可行性剪枝

如果当前位置不合法，则返回

洛谷P1025 [NOIP2001 提高组] 数的划分

将整数 \(n\) 分成 \(k\) 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：\(n=7\)，\(k=3\)，下面三种分法被认为是相同的。

\(1,1,5\);
\(1,5,1\);
\(5,1,1\).

问有多少种不同的分法。

（\(6<n \le 200\)，\(2 \le k \le 6\)）

\(dfs(x,r,l)\) 表示当前正在分第 \(x\) 份，剩余 \(r\) 没有划分，上一份大小为 \(l\)

当 \(r<0\) ，说明当前及之后所有位置全部放上个位置的数时，仍比剩余可分配的数要小，退出

优化搜索顺序

让不合法的情况在一开始就被剪掉

洛谷P1074 [NOIP2009 提高组] 靶形数独

从剩余未填格最少的一行或一列开始填

记忆化搜索

如果当前位置之后的信息全部处理过了，就可以直接利用这些信息

洛谷P1434 [SHOI2002] 滑雪

Michael 喜欢滑雪。可是为了获得速度，滑的区域必须向下倾斜。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：

1   2   3   4   5
16  17  18  19  6
15  24  25  20  7
14  23  22  21  8
13  12  11  10  9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 \(24\)－\(17\)－\(16\)－\(1\)（从 \(24\) 开始，在 \(1\) 结束）。当然 \(25\)－\(24\)－\(23\)－\(\ldots\)－\(3\)－\(2\)－\(1\) 更长。事实上，这是最长的一条。

对于 \(100\%\) 的数据，\(1\leq R,C\leq 100\)。

记录从每个点开始的最长滑坡是多少

玄学剪枝

洛谷P1120 小木棍

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 \(50\)。

现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

\(1 \leq n \leq 65\)，\(1 \leq a_i \leq 50\)。

  1. 原始长度枚举到 所有木棍的长度和 \(/2\) 即可，因为此时所有木棍有可能拼成2根木棍，原始长度再大的话只能是所有木棍拼成1根。

  2. 优化搜索顺序: 对输入的所有木棍按长度从大到小排序，从长到短地将木棍拼入。

  3. 玄学 \(next\) 数组：当dfs返回失败，需要更换当前使用的木棍时，不要再用与当前木棍的长度相同的木棍。预处理出了排序后每根木棍后面的最后一根与这根木棍长度相等的木棍（程序中的next数组），它的下一根木棍就是第一根长度不相等的木棍了。（去重）

  4. 可行性剪枝: 只找木棍长度不大于未拼长度rest的所有木棍。(二分)

  5. 如果 **当前长棍剩余的未拼长度 **等于 当前木棍的长度或原始长度 ，继续拼下去时却失败了，就直接回溯并改之前拼的木棍。

​ 1) 当前长棍剩余的未拼长度等于当前木棍的长度时，这根木棍在最优情况下显然是拼到这（如果用更多短木根拼完剩下的这段，把这根木棍留到后面显然不如把更多总长相等的短木棍扔到后面）。如果在最优情况下继续拼下去失败了，那肯定是之前的木棍用错了，回溯改即可。

​ 2) 当前长棍剩余的未拼长度等于原始长度时，说明这根原来的长棍还一点没拼，现在正在放入一根木棍。很明显，这根木棍还没有跟其它棍子拼接，如果现在拼下去能成功话，它肯定是能用上的，即自组或与其它还没用的木棍拼接。但继续拼下去却失败，说明现在这根木棍不能用上，无法完成拼接，所以回溯改之前的木棍。

#include<iostream>
#include<algorithm>
using namespace std;

int n,S,L,cnt;
int a[71],next[71];
bool v[71];

void dfs(int x,int last,int rest){
	if(!rest){
		x++,rest=L;
		for(int i=1;i<=n;i++)
		if(!v[i]&&a[i]<=rest){
			v[i]=1;
			dfs(x,i,rest-a[i]);
			v[i]=0;

			if(rest==a[i]||rest==L) return;
			i=next[i]+1;
			if(i>=n) return;
		}
	}
	if(x>=cnt) {cout<<L<<endl,exit(0);}
    
	for(int i=last+1;i<=n;i++)
		if(!v[i]&&a[i]<=rest){
			v[i]=1;
			dfs(x,i,rest-a[i]);
			v[i]=0;

			if(rest==a[i]||rest==L) return;
			i=next[i];
			if(i==n) return;
		}
}

int main(){
	int i,k;
	cin>>cnt;
	for(i=1;i<=cnt;i++){
		cin>>k;
		if(k>50) continue;
		a[++n]=k,S+=k;
	}
	sort(a+1,a+n+1,greater<int>());

	next[n]=n;
	for(i=n-1;i>=1;i--)
		if(a[i]==a[i+1]) next[i]=next[i+1];
		else next[i]=i;
	for(L=a[1];L<=S/2;L++){
		cnt=S/L;
		if(S%L) continue;
		v[1]=1;
		dfs(1,1,L-a[1]);
		v[1]=0;
	}
	cout<<S<<endl;

	return 0;
}

BFS

广度优先搜索（\(Broad\) \(First\) \(Search\) ）是一种分层的查找过程，每次将下一层的所有节点加入待访问队列，不像深度优先搜索有回溯的过程。

同时与深搜用栈来维护不同，广搜一般是用队列来进行维护的。

具体操作：它是先将起始状态加入队列，然后每次从队列中取出一个状态，将其后继状态加入队列（后继状态指的是由当前状态一步操作可以到达的状态），直到所有状态均被访问为止。

特点

  1. 它并不考虑结果的可能位置，而是彻底地搜索所有状态，所以很少有基于 BFS 的启发式算法，也很少对 BFS 进行剪枝。

  2. 相对于 DFS，BFS 更加难于保存当前节点的状态，所以 BFS 在爆搜中的应用较少。

  3. 在某一层还没有搜索完时，是不会进入下一层的，也就是说在队列中所有同一深度的状态，是连续的一段。

一般的代码实现方式：

BFS(){
    q.push(初始状态);
    while(!q.empty()){
        u=q.front();  取出队首元素
        遍历所有相邻且未加入队列的元素
        {
            处理信息
            q.push(); 加入队列
        }
    }
}

求最小步数一类的题目一般使用 \(BFS\)