人工智能：现代方法总结上

1. 智能体与搜索问题

1. 理性智能体（Rational Agents）

  • 智能体（Agent） 是一个能 感知（perceive） 环境并 采取行动（act） 的实体。
  • 理性智能体（Rational Agent） 选择 能最大化预期效用（expected utility） 的行为。
  • 智能体的决策受以下因素影响：
    • 感知能力（Percepts）
    • 环境特性（Environment）
    • 行动空间（Action Space）

理性智能体的特点

  • 不是全知全能（Omniscient）：
    • 它们只能根据感知到的信息做决策。
  • 不是预知未来（Clairvoyant）：
    • 它们无法提前知道所有环境的动态变化。
  • 必须探索和学习（Exploration & Learning）：
    • 在未知环境中，智能体需要不断调整策略。

智能体 ≠ 绝对成功

  • 理性智能体不一定总是成功，但它们能 自主行动（Autonomous），尽可能地做出最佳决策。

2. 智能体的 PEAS 结构

智能体的行为可以用 PEAS（Performance Measure, Environment, Actuators, Sensors） 框架描述：

  • P（Performance Measure，性能度量）：如何评估智能体的表现
  • E（Environment，环境）：智能体运行的环境
  • A（Actuators，执行器）：智能体的可执行操作
  • S（Sensors，传感器）：智能体感知环境的方式

示例 1：Pacman（吃豆人）

组件说明
P（性能度量）-1 每个时间步；+10 吃豆子；+500 过关；-500 死亡；+200 吃惊吓状态的幽灵
E（环境）Pacman 迷宫、幽灵的行为
A（执行器）上（N）、左（W）、右（E）、下（S）、停止（Stop）
S（传感器）游戏的整个状态是可见的

示例 2：自动驾驶（RoboTaxi）

组件说明
P（性能度量）收入、顾客满意度、车辆成本、罚款、保险费用等
E（环境）街道、其他车辆、行人、天气等
A（执行器）方向盘、刹车、油门、显示屏、语音播报
S（传感器）摄像头、激光雷达（Lidar）、雷达、超声波传感器、加速度计、麦克风等

3. 环境分类（Environment Categorization）

搜索问题涉及不同的环境特性，例如：

