搜索策略

1. 概述

• 概念
  • 依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程
• 搜索类型
  • 盲目搜索
    • 按预定的控制策略进行搜索，在搜索过程中获得的中间信息不改变控制策略
  • 启发式搜索
    • 在搜索中加入了与问题有关的启发性信息

2. 状态空间盲目搜索

• 形式化描述

名词	说明
状态	对智能体和环境当前情形的描述
动作	从当前时刻所处状态转移到下一时刻所处状态所进行的操作
状态转移	智能体选择了一个动作后，其所处状态的相应变化
路径/代价	一个状态序列
目标测试	评估当前状态是否为所求解的目标状态

• 基本思想
  • 先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点
  • 然后检查问题的目标状态是否出现在这些子节点中
  • 若出现，则搜索成功 ，找到问题的解；若没出现，则再按某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点
• 搜索树：用一棵树来记录算法探索过的路径
• Open表：保存搜索树中潜在可扩展的节点（通常处于树的边缘）
• 算法评价指标
  • 完备性、最优性、时间复杂度、空间复杂度

辅助信息	解释
评价函数$f(n)$	从当前结点n出发，根据评价函数来选择后续结点
启发函数$h(n)$	计算从结点n到目标节点之间所形成路径的最小代价值（一般可把两点之间的直线距离作为启发函数）

• 深度优先搜索（DFS）
  • 表中先进入的节点先被扩展的优先度低，后进入的被扩展的优先度高。
  • 完备性：不一定能找到解
  • 最优性：一般不能保证找到最优解
• 广度优先搜索（BFS）
  • 开表中的先进入的节点先被扩展的优先度高，后进入的被扩展的优先度低。
  • 完备性：当问题有解时，一定能找到解
  • 最优性：得到的解是搜索树中路径最短的解
• 代价一致搜索（UCS）
  • 完备性：当问题有解时，一定能找到解
  • 最优性：得到的解是代价最小的解
  • 评价函数：$f(n)=g(n)$
    • $g(n)$：起始结点到节点n代价（当前最小代价）

3. 状态空间启发式搜索

• 启发性信息：与具体问题求解过程有关，并可指导搜索过程朝着最有希望方向前进的控制信息
  • 启发信息的启发能力越强，扩展的无用节点越少
• 贪婪最佳优先搜索
  • 优先扩展距离目标最近的节点
  • 评价函数：$f(n) = h(n)$
  • 完备性：若不排除环路，不是完备的
  • 最优性：一般不能保证找到最优解
• A*算法
  • 考虑初始节点到当前节点的代价，也考虑当前节点到目标节点的代价
  • 评价函数：$f(n)=g(n)+h(n)$
    • $g(n)$：起始结点到节点n代价（当前最小代价）
    • $h(n)$：结点n到目标结点代价（后续估计最小代价）
      • $h(n)$的值越大，说明它携带的启发性信息越多，A*算法扩展的结点就越少
  • 可容性：如果在起始点和目标点间有路径解存在，那么一定可以得到解，如果得不到解那么一定说明没有解存在
  • 一致性

4. 对抗搜索/博弈搜索

• 最小最大搜索
  • 是在对抗搜索中最为基本的一种让玩家来计算最优策略的方法
• Alpha-Beta剪枝搜索
  • 一种对最小最大搜索进行改进的算法，即在搜索过程中可剪除无需搜索的分支结点，且不影响搜索结果
• 蒙特卡洛树搜索
  • 通过采样而非穷举法来实现搜索

5. 蒙特卡洛树搜索

• 步骤
  1. 选择
     • 算法从搜索树的根节点开始，向下递归选择子节点，直至到达叶子结点或者到达具有还未扩展过的子节点的结点L
     • 这个向下递归选择过程可用UCB1算法来实现，在递归选择过程中记录下每个结点被选择次数和每个结点得到的奖励均值
  2. 扩展
     • 如果结点L不是一个终止结点，则随机扩展它的一个未被扩展过的后继边缘结点M
  3. 模拟
     • 从结点M出发，模拟扩展搜索树，直到找到一个终止结点
  4. 反向传播
     • 用模拟所得结果回溯更新模拟路劲中M以上结点的奖励均值和被访问次数