第五章 进阶搜索
搜索算法可以枚举所有可能的结果，找到最有结果或者统计符合要求的结果数量。在搜索的过程中，每个过程都有若干决策，所以搜索是一类时空开销都极大的枚举算法。
当实在没能想出更好的解法时，可以考虑使用搜索算法来通过一些数据规模较小的测试点。
状态剪枝
如果将搜索的状态看作节点，状态之间的转移看作边，搜索的过程就构建出了一棵 “搜索树”。所谓 “剪枝”，就是在搜索树上去掉一些枝杈不进行搜索，从而减小时间消耗。
系统地说，剪枝的策略分为可行性剪枝和最优性剪枝两种。但需要指出的是，搜索题目的性质及其灵活，在应用时一定要具体问题具体分析，设计合适的剪枝策略，不必拘泥于所学。
所谓可行性剪枝，就是 “保证当前搜索的状态是合法的”，并且 “从当前状态继续搜索时，至少能找到一个最终解”。
考虑一个最优化问题，在搜索过程中已经得出了一个解 $x$（但不确定它是否是最优的），在某个状态中，发现从当前状态在最优情况下到达终点所得到的解也不优于已得到的解 $x$，则可以直接剪枝返回。这种优化思路被称为最优性剪枝。
“卡时” 的技巧：记录已经搜索的节点数量 $\text{cnt}$，当 $\text{cnt}$ 的值超过一定数量时则停止搜索，直接将目前已经掌握的最佳答案输出。使用卡时技巧带有一些 “赌” 的成分，首先需要赌已经搜索到的最优答案就是最佳答案，其次需要赌搜索次数上限——上限太低可能会漏过最佳答案，而上限过高就会导致程序超时。可以在本地运行程序时构造可能造成超时的极限数据，借助每次 $\text{IDE}$ 运行时间调整确定合适的上限。当然需要考虑到评测机的配置，做一个比较保守的估计。
由于使用 “卡时” 技巧并不一定搜完全部的状态，运气不好的话可能得到错误的答案，但效率高且实现起来较为容易。类似的技巧还有爬山法、模拟退火算法和遗传算法等。
最优性剪枝还有几种策略：
- 使用贪心的方式，将可能性大的决策优先枚举。这样可能可以稍微加快到达最优解的速度。
- 目前状态中，如果可以比较方便的判断出后面任何决策都无法使当前状态相比于已经得到的最优解更有，则可以立刻放弃继续搜索下去。
迭代加深与双向搜索
搜索算法的问题在于搜索深度每增加一层，状态数就会呈指数增长。一般来说，由于大部分问题的搜索时间效率会与搜索层数有关。如果搜索状态分为两部分，分别进行搜索，然后合并结果，使用这一方法可以降低复杂度提升效率。
通过枚举深度进行搜索的方式被称为迭代加深搜索，或者更具体地，迭代加深深度优先搜索，简称为 $\text{IDS}$ 或 $\text{IDDFS}$（$\text{Iterative Deepening Depth-first Search}$）。
考虑将搜索状态分成两部分。分别对于这两部分进行 $\text{DFS}$。这种搜索方式被称为双向深度优先搜索。
考虑从初始状态和目标状态一起开始 $\text{BFS}$。当某一个状态既从初始状态又从目标状态拓展到时，两个状态到该状态的步数和即为答案。从两个状态为起点进行 $\text{BFS}$ 的方法即为双向 $\text{BFS}$。不难发现，两个起点的搜索方向是相对而行的，即一个正着搜一个反着搜，因此被称作双向广度优先搜索。
双向 $\text{BFS}$ 有两种写法，既可以把两个方向的状态放在同一个队列里，同时标记它们是正着搜索到的状态还是反着搜索到的状态；也可以开两个队列分别进行两个方向的搜索，外层用 $text{for}$ 枚举当前经过的步数。一旦队头的步数超过循环所限制的步数，则切换至另一方向进行枚举。
用 std::set 或 $\text{has}$ 的方式来分别存储两个方向已经到达过的状态，就可以在较小的时间消耗下完成对某个状态是否已到达的查询。
启发式搜索
启发式搜索指的是在搜索的过程中，利用问题拥有的信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的。之前提到的 “使用贪心的方式，将可能性大的决策优先枚举” 的策略，就是使用了启发式搜索的思想。
$\text{A}*$算法属于启发式搜索的一类。
对于一个状态 $x$，设 $g(x)$ 是从起点到达 $x$ 的代价；$h^*(x)$ 是从 $x$ 到终点的代价的估计值。注意这个估值一定要比实际情况乐观，也就是估计值，一定不会大于最终的实际距离。又设 $f^*(x) = g(x) + h^*(x)$ 为状态的估价函数。在搜索时，找到 $f^*$ 值最小的状态，优先进行搜索，配合最优性剪枝，可以有效地减去较差分支，提高算法效率。
顺带一提，假设通过 “上帝视角” 知道状态 $x$ 到终点的代价准确值 $h(x)$，则 $f(x) = g(x) + h(x)$，代表的就是总代价。
实际上，$h^*(x)$ 函数可以自行设计。当 $h^*(x) = 0$ 时，算法就退化成了普通的 $\text{BFS}$，当 $h^*(x)$ 越大，算法效率越高，但如果 $h^*(x)$ 的值超过了实际到达终点的代价 $h(x)$，就可能得到一个错误的答案。
还可以将 $\text{A}^*$ 算法的思想和迭代加深搜索结合在一起，变为启发式迭代加深搜索，又称为 $\text{IDA}^*$ 算法。
迭代加深搜索所枚举的搜索上界 $\text{dep}$ 即为总的代价 $f(x)$ 的最大值；而从起点到状态 $x$ 的代价 $g(x)$，即走的步数恰好对应着搜索层数。通过限制代价的方式，限制着搜索的深度。而对搜索宽度的限制是通过 “估价函数” 来进行的。而只有 $f^*(x) = g(x) + h^*(x) \gt dep$ 时，该状态才会被本轮搜索拓展。