特性 Pacman 自动驾驶（RoboTaxi）
完全可观察（Fully Observable）/部分可观察（Partially Observable） 完全可观察 部分可观察
单智能体（Single-Agent）/多智能体（Multi-Agent） 多智能体 多智能体
确定性（Deterministic）/随机性（Stochastic） 确定性 随机性
静态（Static）/动态（Dynamic） 静态 动态
离散（Discrete）/连续（Continuous） 离散 连续
详细解释
  1. 完全可观察（Fully Observable） vs. 部分可观察（Partially Observable）

  • Pacman：完全可观察

    • 游戏中的所有信息（如 Pacman 位置、豆子位置、幽灵位置等）都对智能体可见。
    • Pacman 可以基于当前的完整信息进行决策。

  • RoboTaxi：部分可观察

    • 自动驾驶面临 部分可观察 的环境：
      • 传感器（如摄像头、雷达）只能捕捉有限范围内的信息。
      • 其他驾驶员的意图、盲区、交通灯状态等信息可能不完全可知。
    • 这意味着自动驾驶智能体需要通过预测和推理来弥补信息的不确定性。
  1. 单智能体（Single-Agent） vs. 多智能体（Multi-Agent）

  • Pacman：多智能体

    • Pacman 游戏中的幽灵（Ghosts）也是智能体，它们具有自己的行为逻辑，并会影响 Pacman 的决策。
    • 因此，Pacman 需要考虑幽灵的行为模式，从而选择最优路径。

  • RoboTaxi：多智能体

    • 自动驾驶汽车不仅要做出自己的决策，还要考虑其他车辆、行人、自行车、交警等智能体的行为。
    • 这是一个典型的多智能体环境，不同智能体可能有不同的目标和决策方式（如有些车辆可能不遵守交通规则）。
  1. 确定性（Deterministic） vs. 随机性（Stochastic）

  • Pacman：确定性

    • 在 Pacman 游戏中，如果环境是固定的，幽灵的行为遵循特定规则（如朝向 Pacman 移动），那么 Pacman 的决策是确定性的。
    • 即给定当前状态，Pacman 执行相同的动作时，结果是完全可预测的。

  • RoboTaxi：随机性

    • 自动驾驶汽车的环境充满随机性，例如：
      • 其他驾驶员的行为可能不可预测（如突然变道）。
      • 行人可能随时闯红灯。
      • 天气状况（如大雾、暴雨）可能影响感知和决策。
    • 由于这些外部因素的影响，即使相同的起始条件，自动驾驶系统采取相同的行动，结果也可能不同，因此它是随机性的。
  1. 静态（Static） vs. 动态（Dynamic）

  • Pacman：静态

    • 在 Pacman 中，游戏状态在 Pacman 行动之前不会发生变化，幽灵的移动是根据规则设定的，不会在 Pacman 采取行动前随机改变。
    • 这意味着 Pacman 可以花时间计算最优路径，因为环境不会在决策过程中突然改变。

  • RoboTaxi：动态

    • 现实世界的道路环境是高度动态的：
      • 其他车辆可能突然加速或刹车。
      • 行人可能随时穿越马路。
      • 交通灯会不断变化。
    • 因此，自动驾驶汽车需要实时监控环境，并且可能在执行过程中需要重新规划路径。
  1. 离散（Discrete） vs. 连续（Continuous）

  • Pacman：离散

    • Pacman 的世界是网格化的：
      • 位置是离散的（如每个格子是一个状态）。
      • 行动也是离散的（只能上下左右移动）。
    • 这使得 Pacman 的搜索空间是有限的，并且可以使用搜索算法（如 A*）找到最优路径。

  • RoboTaxi：连续

    • 现实世界的道路环境是连续的：
      • 车辆可以在任意角度进行转向，而不是固定的网格移动。
      • 速度也是连续的，可以随时调整加速或减速，而不像 Pacman 只能在固定时间步进行移动。
    • 这种连续环境使得搜索空间变得无限大，需要使用不同的方法（如强化学习、路径规划算法）来解决问题。

4. 反射型智能体 vs. 规划型智能体

反射型智能体（Reflex Agents）

  • 决策方式：
    • 仅基于当前观察（可能结合记忆）选择动作
    • 可能有内部状态，但不会考虑未来的影响
  • 特点：
    • 只关注当前世界状态，而非未来状态
    • 不能主动计划
  • 示例：
    • 基于规则的机器人（如自动门）

问题：反射型智能体能否是理性的？

  • 在某些简单环境下（如自动门）可以，但在复杂问题中通常不是最优选择。

规划型智能体（Planning Agents）

  • 决策方式：
    • 选择动作时考虑未来的影响
    • 需要一个 状态转移模型（Transition Model），即预测环境的变化
    • 需要设定 目标（Goal）
  • 特点：
    • 关注 未来的可能状态，而不仅仅是当前状态
    • 可根据环境变化 动态调整计划
  • 示例：
    • 自动驾驶汽车（RoboTaxi）：需要根据未来道路状况、红绿灯等因素进行决策。

5. 搜索问题（Search Problems）

定义

一个搜索问题包括：

  1. 状态空间（State Space）
  2. 后继函数（Successor Function，包括可行的动作及其代价）
  3. 初始状态（Start State）
  4. 目标测试（Goal Test）
  5. 解（Solution）：
    • 一系列动作（Action Sequence），可以从初始状态到达目标状态。

搜索问题是环境的数学模型

  • 它并不包含所有现实世界的细节，只保留用于规划的必要信息。

6. 搜索问题示例

示例 1：罗马尼亚旅行问题

