Algorithm Miscellany - Search

A* 算法#

A* 算法的目标是找到有向图上从起点 $s$ 到终点 $t$ 的最短路径。设 $d(x, y)$ 为结点 $x$ 与 $y$ 之间的距离，也就是它们之间最短路径的长度。记 $g(x) = d(s, x)$ 为从起点 $s$ 到结点 $x$ 的距离函数，$h^{*}(x)$ 为从结点$x$到终点$t$的距离函数，$h(x)$为$h^{*}(x)$的一个估计。最后，记从$s$出发经由$x$到达$t$的最短路径长度的估计为

$$f(x) = g(x) + h(x)$$

搜索时，$A^{*}$ 算法每次从优先队列中取出一个 $f$ 最小的结点。然后，将它的所有后继结点 $x$ 都推入优先队列中，并利用实际记录的 $g(x)$ 和估计的 $h(x)$ 更新 $f(x)$。

性质#

由于 $h^{*}(x)$ 的实际值在搜索的时候是未知的。所以，需要使用容易计算的$h(x)$作为它的估计

假设图没有负权边。如果估计$h(x)$永远不超过实际距离$h^{*}(x)$，即$0\le h \le h^{*}$，那么，$A^{*}$算法就一定能

$$f(x) = g(x) + h(x) \le C^{*}$$

的结点，其中$C^{*}$是

如果$h$不仅是可采纳的，还是一致的，即

$$h(x) \le h(y) + d(x, y)$$

那么，$A^{*}$算法不会将已经弹出队列的结点再次加入队列。

迭代加深搜索#

迭代加深搜索的本质还是深度优先搜索，只不过在搜索的同时带上了一个深度$d$，当$d$达到设定的深度时就反回，一般用于找最优解。如果一次搜索没有找到合法的解，就让设定的深度加一，重新从根开始。

过程#

首先设定一个较小的深度作为全局变量，进行DFS。没进入一次DFS，将当前深度加一，当发现$d$大于设定的深度$limit$就返回。如果在搜索的途中发现了答案就可以回溯，同时在回溯的过程中可以记录路径。如果没有发现答案，就返回到函数入口，增加设定深度，继续搜索。

$IDA^{*}$#

$IDA^{*}$算法是迭代加深搜索的一种变形。迭代加深搜索在每次DFS中限制深度，而$IDA^{*}$限制单次$DFS$的路径成本

在一次迭代中

Dancding Links#

Alpha-Beta剪枝#

Minimax算法#

Minimax算法又叫极小化极大算法，是一种最小化最差情境下的潜在损失的算法

Alpha-Beta剪枝#

Alpha-Beta剪枝是针对Minimax算法的搜索剪枝

剪枝#

最常用的剪枝有三种:记忆化搜索、最优性剪枝、可行性剪枝

记忆化搜索#

因为在搜索中，相同的传入值往往会带来相同的解，那我们就可以使用数组来记忆

最优性剪枝#

在搜索中导致运行慢的原因还有一种，

可行性剪枝#

在搜索过程中当前解已经不可用了还继续搜索下去也是运行慢的原因

剪枝思路#

剪枝思路有很多种，大多需要对于具体问题来分析，在此简要介绍几种常见的剪枝思路

• 极端法:考虑极端情况，如果最极端的情况都无法满足，那么肯定实际情况搜出来的情况不会更优了
• 调整法:通过对子树的比较剪掉重复子树或者明显不适最有前途的子树
• 数学方法:比如在图论中借助连通分量，数论中借助模方程的分析，借助不等式的放缩来估计下界等等