真实世界的搜索算法

本章讨论了部分可观测的、非确定性的、未知的和连续的环境中问题的搜索算法。

● 局部搜索算法，如爬山法，在内存中只保留少量状态。这些方法已被应用于优化问题，其思想是找到一个高分值的状态，而不考虑进入该状态的路径。研究人员已经开发了一些随机局部搜索算法，包括模拟退火，当给定适当的冷却方案时它能返回最优解。

● 许多局部搜索方法同样适用于连续空间中的问题。线性规划和凸优化问题服从状态空间形状和目标函数性质上的某些限制，并且允许多项式时间算法，这些算法在实践中往往非常高效。对于一些数学上合式的问题，我们可以使用微积分找到梯度为零的最大值；对于其他问题，我们必须使用经验梯度，即测量两个邻近点间的适应度差值。

● 进化算法是一种维护状态种群的随机爬山搜索。通过突变和杂交（结合状态对）产生新状态。

● 在非确定性环境中，智能体可以应用与或搜索算法生成应变规划，无论执行过程中出现何种结果，它都能实现目标。

● 如果环境是部分可观测的，信念状态表示智能体可能位于的可能状态的集合。

● 标准搜索算法可以直接应用于信念状态空间求解无传感器问题，而信念状态与或搜索算法可以求解一般的部分可观测问题。在一个信念状态中逐状态构构造解的增量算法通常效率更高。

● 探索问题发生在智能体对环境的状态和动作一无所知时。对于可安全探索的环境，在线搜索智能体能够构建地图并找到目标（如果存在的话）。根据经验来更新启发式估计值提供了一种避免局部极小值的有效方法。