目标：从 Arad 到 Bucharest

  • 状态空间：罗马尼亚的所有城市
  • 后继函数：道路连接的相邻城市（代价=距离）
  • 初始状态：Arad
  • 目标测试：当前城市是否为 Bucharest
  • 解：找到从 Arad 到 Bucharest 的最短路径

示例 2：迷宫寻路（Pathing Problem）

  • 状态空间：二维坐标 (x, y)
  • 动作：NEWS（上、下、左、右）
  • 后继函数：更新位置
  • 目标测试：当前位置是否为终点
  • 解：一系列移动指令

示例 3：吃豆人（Eat-All-Dots）

  • 状态空间：Pacman 位置 + 每个豆子是否被吃掉
  • 动作：NEWS
  • 后继函数：更新位置，更新豆子状态
  • 目标测试：所有豆子被吃完

2. 无知情搜索（Uninformed Search）

包括：

  • 搜索树（Search Trees）
  • 搜索算法的属性（Algorithm Properties）
  • 深度优先搜索（Depth-First Search, DFS）
  • 广度优先搜索（Breadth-First Search, BFS）
  • 迭代加深搜索（Iterative Deepening）
  • 一致代价搜索（Uniform Cost Search, UCS）

1. 搜索树与状态空间图

状态空间图（State Space Graph）

状态空间图是搜索问题的数学表示：

  • 节点（Nodes） 代表世界的不同状态。
  • 弧（Arcs） 代表动作（Action） 导致的状态变化。
  • 目标测试（Goal Test） 识别目标状态。

特点：

  • 在状态空间图中，每个状态只出现一次。
  • 由于状态数可能极大，通常无法完整存储该图。

搜索树（Search Trees）

搜索树是：

  • 一棵 “假设” 未来行动及其结果 的树。
  • 根节点是初始状态，子节点是后继状态。
  • 节点不仅代表状态，还包含到达该状态的行动序列。

状态空间图 vs. 搜索树

属性状态空间图搜索树
节点代表唯一状态代表状态及其路径
是否构建完整结构？理论上可以现实中通常不行
内存占用仅存储状态需存储完整路径

2. 树搜索（Tree Search）

搜索算法的核心思想：

  • 扩展（Expansion）：展开某个节点，生成后继状态。
  • 边界（Fringe）：待探索的状态集合。
  • 探索策略（Exploration Strategy）：决定选择哪个节点扩展。

问题：如何选择要扩展的节点？

  • 深度优先：先探索最深的节点（DFS）。
  • 广度优先：先探索最浅的节点（BFS）。
  • 代价最小优先：优先扩展代价最低的节点（UCS）。

3. 搜索算法的属性

评价搜索算法时，需要考虑：

  1. 完备性（Completeness）：如果存在解，算法是否一定能找到？
  2. 最优性（Optimality）：是否能找到最短路径/最小代价的解？
  3. 时间复杂度（Time Complexity）：算法在最坏情况下需要多少步？
  4. 空间复杂度（Space Complexity）：算法在最坏情况下需要多少存储？

假设：

  • b = 分支因子（每个状态平均有多少子状态）。
  • m = 最大搜索深度。
  • s = 最浅解的深度。

4. 深度优先搜索（DFS）

策略

  • 优先扩展最深的节点（LIFO 规则）。
  • 使用 栈（Stack） 作为边界管理结构。

DFS 属性

属性DFS
完备性否（如果存在无限路径，可能永远找不到解）
最优性否（找到的是最左侧的解，可能不是最短路径）
时间复杂度(O(b^m))
空间复杂度(O(bm))（只存储沿路径的节点）

优缺点

✅ 优点：

  • 占用较少的内存（只存储沿路径的节点）。
  • 在某些问题上（如迷宫搜索）可能表现良好。

❌ 缺点：

  • 可能进入无限循环（如果不处理重复状态）。
  • 可能找到次优解（路径可能非常长）。

5. 广度优先搜索（BFS）

