一、智能体（Agent）基础
智能体的行为由感知序列到动作的映射来描述
理性（Rationality）是指智能体的行为能够最大化其期望效用或价值。理性智能体会选择能够使其预期绩效指标最大化的行动。
1. 反射智能体（Reflex Agents）
- 基于当前感知选择动作（可能包含记忆）
- 可能具有记忆或世界模型
- 直接从感知映射到动作的内置规则
- 不考虑行动的未来后果
- 只考虑世界的现状（IS）
反射智能体可能是理性的吗？
- 有限的智能
- 当且仅当正确的决策能只根据当前状态给出
- 也就是说，智能体反射的规则被写得足够完善
2. 规划智能体（Planning Agents）
- 基于行动的假设性结果做决策
- 必须有世界演化模型（世界根据我的行动会发生什么变化？）
- 知识表示明确且可修改
- 考虑世界可能的状态（WOULD BE）
3.通用智能体
二、搜索问题（Search Problems）
0. 搜索
搜索的过程包括：
- 节点拓展：从边界中选出一个节点，放入“已探索”集合
- 目标测试：检查当前拓展的节点是否是目标节点
- 生成：若当前节点不是目标节点，则将所有与该节点相连的节点放入边界（frontier），等待后继探索
1. 搜索问题的组成部分
- 状态空间（State Space）：从初始状态可达的所有状态集合
- 初始状态（Initial state）：问题的起点状态
- 动作集（Actions）：每个状态下可以执行的操作
- 转移模型（Transition Model）：描述执行动作后状态如何改变
- 目标测试（Goal test）：判断是否达到目标状态的条件
- 路径代价（Path cost）：从初始状态到目标状态路径的总消耗
A solution is a sequence of actions which transforms the start state to a goal state.
2. 状态空间图
- 节点代表状态
- 节点之间的连线代码行动
状态空间图：每个状态只出现一次
A search state keeps only the details needed for planning (abstraction)
实际上就是人的注意力机制。人接受到的各种信息是海量的，人可以在一瞬间判断那些重要，哪些不重要
3. 搜索树（Search Tree）
搜索树是对搜索过程的展开表示，它显示了从初始状态开始执行的所有可能动作序列。
- 每个节点代表一个状态
- 每条边代表一个动作
- 同一个状态可能在搜索树中出现多次（不同路径到达相同状态）
- 搜索树随着搜索过程逐步展开
- 边界（Frontier）：当前已生成但尚未扩展的节点
- 已探索集（Explored Set）：已经扩展过的节点
问题：搜索树的大小通常远大于状态空间图，因为同一状态可能通过不同路径多次到达。这也是为什么在实际搜索中需要记录已访问状态，以避免重复搜索。
三、非启发式搜索策略
1. 深度优先搜索（DFS）
- 策略：总是扩展搜索树中当前边界最深的节点
- 实现：边界是LIFO栈
- LIFO（Last In First Out）是一种栈的访问策略
- 后进入栈的节点会被优先处理
- 这确保了搜索沿着一条路径尽可能深入探索
- 空间复杂度：
- 空间复杂度表示对存储单元的要求
- 为分支因子，表示在搜索树中每个节点平均可以产生的子节点数量；为最大深度；
- 在搜索树中，每一层最多需要存储b个节点的信息
- 最大深度为m，因此最多需要存储m层
- 所以总的空间复杂度为
- 这比广度优先搜索的空间复杂度要好得多，因为DFS只需要存储当前搜索路径上的节点
- 时间复杂度：如果m有限，则时间复杂度为（考察最差的情况）
- 在最坏情况下，DFS需要搜索至最大深度m
- 在每一层，每个节点最多需要生成b个子节点
- 因此，DFS可能需要访问搜索树中所有节点，直到深度m
- 这意味着最多需要访问个节点
- 这就是为什么DFS的时间复杂度是，其中b是分支因子，m是最大深度
- 完备性：仅当防止循环时，也就是m是有限的（完备性有条件）
- 容易理解：循环👉无限深度👉深度优先搜索会一条路走到黑
- 最优性：否，找到最左边的解，与深度或代价无关
2. 广度优先搜索（BFS）
- 策略：首先扩展最浅的节点
- 实现：边界是FIFO队列
- FIFO (First In First Out) 是一种队列访问策略
- 先进入队列的节点会被优先处理
- 这确保了以层为单位逐步扩展搜索树
- 时间复杂度：，为最浅解的深度
- 每一层搜索都需要扩展前一层的所有节点
- 在深度d之前的每一层，BFS都需要访问所有节点
- 第1层有b个节点，第2层有个节点，直到第d层有个节点
- 所有层的节点总和为
- 空间复杂度：，为最浅解的深度
- 在最坏情况下，BFS需要存储整个搜索树的最后一层的所有节点
- 在深度处，最后一层的节点数量为
- 因为每层节点数呈指数增长：第1层有个节点，第2层有个节点，以此类推
- 所以在搜索到深度时，最后一层的节点数为，严格来说需要的最大存储空间是，不过一般以代替
- 这些节点都需要存储在边界（frontier）中，直到它们被扩展
- 这也是BFS的主要缺点之一：随着搜索深度的增加，内存需求呈指数增长
- 完备性：是
- 最优性：仅当所有步骤代价相同时（有条件的最优）
3. 迭代深度优先搜索
4. 一致代价搜索（UCS）
一致代价搜索（UCS）详细笔记
左边是状态图，右边是搜索树，数字是累积成本（也就是沉默成本）
- 策略：总是优先扩展到目前为止路径成本最小的节点
- 由于是无信息搜索，我们不知道未来的成本，只能根据目前的成本进行决策
- 实现：边界是优先队列（优先级为累积代价）
- 完备性：是（假设最优解有限代价且最小弧代价为正）
- 最优性：是
UCS按照代价等值线（cost contours）进行探索，确保找到的第一个目标状态就是最优解。
四、搜索算法的评估标准
- 完备性：是否保证找到解（如果存在）
- 最优性：是否保证找到最低代价路径（path cost最低）
- 并不是说找到解的时间是不是最短
- 时间复杂度：找到解需要多长时间
- 空间复杂度：需要多少内存来执行搜索
