通过搜索进行问题求解

搜索策略

搜索策略可以大致分为两种：有信息搜索（启发式搜索）和无信息搜索。

常用的搜索方式如下：

• 最佳优先搜索（BeFS）
• 广度优先搜索（BFS）
• 深度优先搜索（DFS）
• 一致代价搜索（UCS）
• 深度受限搜索（DLS）
• 迭代加深搜索（IDS / IDDFS）
• A*搜索

常用于评估搜索算法的几个指标如下：

• 搜索树的最大分支因子b - 每个节点最大有几个分支
• 最小代价解的深度d
• 状态空间的最大深度m

1. 最佳优先搜索

最佳优先搜索本质上是一种启发式搜索。它将待搜索节点队列以启发函数f(node)排序，以找到离目标代价最小的路径。

2. 广度优先搜索

• 完备性: 是 （若b有限）
• 时间：$\sum_{i = 1}^{d} b^i$
• 空间：$\Omicron(b^d)$（所有节点均存在内存中）
• 代价最优（仅当所有动作具有相同代价）

3. 深度优先搜索

• 完备性：否（无限 / 有环状态空间）
• 时间：$\Omicron(b^m)$ - 如果解密集，可能快于BFS
• 空间：$\Omicron(bm)$ - 线性空间
• 代价最优：否（会先返回左边的解）

4. 一致代价搜索

• 完备性：是（假设没有负权边）
• 时间：最坏$\Omicron(b^{\frac{C^*}{\epsilon}})$, C*为最优解的代价
• 空间：最坏$\Omicron(b^{\frac{C^*}{\epsilon}})$
• 代价最优：是

5. 深度受限搜索

在DFS的基础上限制搜索深度只能为l。

适用于最大深度较大的状态空间中的搜索。

6. 迭代加深搜索

运用多次深度限制不断增大的DLS进行图的搜索。

7. A*搜索

主要思想：避免扩展代价已经很高的路径。

A*搜索在BFS的基础上将待搜索队列用f(n) = g(n) + h(n)排列； 其中g(n)是从起点到当前节点的已知代价，h(n)是当前搜索使用的启发函数。

对于 可容许的启发函数，A*搜索是代价最优（能够找到代价最小的解节点）的：

一个启发函数是可容许的，当且仅当$h(n) \le h^*(n)$。其中$h(n)$是当前讨论的启发函数，$h^*(n)$是经过节点n到目标状态的真实代价。

加权A*搜索

加权A*搜索使用的排序公式如下： $f(n) = g(n) + W \cdot h(n), W > 1$

加权A*搜索并不一定能找到最优解，但可能会以更小的时间找到一个次优解。

局部搜索、最优化

如果状态空间非常大，甚至是无穷大，我们可以采用局部搜索算法进行问题的求解。 注意：局部搜索算法并不是系统性的——它们可能永远不会搜索解所在的那部分状态空间。

1. 爬山算法

爬山算法每次用当前状态周围某个更优的状态替换当前状态，但它无法解决局部极大值及平坦区域的问题。

2. 模拟退火

模拟退火算法在爬山算法的基础上做出了改进，允许“下坡”的情况出现。