策略

  • 优先扩展最浅的节点（FIFO 规则）。
  • 使用 队列（Queue） 作为边界管理结构。

BFS 属性

属性BFS
完备性是（如果解存在，BFS 一定能找到）
最优性仅在所有路径代价相同时最优
时间复杂度(O(b^s))
空间复杂度(O(b^s))（需要存储整个层的节点）

优缺点

✅ 优点：

  • 保证找到最短路径（前提是路径代价相同）。
  • 不会陷入无限循环。

❌ 缺点：

  • 占用大量内存（边界存储所有未扩展的节点）。
  • 在深度较大的问题上性能较差。

6. 迭代加深搜索（Iterative Deepening）

策略

  • 结合 DFS 的低内存消耗 和 BFS 的最优性：
    1. 执行深度限制 DFS，限制深度 = 1。
    2. 如果未找到解，增加深度限制，重复执行 DFS。
    3. 直到找到解为止。

迭代加深搜索（IDDFS）属性

属性IDDFS
完备性是
最优性仅在单位代价路径时最优
时间复杂度(O(b^s))
空间复杂度(O(b s))（比 BFS 低很多）

优缺点

✅ 优点：

  • 低内存占用，只存储当前 DFS 路径。
  • 保证找到最短路径（单位代价时）。

❌ 缺点：

  • 重复搜索（但主要开销在最后一层，所以影响不大）。

7. 一致代价搜索（UCS）

策略

  • 扩展累计代价最小的节点（不是最浅的节点）。
  • 使用优先队列（Priority Queue） 作为边界管理结构。

UCS 属性

属性UCS
完备性是（假设每条路径的代价为正）
最优性是（保证找到最低代价路径）

优缺点

✅ 优点：

  • 保证找到最小代价路径（优于 BFS）。
  • 适用于变成本问题（Weighted Graph）。

❌ 缺点：

  • 扩展更多节点，尤其是在代价变化较大时。
  • 不考虑目标位置，可能在不必要的方向上浪费计算。

3. 知情搜索（Informed Search）

  • 启发式（Heuristics）
  • 贪心搜索（Greedy Search）
  • A* 搜索（A* Search）
  • 启发式设计与优化

相比于 无信息搜索（Uninformed Search）（如 DFS、BFS、UCS），有信息搜索利用 启发式函数（Heuristic Function） 来引导搜索过程，使其更高效。

1. 有信息搜索 vs. 无信息搜索

搜索类型 策略 是否使用启发式信息？ 特点
无信息搜索 BFS, DFS, UCS ❌ 否 盲目搜索，无方向性
有信息搜索 Greedy, A* ✅ 是 通过启发式估计引导搜索，更高效

在 无信息搜索 中，智能体像蒙着眼睛在搜索，而 有信息搜索 允许智能体“睁开眼睛”，利用启发式信息 来指导搜索。

2. 启发式（Heuristic）

什么是启发式？

  • 定义：启发式是一个估计函数 (h(n))，用于衡量当前状态 (n) 到目标的预计代价。
  • 作用：
    • 通过估计离目标的距离，引导搜索方向。
    • 适用于特定的搜索问题（不同问题的启发式不同）。

常见启发式函数

  • 曼哈顿距离（Manhattan Distance）：用于网格环境（如八数码问题、迷宫）。

    • 计算两点之间的水平和垂直距离。

  • 欧几里得距离（Euclidean Distance）：用于自由空间路径规划（如自动驾驶）。

    • 计算两点之间的直线距离。

3. 贪心搜索（Greedy Search）

策略

  • 扩展当前最接近目标的节点（根据启发式 (h(n))）。
  • 不考虑路径成本，只关注离目标的估计距离。

优缺点

✅ 优点：

  • 计算速度快，比 DFS、BFS 更高效。

❌ 缺点：

  • 可能找到错误的路径（容易被局部最优困住）。
  • 不保证最优解（可能会走“错误的捷径”）。

