盲目搜索

特点：

采用固定的规则来选择下一个的状态
不会随着要搜索解决的问题的变化而变化
不考虑任何与要解决的问题领域相关的信息

宽度优先：把新扩展的后继状态放在边界的最后。在状态树中按照层数依次遍历每个状态。

具有完备性和最优性
时空复杂度 $O(\text{next state}^{\text{depth} + 1})$
空间需求是瓶颈

深度优先：把新扩展的后继状态放在边界的最前面。

不具备完备性（例如存在无限的路径），不具备最优性（最先发现的不一定最优）
时间复杂度 $O(\text{next state}^{\text{depth}})$，空间复杂度 $O(\text{next state}·\text{depth})$
通常比宽度优先更快地找到可行解

一致代价：维护边界中的路径按照成本升序排列，每次拓展成本最低的路径。

当每个动作的成本一样时，等同于宽度优先。
具备完备性（在有限时间内能找到最短路径）、具备最优性（最先发现的一定最优）
时空复杂度 $O(\text{next state}^{\text{depth} + 1})$

深度受限：预先限制搜索的深度 $L$，在深度优先的过程中始终保持深度 $\le L$

避免了路径无限的问题
只有解路径长度 $\le L$ 时才能找到解
不具备完备性（例如存在无限的路径），不具备最优性（最先发现的不一定最优）
时间复杂度 $O(\text{next state}^{L})$，空间复杂度 $O(\text{next state}·L)$

迭代加深：预先限制 $L = 0$，每次迭代地增加深度限制，对于每个深度限制进行深度受限搜索，直到找到解时停止增加深度限制。

具有完备性和最优性
时间复杂度 $O(\text{next state}^{\text{depth}})$，空间复杂度 $O(\text{next state}·\text{depth})$
比宽度优先的空间小，相比深度优先具有完备性和最优性

双向搜索：同时从初始状态向前与目标状态向后进行搜索，直至状态在中间相遇

具有完备性、最优性（每个动作成本一致的前提下）
时空复杂度均为 $O(\text{next state}^{\text{depth} / 2})$
不适用于向后搜索具有很大难度或者代价很高的问题

Conclusion:

路径检测：每次执行动作的时候，检测拓展的节点和祖先节点均不相等时才扩展，不能出现重复节点。

环检测：每次执行动作的时候，检测拓展的节点和之前扩展的所有节点均不相等时才扩展，不能出现重复节点。

对于一致代价搜索，使用环检测仍能找到最优解。因为如果动作代价都是非负的，那么对于同一节点，后搜索到的路径代价一定比先搜索到的路径代价小。
对于启发式搜索，使用环检测不一定能找到最优解，因为会受到估价函数的印象，对于同一节点，不一定最先找到的路径一定是最优的。

启发式搜索

启发式搜索：

构造一个启发式函数 $h(n)$，用于估计节点 $n$ 到目标节点的成本。
启发式函数随着问题的不同而不同。

启发式函数的例子：直线距离、曼哈顿距离、逆序对数量、错位数量

贪心最好优先搜索：使用启发式函数对边界上的节点进行排序

忽略了初始状态到节点 $n$ 的成本，可能错误进入实际成本很高但 $h(n)$ 很小的节点
不具有完备性，不具有最优性

评价函数：对边界上的节点进行排序的指标 $f(n)$，用于决策下一个扩展的节点。

对于贪心最好优先搜索，$f(n) = h(n)$.

A 搜索：将评价函数改为 $f(n) = g(n) + h(n)$，其中 $g(n)$ 是当前路径的代价，$h(n)$ 是启发式函数，每次扩展评价函数最小的节点。

同时考虑了历史代价与未来可能的代价
如果对于 $h(n)$ 的估计不符实际，或者太大而使得 $g(n)$ 无关紧要，那么将会使得 A 搜索退化为贪心最好优先搜索
不具有完备性和最优性，关键在于设计 $h(n)$.

可采纳启发函数：对于启发函数的估计 $h(n)$，必须不能超过实际的从节点到目标的实际代价 $h^*(n)$，即 $h(n) \le h^*(n)$，我们称这样的启发函数是可采纳的。

采用可采纳启发函数的 A 算法是 $\mathbf{A^*}$ 算法。

迭代加深 $\mathbf{A^*}$ 搜索（$\mathbf{IDA^*}$）：类似于迭代加深，但是用 $f(n)$ 来划定搜索的界限，每次划定的界限单调上升。

时间复杂度 $O(\text{next state}^{\text{depth} + 1})$，空间复杂度 $O(\text{next state} · \text{depth})$
解决 $A^*$ 算法空间复杂度过大的问题
当启发函数是可采纳的时候，该算法满足最优性。

启发式函数的性质

如果 $h(n) < h^*(n)$，那么可能会扩展更多的节点，使得搜索速度变慢，但是不会错过最优解。
如果 $h(n) > h^*(n)$，那么将会使得搜索算法出现误导即跳过了最优点，不能保证总能找到最优解。
当 $h(n) = 0$ 或 $h(n) \ll g(n)$，则算法退化为一致代价搜索 $f(n) = g(n)$。
当 $h(n) \to \infty$ 或 $h(n) \gg g(n)$，则算法退化为贪婪最佳优先搜索 $f(n) = h(n)$。
时空复杂度 $O(\text{next state}^{\text{depth} + 1})$
使用可采纳性启发函数的 A 算法（$A^*$ 算法）一定满足最优性，因为最优解一定在所有成本大于 $C^*$ 的路径之前被拓展到，并且成本 $\le C^*$ 的数量是有限的。

一致性/单调性启发函数：对于启发函数 $h(n)$。如果任意两节点 $n_1, n_2$，均有 $h(n_1) \le c(n_1 \to n_2) + h(n_2)$，其中 $c(n_1 \to n_2)$ 指的是从 $n_1$ 到 $n_2$ 的真实最短路代价，那么我们称 $h(n)$ 具有一致性/单调性。

满足一致性的启发函数一定也满足可采纳性：$$h(n_k) = 0,, h(n_{i - 1}) \le c(n_{i - 1} \to n_i) + h(n_i) \le c(n_{i - 1} \to n_i) + h^*(n_i) = h^*(n_{i - 1})$$
大部分 可采纳的启发式函数也满足一致性
典型例子：路网最短路下采用直线距离为估价函数
环检测的影响：只有具备单调性的启发函数，在进行环检测后仍能保持最优性

构造启发式函数的方法是，建立一个 松弛问题：通过考虑一个比原问题的条件更宽松的问题，将 $h(n)$ 设置为简单问题中到达目标的成本。

定理：松弛问题中的成本是原问题的 可采纳 的启发式函数值。
- 证明：原问题的可行解集一定是松弛问题的可行解集的子集，所以松弛问题的最优解一定比原问题的最优解代价更小。

启发式函数的支配：对于同一问题的两个 可采纳 的启发式函数 $h_1(n) ,, h_2(n)$，如果 $\forall n ,, h_1(n) \le h_2(n)$，那么我们称 $h_2(n)$ 支配了 $h_1(n)$（或者称 $h_2$ 比 $h_1$ 拥有更多的信息）

定理：若 $h_2(n)$ 支配了 $h_1(n)$，那么在 $A^*$ 算法中，$h_2$ 扩展到的节点，$h_1$ 也会扩展到

盲目搜索#

启发式搜索#

启发式函数的性质#

盲目搜索

启发式搜索

启发式函数的性质