《人工智能 一种现代方法》第三版 第3章 通过搜索进行问题求解 笔记摘录

第三章 通过搜索进行问题求解

本章讨论的问题具有如下性质：环境是可观察的、确定的、已知的，问题解是一个动作序列

• 问题求解Agent
  1. 使用原子表示的基于目标的Agent，被称之为问题求解Agent
  2. 使用要素法或结构化表示的基于目标的Agent，称之为规划Agent
  3. 基于当前的情形和Agent的性能度量进行目标的形式化是问题求解的第一个步骤
  4. 为达到目标，寻找行动序列的过程称之为搜索。搜索算法输入是问题，输出是问题的解，以行动序列的形式返回问题的解。
  5. 解一旦找到，他所建议的行动将会付诸实施，这被称为执行阶段。
  6. 因此对Agent的简单设计，即“形式化、搜索、执行。”
  7. 需要注意的是，Agent在执行解的序列时，无视它的感知信息，它明确行为的后果是什么。控制理论把这成为开环系统。
  8. 良定义的问题及解
     1. 一个问题可以用5个组成部分形式化地描述,其中初始状态、行动、转移模型定义了问题的状态空间即从初始状态可以到达的所有状态的集合，状态空间形成一个有向网络或图：
        1. Agent的初始状态 ，例如：In(Arad)
        2. 描述Agent的可能的行动。例如：ACTIONS（s）,返回在状态s下可移植性的动作集合：{Go(sibiu),Go(Timisoara)}
        3. 对每个行动的描述，也叫转移模型,例如：RESULT(s,a),在状态s下执行行动a后达到的状态：RESULT(In(Arad),Go(sibiu))=In(sibiu)
        4. 目标测试：确定给定的状态是不是目标状态
        5. 路径消耗函数为每条路径赋予一个耗散值，即边加权。问题求解Agent选择能反应它的性能度量的耗散函数。
• 问题实例
  1. 玩具问题（举例）

1. 1. 1. 增量形式化（举例）

1. 1. 1. 完全形式化
   2. 现实世界问题（举例）

• 通过搜索求解：再对问题形式化后，我们还需对问题求解
  1. 一个解是一个行动序列，搜索算法的工作就是考虑各种可能的行为序列。
  2. 从搜索树中根节点的初始状态出发，连线表示行动，结点是对应问题的状态空间中得状态。
  3. 再通过扩展当前的状态完成：从当前状态下应用各种合法行为，由此生成了一个新的状态集。
  4. 以上就是搜索，选择一条路走下去，把其他的选择放在一边，等以后发现第一个选择不能求出问题的解时再考虑。
  5. 所有待扩展的叶结点集合成为边缘。
  6. 搜索算法基础
     1. 搜索算法需要一个数据结构来记录搜索树的构建过程，对树中的每个节点，我们定义的数据结构包含四个 元素：

• 1. 1. 问题求解算法的性能：
        1. 评价一个算法的性能考虑以下四个方面：
           1. 完备性
           2. 最优性
           3. 时间复杂度
           4. 空间复杂度
        2. 评价搜索算法的有效性：
           1. 可以只考虑搜索代价—取决于时间复杂度，也包括内存的使用;
           2. 也可以使用总代价—包括求解的搜索代价和解路径的路径总代价
• 无信息搜索（盲目搜索）策略
  1. 无信息搜索算法：算法除了问题定义本身没有任何其他信息
  2. 搜索算法要做的是生成后继并区分目标状态与非目标状态。
  3. 这些搜索策略是以节点扩展的次序来分类的，以下为常见盲目搜索策略：
     1. 宽度优先搜索
     2. 一致代价搜索
     3. 深度优先搜索
     4. 深度受限搜索
     5. 迭代加深的深度优先搜索
     6. 双向搜索
  4. 无信息搜索策略对比
• 有信息（启发式）的搜索策略：（知道一个非目标状态是否比其他状态更有希望接近目标的策略）
  1. 有信息的搜索算法，利用给定的只是引导能够更有效的找到解。
  2. 要考虑的一般算法称为最佳优先搜索，结点是基于评价函数f(n)值被选择扩展的，评估函数被看作是代价估计，因此评估值最低的节点被选择首先进行扩展。
  3. 最佳优先图搜索的实现与一致代价搜索类似，区别在于最佳优先是根据f值而不是g值对优先级队列排序的。
  4. 对f的选择决定了搜索策略，大多数的最佳优先搜索算法的f由启发函数构成

• 1. 启发式信息导引搜索的两种形式
     1. 贪婪最佳优先搜索
     2. A*搜索：缩小总评估代价
     3. 存储首先的启发式搜索
     4. 学习以促搜索
• 启发式函数
  1. 启发式的精确度对性能的影响
  2. 从松弛问题出发设计可采纳的启发式
  3. 从子问题出发设计可采纳的启发式：模型数据库
  4. 从经验中学习启发式
  5.  
• 本章小结