DFS

深度优先搜索。

深度优先，即每一次均搜索一条完整的从起点到达终点的路径，然后继续搜索第二条。

原始支持有权图搜索。

一般情况下，通常使用递归的方式实现。

具体流程为，对于当前节点，循环遍历下一个目标节点，对于可能的目标节点调用递归函数，直到终止条件。

状态一般包括step，记录决策的数组等，可以放在全局变量中（注意回溯时需要回退全局变量）。

剪枝

剪枝就是切掉一部分无用的搜索树，起到优化复杂度的作用

1. **记忆化：**dfs函数中传入相同的状态往往会得到一样的解，所以用数组记录下对应每个状态的答案，若之前已求得直接返回即可。

2. **求代价和最小：**若转移时代价非负，则若目前的代价和已经大于等于之前的最小答案，直接返回。

3. 更改转移的枚举顺序

启发式搜索

当搜索到一个状态u时，计算估价函数 $f(u)$ 的值：

• 对于转移需要代价的题目，$f(u)$ 代表转移到末状态的最小代价，如果走到u状态的代价 $g(u)+f(u)>ans$ 则剪枝

• 对于转移得到收益的题目，$f(u)$ 表示可能的最大收益，如果 $g(u)+f(u)≤ans$ 则剪枝

A*

估价函数同启发式搜索，但是我们用优先队列进行类广搜,每次取出 $f(x)+g(x)$ 最小的 $x$，然后更新相邻的状态。

IDA*

迭代加深A*，仅仅是添加了限制层数。

DFS生成树

在一个有向图中，以DFS的方式选取某一节点进行搜索而形成的树+边的结构。

举个栗子：

我们先看一个有向图：

用DFS跑图，就可以得到一下这个：

我们可以以树形结构将图中的边分为四种：

• 树边：每个节点第一次被访问时经过的边，整体称为搜索树。

• 返祖边：从子树中的节点到其父亲节点的边。

• 前向边：从父亲节点直接指向儿子(也可以是孙子等)节点的边。

• 横叉边：搜索的时候遇到了一个已经访问过的结点，但是这个结点并不是当前结点的祖先时形成的。(看不懂？流氓定义：如果这条边不是上面三种，那就是横叉边)

DFS序

字面意思，很好理解，就是用DFS前序遍历一棵树上所有节点和边时访问的顺序。

我们知道，树是一种非线性的数据结构，它的一些数据调用肯定是没有线性结构来得方便的。所以这个时候，dfs站了出来。

如图，这是一棵树：

所以，整了一大顿，这DFS序到底有啥子用？这得从DFS的优势来探讨了。

DFS是深度优先的，所以对于一个点，它会先遍历完它的所有子节点，再去遍历他的兄弟节点以及其他子树的节点。

因此DFS序保证了一棵树(子树)的根节点和其子树中所有的节点会被存储在连续的区间之中。

比如，以 $5$ 为根的子树中节点编号为 $5\sim8$。

这样，我们把一个非线性的数据结构——树，成功转化为了一个线性的数据结构，然后……请自行选择。

But! 我们现在还有一个问题：

如何直到我的子树区间到哪？别搞出去就不好了。

欲知详情，请接着看 -_-

时间戳

这玩意好比一个标签，贴在每一个点上，记录dfs第一次开始访问这个点的时间以及最后结束访问的时间。

我们发现，节点 $i$ 的DFS序其实是DFS第一次访问节点 $i$ 的时间，因此我们只需要记录最后结束访问的时间即可。

实现很简单，循环完儿子之后(回溯之前)记录一下当前最大DFS序值即可。

这样，我们成功的把一棵树变成了一段段的区间：

BFS

广度优先搜索。

广度优先，即每一次都搜索距离起点相同长度的点，然后继续搜索长度 $+1$ 的点，直到搜索到终点。

原始不支持有权图，但可以使用算法优化。

一般情况下，通常使用队列的方式实现。

具体流程为，先将起始节点推入队列，每次循环弹出队首元素，将其加入以搜索的点集，并将与之连接的未加入以搜索的点集的点推入队列尾部，直到找到终点或者队列为空。

双向BFS

要求 $S$ 状态到 $T$ 状态的最小转移次数，从 $S$，$T$ 分别同时出发进行BFS，直到BFS到的点相遇为止。

理论上将深度为 $n$ 的搜索树拆分成了两棵深度为 $\frac{n}{2}$ 的搜索树 。若决策个数为 $k$，搜索树大小由 $k^n$ 优化为 $2\times k^\frac{n}{2}$。

如何判断一个局面（状态）是否被访问过？可以将全局状态变成一个整数，用map或unordered_map记录该整数是否出现过。

三个要素

• 状态：怎么表示？要求包括全部信息、能够标记是否已访问。
• 转移：转移后的状态计算，转移代价计算。
• 优化：剪枝（剪掉无用的搜索子树），修改搜索顺序，估价函数。