一个well-defined的搜索问题包括下面的组成部分：

• 初始状态
• 操作算子: 用于状态转换
• 目标
• 路径代价函数

即从初始状态出发, 扫描操作算子集, 选取适当的操作算子作用在初始状态上得到新的状态, 新的状态满足目标时终止搜索, 反之以新的状态作为当前状态; 如果最终还需要搜索路径, 那么就在搜索的时候维护搜索树中每个状态的父节点. 在搜索过程中, 我们关注能否找到解, 解的质量, 时空复杂度.

根据搜索方向, 搜索策略可以分为正向搜索和逆向搜索:

• 正向搜索: 实际上就是上面所叙述的搜索过程.
• 逆向搜索: 当操作算子可逆时, 可以从目标出发, 寻找能产生该目标的操作算子以及产生该操作算子需要的条件. 按照该策略不断进行, 直到找到问题给定的条件即可.

根据搜索过程中是否用与问题有关的信息分为盲目搜索和启发式搜索, 启发式搜索可以看作是一种基于经验的贪心策略.

回溯

回溯策略就是从初始状态出发, 不断试探寻找可行的路径, 如果遇到了不可解点时就回溯到距离最近的父节点, 判断其是否还有其他子节点未被扩展.

回溯等同于DFS吗?

如果考虑严格定义的话, DFS本身是在图这一抽象出来的结构上使用的算法; 而回溯则是在拥有上述特征的问题中使用的(或者说, 回溯是搜索问题的特征空间映射得到的的树结构上的DFS), 两者的使用场景其实不太一样. 不过在实际使用的时候, 对DFS和回溯这两个名词其实并没有做明显的区分, 在措辞表达方面可能DFS用得更多一些; 除此之外, 再深究一下回溯定义中的"遇到了不可解点就回溯"这一策略, 这实际上是一种剪枝, 即可以认为回溯相比一般的DFS多了剪枝. 反正没有必要做区分.

BFS和DFS的一些值得注意的地方

1: BFS一定能找到最优解而DFS不一定. 这很好理解, 如果问题对应的搜索树不是有限的, 那么DFS将一直搜下去, 但显然一层一层搜索的BFS一定可以找到最优解.

2: 一个搜索问题必须具备某种特征才能使用BFS求解. 设 表示从起点到节点 的代价(就是文章最开始的路径代价函数), 其中 在搜索树中的层数是 , 那么某个问题能使用BFS求解当且仅当 关于 是递增的. 比较经典的例子是Dijkstra算法无法在有负权环的图上应用, 因为Dijkstra算法本质上就是BFS, 若出现了负权环, 那么就可以在负权环上一直搜索下去(搜索深度增加)而代价始终不增, 也就没有最优解了.

3: DFS的一些改进. 主要是迭代加深搜索, 这个很容易想到, 可能在做题的时候就不经意间使用了: 设定一个深度限制, 记录当前深度, 每迭代一次当前深度加一, 当达到限制还没有找到最优解时便回溯.

和

启发式搜索本质上是基于经验或直觉在每一步选择操作算子时都选择较优的, 达到缩小状态空间的目的. 由于严重依赖经验或直觉, 因此启发式算法往往只能得到次优解 , 甚至一无所获.

对于待搜索节点 , 定义它的估价函数 表示它的"有希望"程度, 那么在搜索时就优先搜索有希望程度更大的的状态; 当然 也可以是"没希望程度", 那么就优先搜索没希望程度更小的状态, 此时搜索的过程相当于最小化 的过程, 这与机器学习中的 loss function 是一样的, 或者说, 本身就是一个 loss function. 实现这种算法往往要使用优先队列. Dijkstra 算法是一个典型的符合该搜索过程的算法, 有时候会把上面的算法称为 A 算法. 搜索过程中碰到重复结点的处理手段类似于 Dijkstra 算法.

对不同的问题 的结构不尽相同, 但都可以写成 的形式, 其中 表示从起点到结点 搜索所耗费的实际代价, 它衡量了状态在搜索图/树中的深度, 为从结点 到目标状态的最佳路径的估计代价. 在搜索的过程中很容易就能确定, 需要根据题目的具体信息来设计, 不同方案会带来显著不同的效果. 和 的大小决定了搜索过程中盲目搜索和基于经验的搜索所占的比例, 时有利于搜索的完备性但状态空间比较大时代价会很高; 时对于比较复杂的问题往往只能得到次优解但效率会有显著提升.

用 Dijkstra 算法求解最短路时 , 此时必然能找到最优解.

不能保证 A 算法能得到最优解, 能否加上一些条件使其必定能得到最优解呢? 算法是这样的算法. 设 表示结点 到目标状态的最优路径的代价, 若对所有节点 都有 则 A 算法必定能在有限步搜索到最优的解, 这时它称为 算法.

值得注意的是 算法仍然是一类算法, 不同的启发策略仍然有优劣, 那么需要一些标准:

• 完备性: 算法是否能在有限步能搜索到最优解. 所有的 算法都满足.
• 单调性: 启发函数 满足(1) 当 是 的子节点时有 ; (2) .
• 信息性. 当 恒成立时称启发策略 相比 具有更多的信息性. 越大相当于用了题目中的更多信息来使得状态空间更小, 当然更多的信息性带来的计算代价可能会与减小状态空间所带来的益处抵消.

算法完备性的证明:

类似于迭代加深搜索, 可以提出 Iterative-deepening 即 . 不同于迭代加深搜索的深度限制, 给 设置了一个限制 , 初始化为 , 即初始状态(根结点) 对应的估价函数值; 接着不断地以 作为限制进行DFS, 找到最优解则返回最优解, 否则返回所有满足 的 的最小值, 或者说搜索终止边界处的结点的估价函数值中的最小值, 依次更新 , 下面是伪代码:

在 的基础上对使用的内存做改进可以得到 , 基本思路是遗忘掉一些结点, 同时需要用到其他结点的估价函数值来更新当前结点的估价函数值.