搜索问题
graph TB
subgraph 盲目搜索
深度优先
宽度优先
end
subgraph 启发式搜索
A算法
A*算法
end
盲目搜索
深度优先算法
沿着一个路径按照一定规则顺序搜索，直到搜到目标，或者搜到非法值。搜到非法值时，则返回到上一个点。
非法值有两种形式，一种是问题本身定义的非法点（deadend），比如下棋的非法落子点；一种是当前点已经被充分展开，其展开点都被搜索过，最终都是非法点。
深度优先算法有两个问题，对应的解决方法为：
- 深度问题
- 可以对搜索深度加以限制
- 死循环问题
- 记录从初始状态到当前状态的搜索路径
深度优先搜索的性质：
- 一般不能保证找到最优解
- 当深度限制不合理的时候可能找不到解
- 最坏的情况是穷举
- 是一个通用方法，与问题无关
- 节省内存。只储存从初始节点到当前节点的路径。主要是因为按顺序搜索
My Remark：
- 深度优先是一个很好的框架，在这个框架上可以衍生出很多算法。课上给出的LISP写的框架要理解，每一步的作用，为什么这样做。
- 深度优先的典型例子：四王后问题 4Queen
宽度优先算法
优先扩展深度浅的结点
学宽度优先的时候第一次引入了OPEN表和CLOSE表（大概？）那节课没去听不知道怎么讲的。
每一层每一层展开，对于每一层，遍历OPEN表，展开之后把父结点放进CLOSE表中。
宽度优先算法的性质：
- 当问题有解时，一定能找到解
- 当问题为单位耗散值，且有解时，一定能找到最优解
- 与宽度优先一样，有通用性
- 效率比较低
- 储存量大
My Remark
感觉宽度优先不是很有用，特别是问题比较复杂（可能的情况很多）的时候。
迭代加深搜索
宽度优先和深度优先都有明显的缺点，所以就有了这个迭代加深搜索，来解决上述两个方法不能找到最优解的问题。主要思想是给深度优先方法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解，或者遍历全局（反正最后都是有可能遍历全局还找不到解的啊www）。
迭代加深搜索的计算时间分析
对于一个满b叉树，设最佳深度为d，则：
- 宽度优先产生的节点数：
N_{SF}=\sum_{i=0}{d}b{i}=\dfrac{b^{d+1}-1}{b-1} - 迭代加深搜索产生的节点数：
N_{IDBT}=\sum_{i=0}b(d-i+1)bi=\dfrac{b}{b-1}N_{BF}-\dfrac{d+1}{b-1} - b>2\Rightarrow N_{IDBT}<\dfrac{b}{b-1}N_{BF}
启发式搜索
相比盲目搜索的。盲目搜索相当于，要么优先深度，要么优先宽度，按照指定的方法来搜，跟问题没有关系。事实上我们总是能对问题做出一些基础分析，来降低搜索的工作量。这些基础分析，构成启发信息，就是启发式搜索了。所以启发式搜索方法的一个显著优点是可以降低工作量。但是因为有一些引导信息，所以可能找到的解不是最优解。而且由于需要计算启发信息，在最差的情况下，退化成盲目搜索，而且比盲目搜索工作量大（但是很少这么倒霉的啦）。
A算法
定义评价函数：
f(n)=g(n)+h(n)
其中，f(n)为评价函数，h(n)为启发函数
通俗地解释，对于结点n，g是从起点到n的最短路径（严格地说，最短路径的耗散值），h是n到目标点的最短路径的耗散值。定义f为g和h的和，显然这个f是可以评价n这个结点的好坏的。
My Remarks
- A算法的一个例子是8数码问题。从这个例子可以感受到启发式算法还是很神奇的。
A*算法
在A算法中，如果满足条件：
$h(n)\leq h^*(n)$
那么称A算法为A*算法。
- A*算法的两个主要结论:
- 如果从初始结点到终点，存在路径，那么A＊一定能找打最优解（可采纳性定理）
- 如果$h2(n)>h1(n)$,那么有$A1$的扩展结点数$\geq A2$的扩展结点数。
- 注意这里，扩展结点数指的是被扩展的结点的个数，也就是说每个结点最多只能被记数一次。
- h函数的生成方法：其中一个方法是，放宽原问题的条件，使原问题变为一个易于求解h的问题，用这个新问题的h＊来代替h。
Vital Remarks
- A算法的停止条件，是到达目标点（h（n）＝0），且目标点的f值在OPEN表中最小。这一点需要特别注意，因为有的时候，虽然达到了目标点，但是并不是最优路径，或者并不是最优目标点。
- 在一些例子中，会发现，有些节点会被多次拓展。这是因为，这个被多次拓展的结点，在第一次被拓展的时候，并不是按照最优路径拓展的。为了避免这种多次拓展，可以采取以下两种方法：
- 对h加以限制。如果h是单调的，那么就可以避免多次拓展。
- h单调的定义：如果一个父结点到子节点的耗散值，大于子节点的h和父结点h之差，或者h＝0，那么h是单调的。（h单调的本质是，任何一个路径，f的变化趋势与g是一致的，不回因为h的变化，使得f和g的变化趋势不同。）
- h单调是A＊算法的必要条件。（由h单调的定义，用反证法可以轻易证明。）
- 对算法进行修正。修正过程A：令$f_m$是目前已经扩展的结点中，最大的f。在进行下一步拓展时，选取f值比$f_m$小的结点，形成NEST表。选取NEST表中g值最小的点进行拓展。
- 由于h＝0时，h是单调的，所以修正过程A中的h也是单调的，也就避免了重复扩展的问题。
- 对h加以限制。如果h是单调的，那么就可以避免多次拓展。
