复杂环境中的搜索主要介绍了更加真实情况下的搜索算法。复杂环境中可能面临如下问题：离散状态、连续状态、确定性假设、可观测性假设。

局部搜索

局部搜索只关心最终状态，不关心路径。

关键算法：爬山搜索，它记录当前状态，并在每次迭代中移动到值最大的相邻状态。这是一个逐步爬升的过程，可以联想到爬山，爬山同样是逐步向高处的一个过程。算法伪代码如下：

function Hill-climbing(problem) returns 一个位于局部极大值的状态
    current=problem.Initial
    while true do
        neighbor=current的值最大的后继状态
        if Value(neighbor) <= Value(current) then return current
        // Value 函数 = 评价函数 = 启发式函数。其实评价函数内部会调用启发式函数得到一个更好的评价函数
        current=neighbor

爬山算法的关键特点：

1. 只维护当前节点，不维护路径
2. 通过邻域移动产生新解
3. 评价函数直接作用于完整状态

书中同时介绍了关于爬山搜索中的两个概念：岭 和 平台区

岭：导致一系列局部极大值，对于贪心算法是问题

平台区：出现无效迭代，导致算法毫无进展

解决岭和平台区，需要通过：随机爬山法和随机重启爬山搜索

1.随机爬山搜索：节点被选中的概率随着坡度变化而变化 2.首选爬山法：随机生成一个后继，直到生成一个比当前状态更好的后继为止。 3.随机重启爬山法：从随机生成的初始状态开始，执行一系列爬山搜索，直到找到目标

爬山算法容易陷入局部极大值的陷阱，模拟退火算法可以解决这一问题。退火是工业属于，先加热到高温，然后在逐步降温，如此往复循环。

这里重要的是降温函数。

function Simulated-Annealing(problem, schedule) returns 一个解状态
    current=problem.Initial
    for t=1 to ∞ do
        T=schedule(t)
        if(T=0) then return current
        next=current的一个随机选择的后继状态
        detaE=Value(current)-Value(next)
        if(detaE > 0) then current=next
        else current=next仅以e的detaE/T次方的概率接受
        // 这里是玻尔兹曼分布，如果T降到0的速度足够慢，所有概率都集中在全局极大值上

局部束搜索

爬山和退火算法是只保留一个状态的算法，而局部束搜索是选择 K 个状态保留在内存中，每一步中完成全部 K 个状态的所有后继状态

在随机束搜索的基础上建立了进化算法。

连续空间中的局部搜索

离散空间和连续空间的区分：

1.离散空间的状态数量有限或可数的。每个状态之间有明确的间隔，不存在中间状态。关键特征是两个状态之间直接跳跃，不需要经过中间值。

商旅问题、拼图游戏等

2. 状态由一组实数（连续值）描述，取值可以无限细分，通常由无数个可能状态。

机器人关节角度从 0-360度的任意实数、飞行器姿态控制等

连续空间状态的处理方法：将连续状态空间离散化。

将连续状态空间离散化后，解决问题的方式就可以采用离散状态空间的方法了。因为离散状态空间每个状态之间存在明确的间隔，这时就需要明确给出被离散化后的连续状态空间的间隔如何给出。书中提了几个方式：

1. 经验梯度：通过两个相邻点之间目标函数值的变化来衡量.它的核心思想在于：通过数值差分来“感受”函数的变化趋势。很多时候，我们面对的是一个未知或过于复杂的数学函数，无法直接求导。经验梯度就像一个勘探者，通过在选定点周围做小范围的实际探测，来估算出局部的“坡度”。

例如，在一个二维的连续问题中，我们可以通过在点 (x, y) 附近采样 (x+dx, y) 和 (x, y+dy) 等点并计算它们的函数值，来近似估计该点沿各维度的梯度方向，从而找到一条能有效提升函数值的“离散”路径。

2. 状态聚合

将连续的数值区间划分为有限个“桶”（bucket）或“单元格”（cell），将落在同一区间内的所有连续状态视为一个单一的离散状态。

比如，在机器人导航中，我们不关心机器人的精确位置坐标（如(1.234, 5.678)），而只关心它位于哪个1米×1米的网格中。这就能将无限的状态空间简化为有限的网格。

使用非确定型动作的搜索

非确定性动作定义：

智能体执行一个动作后，可能转移到多个后继状态中的一个，但具体是哪一个，智能体无法事先确定。这通常源于：

环境的随机性（如掷骰子、移动机器人可能打滑）。

其他智能体的干预（如对手的动作）。

物理世界的内在不确定性（如天气预报）。

何时产生非确定性动作？

当环境是非确定性时，智能体不知道执行某个动作后会转移到什么状态。也就是智能体的信念状态不确定。

非确定性动作和部分可观测环境下，不在需要解的动作序列，而是要通过条件规划确定下一个动作。

通过与或树解决不确定性动作的搜索，或节点表示可以选择这个或那个动作，与节点表示每个动作的结果（也会引入分支条件）

function And-Or-Search(problem) returns 一个条件规划或 failure
    return Or-Search(problem, problem.Initial, [])

function Or-Search(problem, state, path) return 一个条件规划或 failure
    if(problem.Is-Global(state)) then return 空规划
    if(is-cycle(state, path)) then return failure
    for each action 在problem.Actions(state)中 do
        plan = And-Search(problem, Results(state, action), [state] + [path])
        if(plan!=failure) then return [action] + [plan]
    return failure

function And-Search(problem, states, path) return 一个条件规划或 failure
    for each s in states do
        plan = Or-Search(problem, s, path)
        if(plan== failure) then return failure
    return [if s then plan, else if s2 then plan2, else ... plann]

离线搜索和在线搜索

离线搜索是在执行第一个动作时已经的出了一个解。比较适合静态环境。

在线搜索是先开始一个动作，然后观测环境并计算下一个工作。适合半动态或动态环境。

其他资料

自洽性提升了语言模型中的思维链推理 https://ar5iv.labs.arxiv.org/html/2203.11171?_immersive_translate_auto_translate=1