超越经典搜索

1 局部搜索算法和最优化问题

保留一个状态，不断的去修改它。

1.1 爬山法

选择当前状态下最大值的后继。

困境

沿着最陡峭的方向，不一定是最优的。

随机爬山法

失败原因：
只知道上升，不知道下降。（进入局部最优之后，走不出来）

首选爬山法

随机重启爬山法

退回到一个随机的初始状态。
看做是单个爬山法执行了多次（串行执行）。
也可以并行执行。

局部极值问题的解决方法：

• 允许下山移动
• 多次随机重启
• 从多个随机初始状态出发同时爬山。

1.2 模拟退火搜索

1.3 局部束搜索

（并行搜索的时候，有用的信息会在线程之间传递）
随机束搜索：

1.4 遗传算法

2 连续空间中的局部搜索

引入问题：

目标函数

3 使用不确定动作的搜索

环境不确定或者部分可观察，则agent无法判断自己处于什么状态。
感知信息感受agent 行为的结果。

3.1 不稳定的吸尘器世界

做动作、感知信息、判断行动。
此时问题不是一个序列，而是一个应急规划(策略)。

每个动作的结果有多种可能。
转移模型：
新的Result函数返回的是 一组可能的状态。

解：
问题的解不再是动作序列，而是应急规划。
不确定性问题的解 是嵌套的 if-then-else语句。
意味着他们是树，而不是序列。

3.2 与或搜索树

4 使用部分可观察信息的搜索

4.1 无观察信息的 搜索

考虑吸尘器世界的无传感器版本（动作具有确定性）

4.2 有观察信息的搜索

5 联机搜索Agent 和未知环境

5.1 联机搜索问题

竞争比：实际经过的路径开销/实际的最短路径

5.3 联机局部搜索

5.4 联机搜索中的学习

• 需要对这类一般规则作出规范的，明确的可操作的描述
• 需要有算法能够根据agent的行为…………

v
v
v
v
v
v