搜索技术

搜索定义

重要性质

• 完备性
• 最优性
• 时间复杂度
• 空间复杂度

盲目搜索

盲目搜索策略

• 都采用固定的规则来选择下一需要被扩展的状态
• 这些规则不会随着要搜索解决的问题的变化而变化
• 这些策略不考虑任何与要解决的问题领域相关的信息

宽度优先

• 具有完备性和最优性
  • 短的路径会在任何比它长的路径之前被遍历
  • 最终可以遍历所有长度为d的路径
• 时间复杂度：$1+b+b^2+b^3+\cdots +b^d=O(b^{d+1})$
• 空间复杂度：$O(b^{d+1})$

深度优先

• 在状态空间无限情况时、状态空间有限但存在回路时不具备完备性
• 在状态空间有限且对重复路径进行剪枝的情况下有完备性
• 存在多条路径时，最先发现的不一定最优，不具有最优性

一致代价搜索UCS

• 按路径成本升序排序
• 总是扩展成本最低的那条路径

深度受限

• DFS但预先限制了搜索深度L
• 无限长度路径不会导致DFS无法停止
• 只有当解路径的长度 ≤ L 时，才能找到解
• 无完备性、最优性
• L为限制最大深度，时间复杂度为$O(b^L)$，空间复杂度为$O(bL)$

迭代加深IDDFS

• 就是在深度受限基础上，迭代地增加深度限制，对每个深度限制进行深度受限搜索
• 找到解时或深度受限搜索没有节点可以扩展时停止当轮迭代，并提高深度限制L

启发式搜索

A搜索

其评价函数由一致代价搜索UCS和贪心搜索Greedy二者的函数之和得到 $f(n)=g(n)+h(n)$

• g(n)表示：从起始节点到当前节点 n 的实际路径代价 g=gone
• h(n)表示：从当前节点 n 到目标节点的估计代价，不是已经真实算出来的值，所以它叫启发函数。可以把“到终点的直线距离”当作 h(n) h=heuristic
• f(n)表示：经过节点 n 到达目标的总代价估计，前者g(n)表示已经付出的成本，h(n)表示未来还要付出的估计成本

• 比如此练习题中h(n)为启发式估计值，表示所有方块到其目标位置的曼哈顿距离之和
• g(n)表示已经经过了多少步推理
• UCS 本质上就是 Dijkstra 算法在状态空间搜索中的表现形式。两者都按照从起点到当前节点的累计路径代价最小原则选择下一个扩展节点，因此在边权非负条件下是等价的。区别只在于 Dijkstra 常用于图最短路径问题，而 UCS 常用于人工智能中的搜索问题。
• A*是在UCS/Dijkstra基础上再加启发函数h(n)

A* vs A

• A搜索算法中，如果h(n)过大，就会把真正好的路径压下去
• A：用 f(n)=g(n)+h(n) 搜索，但 h(n) 不一定可采纳，因此 不一定最优
• A*：用 f(n)=g(n)+h(n) 搜索，而且 $h(n)\le h^{\ast }(n)$，因此 能保证最优

一致（单调）性

$h(n_1)\le c(n_1\to n_2)+h(n_2)$

假设你现在在节点 n_1，旁边有一个后继节点 n_2。

从 n_1 到目标，有一种走法是：

1. 先走一步到 $n_2$，代价是 $c(n_1\to n_2)$
2. 再从 $n_2$ 走到目标，估计代价是 $h(n_2)$ 那么这条“先到 n_2 再去目标”的总代价估计就是：

$c(n_1\to n_2)+h(n_2)$

而一致性要求：

$h(n_1)\le c(n_1\to n_2)+h(n_2)$

意思就是：

你在 n_1 对目标的估计，不能比“先走到相邻节点 n_2，再从n_2 去目标”的估计还大。

---

设 n_2 是 n_1 的后继，则

$g(n_2)=g(n_1)+c(n_1\to n_2)$

再看 f：

$f(n_2)=g(n_2)+h(n_2)=g(n_1)+c(n_1\to n_2)+h(n_2)$

由一致性条件：

$h(n_1)\le c(n_1\to n_2)+h(n_2)$

可得：

$g(n_1)+h(n_1)\le g(n_1)+c(n_1\to n_2)+h(n_2)$

即：

$f(n_1)\le f(n_2)$

这很关键：

一致性意味着：

沿着一条路径往前走时，$f(n)$不会下降，只会不变或增大。

在8数码中：

用 曼哈顿距离 作为 h(n)：

• 每移动一步，某个数字到目标位置的总曼哈顿距离至多变化 1
• 而每一步的真实代价就是 1

所以它满足： $h(n_1)\le 1+h(n_2)$

因此曼哈顿距离通常是一致的

可采纳性vs一致性

可采纳性

要求的是：

$h(n)\le h^{\ast }(n)$

意思是：

对每个节点 n**，启发值不能超过从** n 到目标的真实最小代价。

这是从“节点到目标”的角度看。

---

一致性

要求的是：

$h(n_1)\le c(n_1\to n_2)+h(n_2)$

意思是：

对每一条边，启发值在相邻节点之间也不能违反代价关系。

这是从“相邻节点之间”的角度看。

---

二者联系

• 一致性可推出可采纳性
• 一致性比可采纳性更强
• 可采纳不一定一致

双人博弈的扩展定义

• 两个玩家：双方完全理性
• 离散的：游戏的状态或决策可以映射为离散的
• 有限的：游戏的状态或可以采取的行动种类是有限的
• 确定性：没有不确定因素，比如骰子、抛硬币等
• 完美信息：任何状态层面的状态是可观察的
• 零和博弈：完全的竞争，游戏的一方赢了，另一方输掉同等数量

MiniMax算法

• Max想要最大化收益、Min想要最小化收益，从叶子节点开始从叶子节点往根节点回溯，对于Min则选其后继中最小的，对于Max则选其后继中最大的。
• 假设对方能做出最优行动
  • 己方总能做出最小化对方获得的收益的行动
  • 通过最小化对方收益来最大化己方收益