示例：罗马尼亚地图

  • 贪心搜索可能直接向目标前进，但如果中间有障碍，它可能会选错路径。

4. A* 搜索（A* Search）

A* 搜索结合：

  • UCS（Uniform Cost Search），考虑路径代价 (g(n))。
  • Greedy Search，考虑目标估计代价 (h(n))。

A* 搜索公式

f(n) = g(n) + h(n)

  • (g(n))：从起点到当前节点 (n) 的实际代价。
  • (h(n))：从当前节点 (n) 到目标的估计代价。
  • (f(n))：预计到达目标的总代价。

5. A* 搜索的最优性

什么时候 A* 是最优的？

A* 搜索的最优性依赖于 启发式 ( h(n) )：

  • 可采纳（Admissible）：
    • 启发式 不会高估实际代价（乐观估计）。
    • 例如：曼哈顿距离在网格环境中是可采纳的。

0 ≤ h(n) ≤ h*(n)

  • 一致性（Consistent）：
    • 对所有相邻节点 (n) 和 (m)，保证 A* 不会重新扩展节点（提高效率），启发式必须满足：

h(n) ≤ c(n, m) + h(m)

示例

  • 曼哈顿距离 满足可采纳性和一致性，因此 A* 搜索保证找到最优解。

4. 约束满足问题（CSP）

变量（Variables）：一组需要赋值的变量。

取值范围（Domain）：每个变量的可选值集合。

约束条件（Constraint）

5. 对抗搜索

abcut

Max-Value Function

def Max_Value(s, α, β):
if terminal(s):
return U(s) # Return utility value if terminal state

v = -∞
for c in next_states(s):  # Iterate through possible next states
    v' = Min_Value(c, α, β)
    if v' > v:
        v = v'
    if v' ≥ β:
        return v  # Prune the branch
    if v' > α:
        α = v'
return v

Min-Value Function

def Min_Value(s, α, β):
if terminal(s):
return U(s) # Return utility value if terminal state

v = +∞
for c in next_states(s):  # Iterate through possible next states
    v' = Max_Value(c, α, β)
    if v' < v:
        v = v'
    if v' ≤ α:
        return v  # Prune the branch
    if v' < β:
        β = v'
return v

解析

  • Max-Value 函数：
    • 适用于 Max 层（即希望最大化得分的玩家）。
    • 递归地计算所有可能子状态的 最小值 (Min_Value)。
    • 维护 α（当前已知的最佳最大值）和 β（当前已知的最佳最小值）。
    • 若 v' ≥ β，则直接返回 v（剪枝优化）。
  • Min-Value 函数：
    • 适用于 Min 层（即希望最小化得分的对手）。
    • 递归地计算所有可能子状态的 最大值 (Max_Value)。
    • 维护 α 和 β。
    • 若 v' ≤ α，则直接返回 v（剪枝优化）。

α-β 剪枝优化

  • 剪枝 (Pruning) 机制：
    • 当 Min-Value 发现 v' ≤ α 时，不再继续搜索，因为 Max 一定不会选择这个分支。
    • 当 Max-Value 发现 v' ≥ β 时，不再继续搜索，因为 Min 一定不会选择这个分支。
    • 通过剪枝，减少了不必要的计算，提高了算法效率。
  • 时间复杂度改进：
    • 普通 Minimax：O(b^d)（b = 分支因子，d = 深度）。
    • α-β 剪枝优化：最佳情况下 O(b^(d/2))，大幅减少搜索空间。

abcut

  • 非叶子结点：

max 层只改变a，取max(a, 下一层b)

Min 层只改变b，取min(b, 下一层a)

  • 最后一层子节点：无论大小都更新

max 层改变a，取叶子结点最大

min 层改变b，取叶子结点最小

  • 剪枝：a>=b，剪去当前结点右子树

abcut

Linear Programming

变量、条件、目标函数

优化

如何判断凸函数和凸集

1. 如何判断凸函数？

