一、智能体（Agent）基础
智能体的行为由感知序列到动作的映射来描述
理性（Rationality）是指智能体的行为能够最大化其期望效用或价值。理性智能体会选择能够使其预期绩效指标最大化的行动。
1. 反射智能体（Reflex Agents）
- 基于当前感知选择动作（可能包含记忆）
- 可能具有记忆或世界模型
- 直接从感知映射到动作的内置规则
- 不考虑行动的未来后果
- 只考虑世界的现状（IS）
反射智能体可能是理性的吗？
- 有限的智能
- 当且仅当正确的决策能只根据当前状态给出
- 也就是说，智能体反射的规则被写得足够完善
2. 规划智能体（Planning Agents）
- 基于行动的假设性结果做决策
- 必须有世界演化模型（世界根据我的行动会发生什么变化？）
- 知识表示明确且可修改
- 考虑世界可能的状态（WOULD BE）
3.通用智能体
二、搜索问题（Search Problems）
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）是一种栈的访问策略
- 后进入栈的节点会被优先处理
- 类似于叠盘子，最后放上去的盘子会最先被拿走
- 这确保了搜索沿着一条路径尽可能深入探索
- 空间复杂度：O(bm)，b为分支因子，m为最大深度：
- DFS只需要保存从根节点到当前搜索节点的路径上的节点，以及每个节点上未扩展的子节点
- 在任一时刻，搜索树中只需要保存一条从根到叶的路径，加上这条路径上所有节点的兄弟节点
- 即使在最坏情况下（最大深度m），所需空间也仅与树的深度成正比，而不是与树的宽度成指数关系
- 完备性：仅当防止循环时，也就是m是有限的（完备性有条件）
- 最优性：否，找到最左边的解，与深度或代价无关
- 时间复杂度：如果m有限，则时间复杂度为（考察最差的情况）
2. 广度优先搜索（BFS）
- 策略：首先扩展最浅的节点
- 实现：边界是FIFO队列
- FIFO (First In First Out) 是一种队列访问策略
- 先进入队列的节点会被优先处理
- 类似于排队买票，先到的人先买票离开
- 这确保了以层为单位逐步扩展搜索树
- 时间复杂度：O()，d为最浅解的深度
- 空间复杂度：
- 完备性：是
- 最优性：仅当所有步骤代价相同时（有条件的最优）
3. 迭代深度优先搜索
迭代深化深度优先搜索笔记4. 一致代价搜索（UCS）
一致代价搜索（UCS）详细笔记- 策略：总是优先扩展到目前为止路径成本最小的节点
- 实现：边界是优先队列（优先级为累积代价）
- 完备性：是（假设最优解有限代价且最小弧代价为正）
- 最优性：是
UCS按照代价等值线（cost contours）进行探索，确保找到的第一个目标状态就是最优解。
四、搜索算法的评估标准
- 完备性：是否保证找到解（如果存在）
- 最优性：是否保证找到最低代价路径（path cost最低）
- 时间复杂度：找到解需要多长时间
- 空间复杂度：需要多少内存来执行搜索
