人智导 搜索

搜索问题

盲目搜索过于困难的时候，采用一些方法来帮助我们加快搜索进程

深度优先

优先扩展深度更深的节点，略

性质：

• 一般不能保证最优解
• 深度限制不合理时可能找不到解，并且可能退化为穷举
• 是一个通用的算法，并且相对节省内存

宽度优先

优先扩展深度更浅的节点，略

性质：

• 问题有解的时候一定能找到，如果问题是单位耗散值则一定能找到最优解
• 通用算法，但是效率较低，存储量较大

Dijkstra

略

优劣：

• 有解一定可以找到最佳解
• 只考虑了距离起点的具体

启发式图搜索

引入启发知识，用于评估节点到达目标的距离，尽可能减少搜索范围

A算法

评价函数为：

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

其中$g(n)$是点$n$到起点$s$的耗散值估计值，$h(n)$是点$n$到目标$t$的耗散值估计值，真实值分别为$g^{*}(n)$与$h^{*}(n)$

$A$算法伪代码如下，主要为维护$\text{CLOSE}$表与$\text{OPEN}$表：

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

while OPEN is not empty, do:
    n = OPEN.first()
    if n == g 
        return n
    OPEN.pop(n)
    CLOSE.push(n)
    expand(n)
    for child in n.childs()
        if child in OPEN:
            # 标记为m_{k}
            f(child) = min{f(child), f(n) + d(n, child) + h(child)}
        else if child in CLOSE:
            # 标记为m_{l}
            f(child) = min{f(child), f(n) + d(n, child) + h(child)}
            ### important!
            OPEN.push(child) if f(child) change
        else:
            # 标记为m_{j}
            f(child) = f(n) + d(n, child) + h(child)
            OPEN.push(child)
    sort(OPEN, f)     

A*算法

若$A$算法中的启发函数满足条件$h(n)\leq h^{*}(n)$，则得到$A^{*}$算法

放宽了约束条件得到估计值，$A^{*}$算法的优势在与：

• 一定能找到最优解
• 启发信息越少的算法，所拓展的节点越多（不少于信息更多的算法）

对启发函数的评价方式为平均分叉数$b^{*}$，探索$d$层后其与总搜索节点数$N$的关系为：

$$N = \sum\limits_{i=0}^{d}b^{*d} = \frac{1 - b^{*(d+1)}}{1 - b^{*}}$$

一般情况下，$b^{*}$是与问题相关，而与问题的规模关系不大

改进的A*算法

对于$A^{*}$算法，其最大的问题就是CLOSE表中的节点可能再次进入OPEN表中，也即没有在第一次探索到节点的时候就找到其最短路径，会造成重复探索，导致资源的浪费。因此我们需要对启发函数做出如下限制：

改进后有：

• 扩展的节点一定满足$f(n) \leq f^{*}(s)$
• OPEN表中满足$f(n) < f^{*}(s)$的一定会被扩展

再次改进，使用当前被扩展的最大节点来估计$f^{*}(s)$，即$\max(f(n)) \sim f^{*}(s)$，具体来说：

维护一个NEST表，满足$\mathrm{NEST} = \{n_{i}\,|\,f(n_{i}) < f_{m}, n_{i}\in \text{OPEN}\}$，并且在选择的时候优先选择NEST表中$g$最小的节点，如果NEST空了再去OPEN表里面选择，并更新$f_{m}$

其他搜索算法

例如爬山法，随机搜索算法，动态规划等，$h(n) = 0$的时候$A^{*}$算法就变成了动态规划（？

Viterbi算法

Viterbi算法实例

转移方程为：

$$\begin{align*} Q(W_{ij}) = \begin{cases} \min\limits_{k}(Q(W_{(i-1)k}) + D(W_{(i-1)k, W_{ij}})) & i \neq 0 \\ 0 & i = 0 \end{cases} \end{align*}$$