1.1 凸性定义

对于一个函数 ( f: \mathcal{F} \to \mathbb{R} )，如果对于任意 ( x, y \in \mathcal{F} ) 和 ( \theta \in [0,1] )，满足：
[
f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta) f(y)
]
那么 ( f(x) ) 是凸函数。

1.2 二阶导数法（单变量）

  • 计算函数的二阶导数 ( f’’(x) )：
    • 若 ( f’’(x) \geq 0 ) 对所有 ( x ) 成立，则 ( f(x) ) 是凸函数。
    • 若 ( f’’(x) ) 在某些区间小于 0，则该函数在该区间上不是凸的。

✅ 示例：

  • ( f(x) = x^2 )，( f’’(x) = 2 > 0 )，所以是凸函数。
  • ( f(x) = x^3 )，( f’’(x) = 6x )，在 ( x > 0 ) 时凸，在 ( x < 0 ) 时凹，因此在整个 ( \mathbb{R} ) 上不是凸函数。

1.3 Hessian 矩阵法（多变量）

对于一个二次可微的多元函数 ( f: \mathbb{R}^n \to \mathbb{R} )，计算其 Hessian 矩阵：
![截屏2025-03-06 18.05.26](/Users/peng/Library/CloudStorage/OneDrive-CityUniversityofHongKong-Student/CITYU/semester B/cs5491/midterm/截屏2025-03-06 18.05.26.png)

  • 如果 Hessian 矩阵 ( H(x) ) 是半正定的（所有特征值 (\lambda_i \geq 0)），则 ( f(x) ) 是凸的。

✅ 示例：

  • ( f(x) = x^T A x )，若矩阵 ( A ) 是半正定的，则 ( f(x) ) 是凸函数。

1.4 特殊函数的凸性

以下函数具有已知的凸性：

  • 指数函数 ( e^x ) 是凸的（因为二阶导数始终为正）。
  • 对数函数 ( \log x ) 是凹的，不是凸函数（因为二阶导数小于 0）。
  • 范数函数 ( |\mathbf{x}|_2 ) 是凸的（满足三角不等式）。

2. 如何判断凸集？

2.1 凸集定义

一个集合 ( \mathcal{F} ) 是凸集，如果对于任意两个点 x,y∈F 和 θ∈[0,1]，点 ( z ) 也属于F：
z=θx+(1−θ)y ∈F
即集合内任意两点的连线仍然属于该集合。

2.2 直观方法

  • 如果集合形状是“完整的”，没有“洞”或“凹陷”，通常是凸的。
  • 若集合有“弯曲”或“凹陷”，通常不是凸的。

✅ 凸集示例：

  • ( \mathbb{R}^n ) 是凸的，因为任意两点的连线都在 ( \mathbb{R}^n ) 内。
  • 空集 ( \emptyset ) 和单点集 ( {x_0} ) 是凸的（没有点去破坏凸性）。

❌ 非凸集合示例：

  • ( \mathbb{Z}^n ) 不是凸的，因为整数集合中的两个点的凸组合可能不在集合内。
  • 两个凸集的并集通常不是凸的（除非它们的并集仍然是一个整体）。

2.3 代数方法

  • 线性子空间和仿射子空间是凸的。
  • 半空间 ( a^T x \leq b ) 是凸的。
  • 两个凸集的交集仍然是凸的。

✅ 示例：

  • {x∣aTx≤b} 是凸集（线性不等式定义的集合）。
  • 单个点{x0} 是凸的。

❌ 非凸示例：

  • 两个凸集的并集 F1∪F2 不一定是凸的。

3. 总结

判断凸函数的方法

  1. 定义法：检查是否满足凸函数的不等式定义。
  2. 二阶导数法（单变量）：如果 ( f’’(x) \geq 0 ) 对所有 ( x ) 成立，则函数是凸的。
  3. Hessian 矩阵法（多变量）：如果 Hessian 矩阵是半