Ch1-2 绪论与智能体 (Introduction & Intelligent Agents)

课件：lec1_intro.pdf (62 页) + lec2.pdf (45 页)
教材：Artificial Intelligence: A Modern Approach (Russell & Norvig), Ch1 & Ch2
教师：吉建民，USTC

0. 本章概述

本章是整门课的起点，由"绪论"与"智能体"两节合并。绪论回答"AI 是什么、从哪来、到哪去"；智能体给出贯穿全书的统一框架——理性智能体 (Rational Agent)。后续所有主题（搜索、逻辑、不确定性、学习）都可视为不同类型智能体的能力。

第一部分：人工智能绪论 (lec1)

1.1 课程概览

教材与考核

• 主教材：Artificial Intelligence: A Modern Approach (3rd Edition)，S. Russell & P. Norvig（中译《人工智能——一种现代方法》）
• 参考书：机器学习（周志华，2016）、《动手学深度学习》（第二版）
• 学期总评 = 期末考试 (60%) + 书面作业 (15%) + 实验部分 (25%)

课程六大模块

课程定位

• 广义"人工智能"含搜索、知识表示与推理、规划、MDP、贝叶斯网等经典工作；当下大众语境中的"AI"多指机器学习/深度学习/大模型。
• 本课定位：面向计算机专业，熟练掌握 IT 工程师应具备的 AI 基础技术；同时作为索引介绍 ML/NN/大模型等新方向，仅要求了解。
• 进阶建议：系统入门 DL → 自学"动手学深度学习"（李沐，d2l.ai）；精深 → 选定 CV/NLP/多模态等具体领域，从综述读起、动手实现；成专家 → 加入实验室做前沿研究。

1.2 什么是 AI？—— 四种定义思路

教材主张：“理性地行动 (acting rationally)”。

四种思路的二维划分（按"像人/理性" × “思考/行动”）：

① 像人一样行动 (Acting Humanly)：图灵测试

• Turing (1950) “Computing Machinery and Intelligence”：将"机器能否思考？“转化为"机器能否表现出智能行为？”
• 模仿游戏 (Imitation Game)：人类裁判通过问答区分机器与真人。
• 预言：到 2000 年，机器可能有 30% 概率骗过普通人 5 分钟；并预见了此后 50 年反对 AI 的主要论点。
• 暗示 AI 的核心组成部分：知识 (knowledge)、推理 (reasoning)、语言理解 (language understanding)、学习 (learning)。
• ⚠️ 缺点：不可复现、非构造性、难以做数学分析。

② 像人一样思考 (Thinking Humanly)：认知科学

• 1960s"认知革命"：信息加工心理学取代行为主义。
• 需要关于大脑内部活动的科学理论，涉及抽象层次（“知识"还是"电路”？）与验证方式（自上而下预测行为 / 自下而上神经数据）。
• 现已与 AI 分离：发展为认知科学 (Cognitive Science) 与认知神经科学 (Cognitive Neuroscience)。

③ 理性地思考 (Thinking Rationally)：思维法则

• 规范性 (normative / prescriptive) 而非描述性。
• 源于亚里士多德：什么是正确的论证/思维过程？古希腊各学派发展出各种逻辑（思想的符号化与推导规则）。
• 经数学、哲学一脉相承到现代 AI。
• ⚠️ 问题：
  • 并非所有智能行为都由逻辑深思熟虑驱动；
  • "思考的目的是什么？该有什么想法？"难以回答；
  • 逻辑系统在不确定性下常做错事（部分学者认同此点，部分不认同）。

④ 理性地行动 (Acting Rationally) ← 教材采用

• 理性行为 (rational behavior) = 做正确的事：在给定可得信息下，期望最大化目标达成。
• 不一定需要思考（如眨眼反射）；但思考应服务于理性行动。
• 引亚里士多德《尼各马可伦理学》(Nicomachean Ethics)：“一切技艺与探索、一切行动与追求，都被认为指向某种善。”
• 关键区分：
  • 理性 ≠ 成功 (rational ≠ successful)
  • 不理性 ≠ 疯狂 (irrationality = 次优行动，而非 insane)
  • 完全依赖目标 (goals)
  • 现实世界充满不确定性与复杂性，通常只是近似理性。

1.3 理性智能体 (Rational Agents)

⭐ 这是贯穿全书的统一定义：

• 智能体 (agent) 是能够感知 (perceive) 和行动 (act) 的实体。
• 本课核心：设计理性智能体。
• 抽象地，智能体是一个从感知历史到行动的函数：

$$f : P^{*} \to A$$

（$P^{*}$ 为所有可能的感知序列，$A$ 为动作集）

• 对给定环境类与任务类，寻找性能最优的智能体（类）。
• ⚠️ 注意：计算资源有限使完美理性不可达 → 实际目标是"为给定机器资源设计最好的程序"。

学习与具身案例：自动驾驶架构在 2020 年前后从"分模块流水线"转向"端到端"。

1.4 机器学习：表示 + 评价 + 优化

• 机器学习 ≈ 拟合一个函数。
• 学习 = 表示 + 评价 + 优化：
  • 表示 (Representation)：确定假设空间 (hypothesis space) $\mathcal{H}$。
  • 评价 (Evaluation)：用评价函数（目标函数/打分函数）判断优劣。
  • 优化 (Optimization)：用搜索方法在假设空间中找到评价函数得分最高的函数。

1.4.1 误差定义

设假设 $h \in \mathcal{H}$，目标概念 $c \in \mathcal{C}$，分布 $\mathcal{D}$，样本集 $S=(x_1,\dots,x_m)$：

• 泛化误差 (generalization error)：

$$R(h) = \Pr_{x \sim \mathcal{D}}[h(x) \neq c(x)]$$

• 经验误差 (empirical error)：

$$\hat{R}_S(h) = \frac{1}{m}\sum_{i=1}^{m}\mathbb{1}[h(x_i) \neq c(x_i)]$$

• 两者关系：因为 $S$ 由 $\mathcal{D}$ 独立同分布产生，

$$\mathbb{E}_{S\sim\mathcal{D}^m}\big[\hat{R}_S(h)\big] = R(h)$$

（经验误差是泛化误差的无偏估计）

1.4.2 PAC 学习（“机器学习为什么可能”）

"好的假设"需同时满足两个 PAC 辨识条件：

1. 近似正确 (Approximately Correct)：泛化误差足够小，即 $R(h) \le \epsilon$。
2. 可能正确 (Probably Correct)：以大概率近似正确，即 $P(R(h)\le\epsilon)\ge 1-\delta$。

且所需样本数是关于 $1/\epsilon,\,1/\delta,\,n,\,\text{size}(c)$ 的多项式函数。

⭐ PAC 可学 (PAC-Learnable) 定义：概念类 $\mathcal{C}$ 称为 PAC 可学，若存在算法 $A$ 和多项式 $\text{poly}(\cdot)$，使得对任意 $\epsilon>0,\delta>0$、任意分布 $\mathcal{D}$（实例长度 $n$）、任意目标概念 $c\in\mathcal{C}$，当样本量

$$m \ge \text{poly}\!\left(1/\epsilon,\,1/\delta,\,n,\,\text{size}(c)\right)$$

有 $P_{S\sim\mathcal{D}^m}\!\left[R(h_S)\le\epsilon\right]\ge 1-\delta$。若 $A$ 运行时间也是多项式，则称高效 PAC 可学，$A$ 为 $\mathcal{C}$ 的 PAC 学习算法。

1.4.3 独立同分布 (i.i.d.)

$X_1,\dots,X_n$ 独立同分布当且仅当：

• 独立性：任意有限个 $X_{i_1},\dots,X_{i_k}$ 的联合分布 = 各自边缘分布之积；即每个变量的取值不受其他变量影响。
• 同分布性：所有变量服从相同分布。

⚠️ i.i.d. 是理想化假设，实际数据常违反（如时间序列自相关、空间聚类效应），需用时序分析、混合模型，或数据预处理（随机打乱）逼近。

1.4.4 Hoeffding 不等式

定理（Wassily Hoeffding, 1963）：设 $X_1,\dots,X_m$ i.i.d.，$X_i\in[a_i,b_i]$，对任意 $\epsilon>0$：

$$P\!\left(\frac{1}{m}\sum_{i=1}^{m}X_i - \frac{1}{m}\sum_{i=1}^{m}\mathbb{E}(X_i) \ge \epsilon\right) \le 2\exp\!\left(\frac{-2m^2\epsilon^2}{\sum_{i=1}^{m}(b_i-a_i)^2}\right)$$

• 直觉：取值范围有界的独立变量，随样本量增加，其均值越来越集中于期望附近；上界随 $m$ 指数级下降。
• 特例 $X_i\in[0,1]$：$P(\cdot)\le 2e^{-2m\epsilon^2}$。

1.4.5 经验误差与泛化误差的关系

由 $\mathbb{E}(\hat{R}_S(h))=R(h)$ 代入 Hoeffding（$[0,1]$ 情形）：

$$P_{S\sim\mathcal{D}^m}\!\left[\hat{R}_S(h)-R(h)\ge\epsilon\right]\le 2e^{-2m\epsilon^2}$$

令 $\delta = 2e^{-2m\epsilon^2}$，则对固定假设 $h:\mathcal{X}\to\{0,1\}$，以至少 $1-\delta$ 的概率成立：

$$\boxed{\,R(h)\le \hat{R}_S(h) + \sqrt{\dfrac{\log(2/\delta)}{2m}}\,}$$

1.4.6 奥卡姆剃刀 (Occam’s Razor)

对有限假设集 $\mathcal{H}$：

$$R(h) \le \hat{R}_S(h) + O\!\left(\sqrt{\dfrac{\log_2|\mathcal{H}|}{m}}\right)$$

• 固定 $|\mathcal{H}|$ 时，要达到与一致情形相同的保证，需要平方量级更大的标注样本。
• 即 Occam’s Razor（奥卡姆剃刀）：“如无必要，勿增实体” / 最简单的解释最好。

1.4.7 从特征工程到深度学习

• 传统 ML 流程中"特征表达"靠人工提取，耗时且关键 → 能否自动学习特征？能，即深度学习 (Deep Learning / 无监督特征学习)。
• 衍生：深度神经网络、计算图、CNN；代表模型 BERT、GPT-3。
• DeepSeek（范例）：
  • V3：671B 参数、推理激活 37B；核心创新含 MoE 架构（对 Transformer 的改进）、数据并行-专家并行-流水并行、MTP、分布式混合精度训练、DualPipe 训练框架；大幅降低训练/推理成本。
  • R1：用强化学习 GRPO（多组策略竞争、组内相对奖励）优化生成更好的 CoT，提升 LLM 推理能力；R1 生成的带推理过程 CoT 数据可蒸馏小模型，显著提升其推理能力。

1.5 "新"新工具 (Novum Organum)：神经网络的认识论

借"自然科学如何可能？"这一哲学命题，引出神经网络作为新工具的地位。

• 英国经验主义（休谟）：没有绝对真理，只是经验的归纳整理、compact 的表示。
• 大陆理性主义（莱布尼茨）：仿《几何原本》，从几条公设出发形式化推理构建完整理论。
  • 哥德尔不完备性定理：任何足够复杂（含数学归纳法）的公理系统不能既可靠又完备；可靠系统中必有真但不可证的命题。
  • 不同公理系统（理论）彼此不能证伪。
• 康德、黑格尔：人通过先验概念理解世界——不是世界本就如此，而是我们只能以公理系统方式理解复杂世界。
• 培根《新工具》：公理系统 + 科学实验。
• "新"新工具 = 神经网络、端到端学习，其理论基础有二：
  • 通用近似 (Universal Approximation)：任何连续函数都能被前馈神经网络以任意小误差近似。
  • 图灵完备 (Turing Completeness)：任何图灵机都能被循环神经网络 (RNN) 模拟。

1.6 AI 发展简史

孕育期 (Pre-1956)

诞生 (1956)：达特茅斯会议 (Dartmouth Workshop)

• 由 John McCarthy 组织为期两个月的暑期研讨会。
• 先驱：McCarthy, Minsky, Rochester, Shannon, Moore, Samuel, Selfridge, Solomonoff, Simon, Newell。
• 核心假设：“学习的每一个方面、智能的任何其他特征，原则上都能被精确描述到可以让机器模拟的程度。”
• 里程碑：与会者一致采用 Artificial Intelligence 作为该领域名称，标志 AI 作为独立学科正式诞生。

简史年表 (1950s–2026)

1.7 AI 现状与前沿 (2026)

• 全球格局：产业高速增长，中美领跑第一梯队；依托 LLM，AI 高速渗透科研、工业与生活，进入战略部署、监管落地与生态建设的深水区。
• 推理革命 (Reasoning Revolution)：范式从"快速生成 (System-1)“转向"慢思考推理 (System-2)”；DeepSeek V3/R1 引领低成本强化学习与开源推理范式；OpenAI o 系列、Google Gemini 等确立原生多模态与深度思考新标准。
• 具身 VLA 与复杂操作：$\pi_0^{*},\,\pi_{0.5},\,\pi_{0.6},\,$Motus 等 VLA 模型在非结构化环境中泛化能力显著提升；突破单一抓取，联合离散任务与连续运动规划，走向长程复杂操作。
• Agentic AI（自主智能体）：AI 从"对话框顾问"进化为"系统级执行者"，代表如 OpenClaw 接管终端，赋能跨应用、跨任务的自动化。

1.8 典型 AI 应用与里程碑模型

应用一：感知、决策与物理交互

• 智能交通与低空经济：自动驾驶（Tesla FSD v13 端到端纯视觉、华为乾崑 ADS 4.0 无图智驾城市泛化、Waymo 全无人 Robotaxi 商业运营）；无人机感知与控制（大疆行业级多模态巡检大模型、软体机械臂空中作业平台）。
• 具身智能与机器人：人形机器人（Tesla Optimus、Figure 02、宇树、智元）；家庭/服务机器人（斯坦福 Mobile ALOHA 炒菜/家务、RoboCup@Home）；四足机器人（宇树 Go2/B2）。
• 计算机视觉与安防：身份识别（苹果 Face ID 3D 活体检测、商汤智慧城市）；工业质检（百度智能云开物 3C 电子微米级缺陷检测）；医疗影像（腾讯觅影食管癌/肺结节、联影智能 uAI）。

应用二：生成、助理与科学前沿

• 生产力与代码生成：AI 编程（Cursor IDE 集成 Claude/o3、GitHub Copilot、DeepSeek Coder）；办公智能（微软 Copilot for Microsoft 365、钉钉 AI 助理）。
• 内容生成与大模型对话 (AIGC & LLMs)：文本/推理（ChatGPT GPT-4o/o3、Gemini 3.1、DeepSeek R1、豆包）；图像/视频（Sora、Veo、字节 Seedance 2.0）；音乐/音频（Suno v4、Udio）。
• 智能体与科学计算：个人助理/终端 Agent（Apple Intelligence、OpenClaw）；气象/物流（华为盘古气象大模型精度超传统数值预报、京东地狼 AGV 调度）；生命科学（DeepMind AlphaFold 3 高精度预测蛋白质结构，加速靶点制药与抗体设计）。

里程碑模型速查

课后练习：对比 DeepSeek/ChatGPT/Gemini/豆包/Kimi/千问/星火等大模型；利用大模型协助编程解题；调研试用 OpenClaw。

第二部分：智能体 (lec2)

2.1 智能体与环境

⭐ 智能体 (agent) 是任何能被视作通过传感器 (sensors) 感知环境、通过执行器 (actuators) 作用于环境的事物。

• 例：
  • 人类智能体：传感器 = 眼、耳及其他器官；执行器 = 手、腿、嘴等身体部位。
  • 机器人智能体：传感器 = 摄像头、红外测距仪；执行器 = 各类电机。
• 其他例子：软件机器人 (softbots)、自动调温器 (thermostats) 等。

智能体函数与程序

• 智能体函数 (agent function)：从感知历史到行动的映射 $f:P^{*}\to A$，完全定义了智能体。
• 智能体程序 (agent program) 在物理架构上运行以实现 $f$。
• ⭐ agent = architecture（架构）+ program（程序）

吸尘器世界 (Vacuum-cleaner world) — 经典示例

• 感知 (Percepts)：位置与内容，如 [A, Dirty]。
• 动作 (Actions)：Left, Right, Suck, NoOp。
• 引出问题：正确的函数是什么？能否用小程序实现？
• 现实类比：随机覆盖式扫地机器人（iRobot Roomba 3–8 系列算法）vs 规划式扫地机器人。

2.2 理性 (Rationality)

• 智能体应努力"做正确的事"——基于其能感知的信息与能执行的动作，选择最可能成功的行动。
• 性能度量 (Performance measure)：评价智能体行为成功与否的客观准则。
  • 扫尘器例：清除的灰尘量、用时、耗电量、噪声等。

⭐ 理性智能体定义：对每个可能的感知序列，理性智能体应基于该感知序列提供的证据和自身已有先验知识，选择期望最大化其性能度量的行动。

理性的三个不等式

由理性衍生出三种行为：

• 信息收集 (information gathering / exploration)：为修改未来感知、获取有用信息而采取行动。
• 学习 (learning)：弥补不全面或不正确的先验知识。
• 自主性 (autonomy)：智能体行为由自身经验决定（能学习与适应）即为自主。

即：Rationality → exploration, learning, autonomy。

2.3 PEAS 描述

⭐ PEAS = Performance measure（性能度量）、Environment（环境）、Actuators（执行器）、Sensors（传感器）。用于刻画一个任务环境。

示例一：自动驾驶出租车 (automated taxi)

示例二：互联网购物智能体 (Internet shopping agent)

2.4 环境类型（6 个维度）

环境类型在很大程度上决定了智能体的设计。

⭐ 真实世界是最难的组合：partially observable, stochastic, sequential, dynamic, continuous, multi-agent。

2.5 智能体类型

按通用性递增排列，四种基本类型，且都可变为学习智能体。

① 简单反射智能体 (Simple Reflex Agents)

• 仅基于当前感知与 条件-动作规则 (condition-action rules) 行动；无内部状态。

② 有状态的反射智能体 (Reflex Agents with State / Model-based)

• 维护内部状态以追踪世界的不可见部分，并根据变化与自身动作更新状态。

③ 目标驱动智能体 (Goal-based Agents)

• 反射智能体仅基于预计算知识（规则）行动；目标驱动智能体通过推理哪种行动能达到目标来行动。
• 更低效，但更自适应、灵活。
• 搜索与规划 (search and planning)：寻找满足目标的动作序列；与条件-动作规则的本质区别——需考虑"如果我做…会发生什么 (what will happen if I do…)"，涉及对未来推理。
• 可在不"重编程"规则的情况下改变目标（如出租车换了新目的地）。

④ 效用驱动智能体 (Utility-based Agents)

• 效用函数 (Utility Function)：状态到实数的映射。
• 允许在两类情形下做理性决策：
  • 权衡冲突目标 (conflicting goals)；
  • 评估竞争目标 (competing goals)。
• 更偏好的世界状态有更高效用。

⑤ 学习智能体 (Learning Agents)

⭐ 四大组件：

表查找智能体 (Table-lookup Agent) 的缺点

作为反例：表巨大、建表耗时长、无自主性、即便学习也需很久才能填满表项。

2.6 大语言模型驱动的 Agentic AI（现代延伸）

范式演进：从对话系统到 Agentic AI

• 生成式 AI 的局限：传统对话界面属被动响应系统，依赖人类输入 Prompt，输出文本/代码，缺乏与外部世界直接交互。
• ⭐ Agentic AI 定义：能够感知环境、自主多步规划 (Planning)、调用工具 (Tool-use)，并为达成既定目标而行动的 AI 系统。
• 经典公式的现代重构：agent = architecture + program
  • Program（认知核心）：LLM 作为推理与规划的"大脑"。
  • Architecture（躯干/脚手架）：现代 Agent 框架提供环境交互接口与执行环境。

现代 Agent 架构与 PEAS 映射（以 OpenClaw 为例）

⭐ 核心运行机制：ReAct 范式 (Reasoning and Acting)

1. Thought（思考）：LLM 接收自然语言指令，评估当前系统状态并决定下一步操作的逻辑。
2. Action（行动）：LLM 输出结构化的工具调用指令（如 JSON 格式的 search_files 工具），本地实际执行。
3. Observation（观察）：将本地执行结果（文件路径或文本截取）反馈给 LLM。
4. Loop（循环）：重复"思考 → 行动 → 观察"，直到自我验证目标已完成。

OpenClaw 架构细节

• 定位：开源自主系统操作智能体框架，将 LLM 的逻辑推理能力与 OS 级执行权限深度集成的闭环系统；实现"云端大脑 (LLM) + 本地手脚 (执行沙箱)"的物理与逻辑解耦。
• OS 级深度集成：运行在宿主机后台（终端或常驻进程），可直接挂载文件系统、终端 (CLI) 和网络栈作为"物理环境"。
• 多模态交互界面：无缝嵌入 Slack/Telegram/命令行等，把 Agent 转化为"数字共事者 (Digital Coworker)"。
• 扩展的 ReAct 状态机：
  1. 状态感知与思考：LLM 评估上下文 (Context)，进行目标拆解 (Task Decomposition)；
  2. 结构化行动：必须输出严格符合 JSON Schema 签名的函数调用 (Function Calling)，框架捕获并映射到本地脚本/命令；
  3. 客观反馈注入：捕获 stdout/stderr 作为新观测拼入上下文，触发下一轮推理。
• 动作空间 (Action Space) 决定能力边界：
  • 文件与系统工具：read_file、write_to_file、grep_search 等；
  • 浏览器自动化：集成 Playwright/Puppeteer，将 DOM 树转为无障碍树 (A11y Tree) 实现精准点击/输入/抓取；
  • 动态技能扩展：支持用户自行编写 Python 函数注册新技能，运行时动态调用甚至自我编写脚本解决长尾需求。

系统记忆管理与个性化对齐

为避免每次启动成为"白板 (Blank Slate)"，引入持久化双轨记忆系统：

• 静态系统级提示词：IDENTITY.md（行为准则与响应风格）、USER.md（用户偏好、操作系统类型、工作流习惯）。
• 动态情景记忆：本地**向量数据库（如 ChromaDB）**记录历史交互轨迹；面临相似任务时通过 RAG 召回过去成功路径或纠错经验，降低 Token 消耗、提高规划成功率。

部署挑战

• 边缘计算与本地推理：高频思考-行动循环带来巨大延迟与 API 成本 → 将小参数模型（如 7B/8B）本地量化部署。
• 安全边界与人在回路 (Human-in-the-loop, HITL)：
  • 沙箱隔离：执行环境限制在 Docker 容器或特定 VM 挂载目录，防误删核心文件；
  • 权限拦截：对不可逆高危操作（如 rm -rf、数据库 DROP、对外发邮件）强制挂起，等待人类明确授权。

⭐ Agentic AI 前沿挑战

📋 本章速览补充：以下内容节选自《人工智能大抄》，是该章核心知识点的浓缩版，置于章末便于快速回顾。

2 智能体

0. AI 定义与理性智能体

0.1. AI 的四种定义视角

教材常把 AI 定义分成四类：

本课更偏向：理性智能体 (rational agent)，即在给定感知和知识下，选择期望性能最好的行动。

0.2. 图灵测试

图灵测试关注机器是否能表现出与人类不可区分的智能行为。需要能力：

• 自然语言处理。
• 知识表示。
• 自动推理。
• 机器学习。
• 若是 Total Turing Test，还包括感知和机器人行动。

0.3. 理性智能体

理性不等于全知。理性智能体根据：

• 当前感知序列。
• 已有知识。
• 可执行行动。
• 性能度量。

选择能最大化期望性能的行动。

1. 智能体基础

1.1. 智能体定义

智能体通过传感器感知环境，通过执行器作用于环境。

1

agent = sensors + actuators + agent program

智能体函数：$f: \text{percept sequence} \to \text{action}$。注意输入是感知序列，不只是当前感知。

1.2. 理性智能体

理性智能体对每个可能感知序列，选择能最大化期望性能度量的行动。理性取决于：

• 性能度量。
• 先验知识。
• 可执行行动。
• 当前感知序列。

理性不等于：全知；永远成功；事后看最优。

1.3. PEAS

PEAS 用于描述任务环境：

• P Performance measure：性能度量。
• E Environment：环境。
• A Actuators：执行器。
• S Sensors：传感器。

例：自动驾驶出租车

• P：安全、准时、舒适、盈利、守法。
• E：道路、行人、车辆、交通灯、天气。
• A：方向盘、油门、刹车、喇叭、显示屏。
• S：摄像头、雷达、GPS、速度计、麦克风。

2. 环境与智能体类型

2.1. 环境类型

• 完全可观测：传感器能获得决策所需全部状态。
• 部分可观测：有隐藏状态或传感器噪声。
• 单智能体：只需考虑自身行动。
• 多智能体：其他智能体也会行动，可能合作或竞争。
• 确定性：当前状态和行动完全决定下一状态。
• 随机性：结果有概率分布。
• 片段式 (episodic)：每次决策互不影响。
• 序贯式 (sequential)：当前行动影响未来。
• 静态：智能体思考时环境不变。
• 动态：环境会变化。
• 半动态 (semidynamic)：环境不变但性能随时间变化，如限时考试。
• 离散：状态、时间、行动有限或可数。
• 连续：变量连续，如自动驾驶位置和速度。
• 已知：智能体知道行动结果模型。
• 未知：需要学习模型。

2.2. 智能体类型

2.2.1. 简单反射智能体
基于当前感知选择行动：if condition then action。适用于完全可观测环境。缺点：没有记忆。

2.2.2. 基于模型的反射智能体
维护内部状态：internal state = update(previous state, action, percept)。适用于部分可观测环境。

2.2.3. 基于目标的智能体
使用目标信息选择行动，常需要搜索/规划。例：目标 = 到达 Bucharest。

2.2.4. 基于效用的智能体
不只判断是否达成目标，还比较不同结果好坏。最大化期望效用：$\arg\max_a E[U(\text{Result}(a))]$。

2.2.5. 学习智能体
能通过经验改进性能。包含：performance element、learning element、critic、problem generator。

2.3. LLM Agentic AI（隔壁班补充）

隔壁班课件提到大语言模型驱动的 Agentic AI。可理解为：

• LLM 负责理解任务、规划步骤。
• 工具调用负责执行搜索、代码、数据库、网页等操作。
• 记忆模块保存上下文。

低概率概念题，了解即可。

3. 考试速查

3.1. 常见判断题

• 智能体函数输入是感知序列：对。
• 性能度量由智能体自己随意定义：错，通常由任务设计者给出。
• 简单反射智能体适合部分可观测复杂环境：错。
• 基于效用的智能体能处理目标之间的权衡：对。

3.2. 最后一分钟版

• PEAS：Performance, Environment, Actuators, Sensors。
• 理性 = 在给定信息下最大化期望性能。
• 环境分类：可观测/确定/片段/静态/离散/单智能体/已知。
• 智能体类型：简单反射、模型反射、目标、效用、学习。

Ch3-4 搜索 (Search: Uninformed & Informed)

课件：lec3.pdf (无信息搜索 / Uninformed Search) + lec4.pdf (有信息搜索 / Informed Search)
教材：Artificial Intelligence: A Modern Approach (Russell & Norvig), Ch 3
教师：吉建民，USTC

0. 本章概述

第二章的"目标驱动智能体 (goal-based agent)"需要"搜索与规划 (search and planning)"来找到达成目标的动作序列。本章正是把这一能力具体化：先给出搜索问题 (search problem) 的形式化，再用一系列策略在状态空间中寻找解。按是否利用额外领域知识，分为无信息搜索 (uninformed search) 与有信息搜索 (informed search / heuristic search)。

第一部分：问题求解智能体与搜索问题 (lec3)

1.1 问题求解智能体 (Problem-solving Agents)

⭐ 问题求解智能体是一类目标驱动智能体 (goal-based agent)：它通过评估未来的动作序列来做决策。

• 搜索算法通常假设：
  • 转移模型已知且确定 (known, deterministic transition model)
  • 离散的状态与动作 (discrete states and actions)
  • 完全可观测 (fully observable)
  • 原子表示 (atomic representation)：状态被视为整体，内部结构对算法不可见
• 通常有明确目标 (definite goal)；最优 (optimal) = 以最小代价达成目标。
• 使用更高级的因子化 (factored) 或结构化 (structured) 表示的同类智能体称为规划智能体 (planning agents)。

离线 vs 在线

• 离线问题求解 (offline problem solving)：先求出完整解再执行（“闭着眼睛执行 solution executed eyes-closed”）。
• 在线问题求解 (online problem solving)：在不具备完全知识时边感知边行动（后续章节）。

引例：Romania（罗马尼亚公路旅行）

• 在 Arad 度假，明天从 Bucharest 起飞 → 目标：到达 Bucharest。
• 目标形式化：“be in Bucharest”。
• 问题形式化：states = 城市；actions = 在城市间驾车。
• 解 (solution)：城市序列，如 Arad, Sibiu, Fagaras, Bucharest。

1.2 搜索问题的形式化 ⭐

⭐ 一个（搜索）问题 (search problem) 由以下要素组成：

• 解 (solution)：从初始状态到目标状态的一个动作序列。
• 最优解 (optimal solution)：所有解中代价最小者。

1.3 状态空间的抽象化 (Abstraction) 与"好"状态空间

抽象化

真实世界极其复杂，必须抽象化 (abstracted) 后才能求解：

• (抽象) 状态 = 一组真实状态的集合。
• (抽象) 动作 = 一组复杂真实动作的组合（如 Go(Zerind) 代表无数种可能路线、绕路、停靠）。
• 为保证可实现性 (realizability)：任何处于抽象状态 $\text{In(Arad)}$ 的真实状态，执行该动作后必须落入某个 $\text{In(Zerind)}$ 的真实状态。
• 每个抽象动作应比原问题"更容易"。

构建"好的"状态空间 ⭐

• 让状态尽可能可达、可行、合法；状态数越少越好（规避大量不可达状态）；方便设计后继函数与搜索算法。

例：n 皇后问题的三种状态空间设计（状态数差异巨大）

→ 同一个问题，状态空间设计的优劣直接决定搜索可行性。

其他典型搜索问题

⚠️ n-puzzle 的最优解是 NP-hard；8-puzzle 的状态数为 $O((n+1)!)$，是 NP 完全问题。

1.4 状态空间图 (State Space Graph) vs 搜索树 (Search Tree) ⭐

状态空间图

• 节点 (nodes) = 抽象的世界配置；弧 (arcs) = 后继关系（动作结果）；目标测试对应一组目标节点。
• ⭐ 在状态空间图中，每个状态只出现一次。
• 通常太大，无法完整在内存中构造，但是有用的概念。

搜索树

• 通过扩展 (expanding) 已探索状态的后续状态，按需动态构造。
• 搜索树的每个节点 (node) 对应状态空间图中一条完整路径（不是单个状态）。
• 尽量只构造必要的部分。

节点 (Node) 的数据结构

节点是搜索树中的数据结构，包含：

• state（状态）
• parent node（父节点）
• action（从父到本节点的动作）
• path cost $g(n)$（路径代价）
• depth（深度）

重复状态问题 ⭐

“Those who don’t know history are doomed to repeat it!”（不吸取历史教训者注定重蹈覆辙）

• 不检测重复状态，可能把一个线性规模的问题变成指数规模。
• 例：含重复状态、深度 $d$ 的搜索树有 $4^d$ 个叶节点；而距起点 $d$ 步以内的不同状态仅有约 $2d^2$ 个。

1.5 树搜索 vs 图搜索 (Tree-Search vs Graph-Search) ⭐

通用树搜索 (General Tree Search)

• 基本思想：离线、模拟地探索状态空间——不断生成已探索状态的后继（即"扩展状态"）。
• 主要变化维度：
  1. 下一步扩展哪个叶节点（决定策略）
  2. 是否检测重复状态
  3. frontier 与已扩展节点的数据结构

图搜索 (Graph Search) 与 Frontier

• Frontier（边界 / fringe）：分隔"已扩展区域"与"未探索区域"。
• 扩展一个 frontier 节点：把它从 frontier 移入已扩展集，并把新发现的未探索节点加入 frontier（维持 frontier 性质）。
• 例：$\{1,2\}$ 已扩展，frontier $=\{3,4,5\}$；扩展 3 后 frontier $=\{4,5,6,7\}$。

对比

1.6 搜索算法性能评估 ⭐

搜索策略 (search strategy) = 选择节点扩展的顺序。

四个评估维度：

复杂度参数 ⭐

1.7 无信息搜索 (Uninformed Search) 策略 ⭐

⭐ 定义：无信息搜索 (uninformed / blind search) 指除问题定义提供的状态信息外，没有任何附加信息。与之对应的是有信息搜索（启发式搜索），后者知道某非目标状态是否比其他状态更接近目标。

本课介绍 6 种无信息策略：广度优先、一致代价、深度优先、深度受限、迭代加深、双向。

1.7.1 广度优先搜索 (Breadth-First Search, BFS) ⭐

• Frontier 数据结构：FIFO 队列（first-in, first-out）。
• 完备性：完备（若 $d$ 有限）。
• 最优性：当每条边代价一致（cost = 1/step）时返回最优解；否则不一定。
• 时间复杂度：

$$1+b+b^2+\cdots+b^d = O(b^d)$$

若目标测试在节点被扩展时做（而非生成时），则整层 $d$ 都被扩展，时间复杂度为 $O(b^{d+1})$。

• 空间复杂度：$O(b^d)$（或 $O(b^{d+1})$），所有节点都要存——BFS 的最大瓶颈是空间。

1.7.2 一致代价搜索 (Uniform-Cost Search, UCS) ⭐

• 思想：扩展当前路径代价最小的未扩展节点。
• Frontier：按路径代价 $g(n)$ 排序的优先级队列。
• 若所有边代价一致，UCS 退化为 BFS。
• 完备性：完备，前提是单步代价有下界 $\epsilon>0$（即 step cost $\ge\epsilon$）。
• 最优性：最优（节点按 $g(n)$ 递增顺序扩展）。
• 时间/空间复杂度：代价不超过 $C^*$ 的节点数

$$O\!\left(b^{1+\lfloor C^*/\epsilon\rfloor}\right)$$

其中 $C^*$ 为最优解代价。

1.7.3 深度优先搜索 (Depth-First Search, DFS)

• Frontier：LIFO 栈（last-in, first-out）。
• 完备性：不完备——在无限深空间或含环空间会失败；若改为避免路径上的重复状态，则在有限空间完备。
• 最优性：不保证。
• 时间复杂度：

$$1+b+b^2+\cdots+b^m = O(b^m)$$

当 $m\gg d$ 时很糟；但若解密集，可能比 BFS 快得多。

• 空间复杂度：$O(bm)$，即线性空间——只需存一条根到叶的路径及路径上节点的未扩展兄弟。

1.7.4 深度受限搜索 (Depth-Limited Search, DLS)

• 思想：DFS + 深度界限 $l$，深度 $>l$ 的节点不再扩展。目的：避免 DFS “一条路走到黑”。
• 返回结果三种：有解 / 无解 / 在 $l$ 范围内无解。
• 完备性：不完备。
• 最优性：不保证。
• 时间复杂度：$O(b^l)$；空间复杂度：$O(bl)$。
• 若 $l<d$ 可能不完备；若 $l>d$ 不最优。

1.7.5 迭代加深的深度优先搜索 (Iterative Deepening Search, IDS) ⭐⭐⭐

⭐ 由 DLS 演化：以 $k=0,1,2,\dots$ 为深度界限反复执行 DLS，每轮加一。

• 结合了 BFS（完备/最优/浅层优先）与 DFS（线性空间）的优点。
• 完备性：完备。
• 最优性：当每条边代价一致（step cost = 1）时返回最优解；否则不一定。
• 时间复杂度：

$$db+(d-1)b^2+(d-2)b^3+\cdots+b^d = O(b^d)$$

（上层被重复生成，但额外开销不大）

• 空间复杂度：$O(bd)$（深度界限达到 $d$）。

IDS vs BFS 数值对比（$b=10,d=5$，解在最右叶）

• $N(\text{IDS})=50+400+3000+20000+100000=123450$
• $N(\text{BFS})=10+100+1000+10000+100000=111100$

重复生成上层的额外成本很小，但换来了线性空间。

⭐ 结论：当搜索空间大、解深度未知时，IDS 是无信息搜索的首选方法 (preferred uninformed search method)。

1.7.6 双向搜索 (Bidirectional Search)

• 思想：同时从初态和终态进行 BFS，在中间相遇。
• 难点：终态可能不好描述（如 n 皇后）；从终态出发的前驱函数可能不好定义。
• 完备性：完备。
• 最优性：当每条边代价一致时返回最优解；否则不一定。
• 时间/空间复杂度：$O(b^{d/2})$（两个 $d/2$ 深度的搜索）。

第二部分：有信息搜索 (Informed Search) (lec4)

2.1 有信息 vs 无信息

2.2 最佳优先搜索 (Best-First Search) ⭐

⭐ 核心思想：为每个节点定义评价函数 (evaluation function) $f(n)$——对"合意性 (desirability)"的估计；每次扩展 $f$ 最优的未扩展节点。

• 启发函数 (heuristic function) $h(n)$：估计状态 $n$ 距目标的接近程度；针对特定搜索问题设计。
• 实现：frontier 为按 $f$ 降序排列的优先级队列 (priority queue)。
• 是通用 TREE-SEARCH / GRAPH-SEARCH 的实例。
• 三个评价函数的特例：

其中：

• $g(n)$ = 从初始节点到 $n$ 的实际路径代价 (path cost so far)（向后代价 backward cost）。
• $h(n)$ = 从 $n$ 到目标的估计代价 (estimated cost to goal)（向前代价 forward cost）。

2.3 贪心最佳优先搜索 (Greedy Best-First Search) ⭐

• 评价函数 $f(n)=h(n)$ = 从 $n$ 到最近目标的代价估计。
  • Romania 例：$h_{\text{SLD}}(n)$ = $n$ 到 Bucharest 的直线距离 (Straight-Line Distance)。
• 策略：扩展看起来离目标最近的节点。
• 性质：

2.4 A* 搜索 ⭐⭐⭐

评价函数

$$\boxed{\,f(n)=g(n)+h(n)\,}$$

• $g(n)$ = 到达 $n$ 的耗散（cost so far）
• $h(n)$ = 从 $n$ 到目标的最低耗散路径的估计（启发函数）
• $f(n)$ = 经过 $n$ 到达目标的总代价估计

可采纳性 (Admissibility) ⭐

⭐ $h(n)$ 是可采纳的 (admissible) 当且仅当对每个节点 $n$：

$$h(n)\le h^*(n)$$

其中 $h^*(n)$ 是从 $n$ 到目标的真实最小代价。并要求 $h(n)\ge 0$，且对任何目标 $G$ 有 $h(G)=0$。

• 直觉：可采纳启发式从不过高估计到达目标的代价，即它是乐观的 (optimistic)。
• 例：$h_{\text{SLD}}$ 从不高估真实公路距离。

一致性 (Consistency) ⭐

⭐ $h(n)$ 是一致的 (consistent / monotone) 当且仅当对每个节点 $n$、每个由动作 $a$ 生成的后继 $n'$：

$$h(n)\le c(n,a,n')+h(n')$$

• ⭐ 一致性蕴含可采纳性 (consistency implies admissibility)。
• 若 $h$ 一致，则沿任何路径 $f$ 值单调不减：

$$f(n')=g(n')+h(n')=g(n)+c(n,a,n')+h(n')\ge g(n)+h(n)=f(n)$$

A* 的最优性定理 ⭐⭐⭐

定理 1（TREE-SEARCH）：若 $h(n)$ 可采纳，则 A* 的 TREE-SEARCH 版本最优。

定理 2（GRAPH-SEARCH）：若 $h(n)$ 一致，则 A* 的 GRAPH-SEARCH 版本最优。

最优性证明（TREE-SEARCH，可采纳情形）⭐

设次优目标 $G_2$ 已在 fringe 中，$n$ 是 fringe 中、位于通向最优目标 $G$ 的最短路径上的未扩展节点。

1. $f(G_2)=g(G_2)$（因为 $h(G_2)=0$）。
2. $g(G_2)>g(G)$（$G_2$ 次优）。
3. $f(G)=g(G)$（因为 $h(G)=0$）。
4. 故 $f(G_2)>f(G)$。
5. 由可采纳性 $h(n)\le h^*(n)$，且 $n$ 在到 $G$ 的最短路上：

$$f(n)=g(n)+h(n)\le g(n)+h^*(n)\le g(G)=f(G)$$

6. 因此 $f(G_2)>f(n)$，A* 永远不会选择 $G_2$ 扩展。$\square$

A* 的三个版本

• Tree-search 版本：不检测重复。
• Graph-search 版本：检测重复。
• Practical 版本：当发现到达旧节点 $n$ 的新路径时，若 $g(n)$ 变得更小，则更新 $n$ 并让它重新成为待扩展节点（即重新打开 closed 节点 / 路径更新）。这是实际工程中最常用的形式。

f-等值线 (f-contours)

A* 按递增的 $f$ 值扩展节点，逐步形成"等值线 (contours)"——contour $i$ 包含所有 $f=f_i$ 的节点，$f_i<f_{i+1}$。

A* 扩展哪些节点 ⭐

设 $C^*$ 为最优解代价：

• A* 扩展所有 $f(n)<C^*$ 的节点；
• A* 扩展部分 $f(n)=C^*$ 的节点；
• A* 不扩展任何 $f(n)>C^*$ 的节点。

A* 性质总结

2.5 启发式设计 (Heuristic Design) ⭐⭐⭐

8-puzzle 的两个经典启发式

设 $h^*(n)$ 为真实最少步数：

• $h_1(n)$ = 错位棋子数 (number of misplaced tiles)。
• $h_2(n)$ = 曼哈顿距离之和 (total Manhattan distance) = 所有棋子到其目标位置的水平竖直距离和。

对同一初始状态 $S$：$h_1(S)=8$，$h_2(S)=3+1+2+2+2+3+3+2=18$。

8-puzzle 平均解步数约 22，分支因子约 3；穷举到深度 22 需 $3^{22}\approx 3.1\times10^{10}$。

支配性 (Dominance) ⭐

⭐ 若对所有 $n$ 都有 $h_2(n)\ge h_1(n)$（且两者都可采纳），则称 $h_2$ 支配 (dominate) $h_1$，$h_2$ 更有利于搜索。

典型搜索开销（平均扩展节点数）对比：

→ 支配性更强的启发式扩展节点数远少于被支配者。

组合多个启发式 ⭐

⭐ 给定任意一组可采纳启发式 $\{h_1,\dots,h_m\}$，

$$h(n)=\max(h_1(n),\dots,h_m(n))$$

仍可采纳，且支配其中每个成员启发式。

松弛问题 (Relaxed Problems) ⭐⭐⭐

⭐ 松弛问题 (relaxed problem)：对动作施加更少限制的问题。

• ⭐ 核心定理：松弛问题最优解的代价，是原问题的一个可采纳启发式（因为去掉限制只会让代价不增）。
• 关键点：松弛问题的最优解代价 $\le$ 原问题的最优解代价。

8-puzzle 的三种松弛（原规则：棋子可从 A 移到 B，当 A、B 水平/垂直相邻且 B 为空）：

设计启发式的一般方法：从原问题去掉某些约束得到松弛问题，求其精确最优解作为 $h$。

Pattern Database（模式数据库）*

课件正文未直接展开，属 AIMA 标准方法（对照原课件/教材查看）：预先存储一组"模式 (patterns)"到目标的最短代价，作为可采纳启发式，常用于 15-puzzle 等大状态空间。

有效分支因子 (Effective Branching Factor)*

AIMA 标准评估指标（对照原课件/教材查看）：若 A* 扩展 $N$ 个节点、解深 $d$，定义 $b^*$ 使 $N+1=1+b^*+\cdots+(b^*)^d$；$b^*$ 越接近 1 说明启发式越好，且对同一问题 $b^*$ 在不同 $d$ 下大致恒定。

2.6 Hybrid A*（应用扩展）*

车辆自主泊车的路径规划算法：以较少换挡次数规划出可行驶轨迹。

• 搜索状态 $(x,y,\theta,r)$，$r$ 表示前进/后退。
• 动作离散化：max-left / no-turn / max-right。
• 启发式：
  • non-holonomic without obstacles：忽略障碍但满足可行驶约束（车头朝向连续变化）；
  • holonomic with obstacles：考虑障碍但忽略可行驶约束。
• 最后再做轨迹平滑与优化。

2.7 内存受限与迭代加深的 A*（AIMA 扩展）*

课件正文未直接出现，属 AIMA 标准考点（建议对照教材 Ch3 补充）：

• IDA* (Iterative Deepening A*)：把迭代加深思想用到 $f$ 值上。每轮设 $f$ 阈值，只扩展 $f\le$ 阈值的节点；下一轮阈值 = 上一轮被剪枝节点的最小 $f$。内存 $O(bd)$，可采纳 $h$ 下完备且最优。
• RBFS (Recursive Best-First Search)：递归式最佳优先，用线性内存模拟最佳优先；每个节点记录"可达的最佳 $f$ 替代值"，递归回溯。
• SMA* (Simplified Memory-bounded A*)：A* 的内存受限版——当内存满时丢弃 $f$ 最差节点，但将其信息回填到父节点，以便日后必要时重新生成。

2.8 局部搜索算法 (Local Search Algorithms) ⭐

适用场景：很多优化问题中，到目标的路径无关紧要，目标状态本身就是解。

• 状态空间 = “完整配置 (complete configurations)” 的集合（如 n 皇后的一种摆法）。
• 不断保持单个"当前状态"并尝试改进；常数空间，适合在线与离线搜索。

2.8.1 爬山搜索 (Hill-Climbing Search)

• 比喻：“像在浓雾中、患健忘症 (amnesia) 攀登珠峰”——只能看到局部、忘记来路。
• 问题：依赖初始状态，可能陷入局部极大值 (local maxima)、山肩 (shoulders)、平坦区。
• 改进：
  • 随机重启爬山 (Random-restart hill climbing)：克服局部极大，平凡地完备。
  • 横向随机移动 (random sideways moves)：逃出山肩。

8-queens 中的爬山

• 评价 $h$ = 互相攻击的皇后对数；某状态 $h=17$；可能陷入 $h=1$ 的局部最小。

2.8.2 模拟退火 (Simulated Annealing Search) ⭐

• 思想：允许少量"坏"移动以逃离局部极大，但逐渐降低其频率（温度 $T$ 缓慢下降）。
• ⭐ 理论保证：若 $T$ 下降足够慢，模拟退火将以趋于 1 的概率找到全局最优。
• 广泛用于 VLSI 布局、航班调度等。

标准 AIMA 中的接受准则（对照教材）：若 $\Delta E>0$ 直接接受；否则以概率 $\exp(\Delta E/T)$ 接受（$\Delta E$ 为新状态的值增量）。

2.8.3 局部剪枝搜索 (Local Beam Search)

1. 同时跟踪 $k$ 个状态（而非一个）。
2. 从 $k$ 个随机生成的状态开始。
3. 每轮生成所有 $k$ 个状态的全部后继。
4. 若任一为目标则停止；否则从完整后继列表中选最好的 $k$ 个，重复。

• ⚠️ 不是 $k$ 个独立搜索并行运行——发现好状态的搜索会"招募"其他搜索加入。
• 缺点：$k$ 个状态常聚集到同一座局部山丘 → 改进：随机选 $k$ 个后继、偏向好状态（随机束搜索 stochastic beam search）。

2.8.4 遗传算法 (Genetic Algorithms, GA) ⭐

• 后继由两个父代状态组合产生。
• 从 $k$ 个随机生成的状态（种群 population）开始。
• 状态表示为有限字母表上的串（常为 0/1 串）。
• 评价函数 = 适应度函数 (fitness function)：状态越好值越大。
• 通过三大操作产生下一代：选择 (selection)、杂交 (crossover)、变异 (mutation)。

8-queens 中的 GA

• 适应度 = 不互相攻击的皇后对数（min = 0，max = $\binom{8}{2}=28$）。
• 选择概率正比于适应度，如 $24/(24+23+20+11)=31\%$。

2.9 搜索方法小结

有信息搜索

• 启发函数估计到目标的最短路径代价；好的启发可极大降低搜索代价。
• 贪心最佳优先：扩展最小 $h$；不完备、不最优。
• A*：扩展最小 $g+h$；完备、最优，且（对前向搜索、除并列外）效率最优 (optimally efficient)。
• 可采纳启发式可由松弛问题的精确解导出。

局部搜索

• 路径无关紧要；保持单个"当前状态"并改进。
  • 爬山：可能陷入局部极大。
  • 模拟退火：允许坏移动并逐渐降温，可收敛到全局最优。
  • 局部剪枝：同时保留 $k$ 个状态。
  • 遗传算法：基于种群的选择/杂交/变异。

无信息 vs 有信息（课程结语）

• 好的启发式搜索能大幅提高搜索性能。
• 但启发式需要抽取问题相关特征信息，而特征抽取有时困难 → 盲目搜索仍是有用的策略。

好的搜索策略应满足

• 引起运动——避免原地踏步；
• 系统——避免兜圈；
• 运用启发函数——缓解组合爆炸。

📋 本章速览补充：以下内容节选自《人工智能大抄》，是该章核心知识点的浓缩版，置于章末便于快速回顾。

3 问题求解与无信息搜索

问题建模，BFS，UCS，DFS，DLS，IDS，手画搜索树

目录：0. 快速定位 · 1. 基本概念 · 2. 无信息搜索算法 · 3. 建模与手算模板 · 4. 考试速查

0. 快速定位

• 题目问"怎样表示问题"：看"问题形式化五要素"。
• 题目问"哪个算法最优/完备/省空间"：看"搜索算法对比表"。
• 题目给搜索树问下一步扩展谁：看"队列规则"。
• 题目要求自己建模，如 2020 三位数变换题：看"状态必须包含什么"。

1. 基本概念

1.1. 问题求解智能体

问题求解智能体通常是 goal-based agent：先给出目标，再把当前世界抽象成状态空间，在状态空间中搜索一条从初始状态到目标状态的行动序列。

课件特别强调：这是 offline problem solving，即先搜索完整计划，再闭眼执行。若执行中才获得新信息，则属于 online problem solving，不是本章重点。

1.2. 问题形式化五要素

一个良定义问题通常包含：

1. 状态空间 (state space)：所有可能状态的集合。
2. 初始状态 (initial state)：搜索起点。
3. 行动/后继函数 (actions/successor function)：在某状态能做什么，做完到哪里。
4. 目标测试 (goal test)：判断状态是否满足目标。
5. 路径代价 (path cost)：路径总代价，通常是单步代价累加。

标准写法：$\text{Problem} = (\text{States, InitialState, Actions, TransitionModel, GoalTest, PathCost})$。课件有时把后继函数写成：$S(x) = \langle \text{action, successor state} \rangle, \dots$，其中单步代价写作 $c(x, a, y) \geq 0$。

1.2.1. 状态与节点不要混淆

• 状态 (state)：世界的一种配置，例如"人在 Arad"，“水壶水量为 $(0,8,3)$”。
• 节点 (node)：搜索树中的数据结构，通常包含：state、parent、action、path-cost $g(n)$、depth。

同一个状态可能在搜索树中出现多次，因为它可能由不同路径到达。

考试常见坑：如果题目有"上一步不能操作同一位"之类限制，这个限制会影响未来后继，因此必须放进状态，而不只是节点注释。

例：2020 三位数搜索题。状态不能只写三位数 567，还要写"上一次改变的是哪一位"：

1

state = (number, last_changed_digit)

初始状态可写：(567, None)，否则无法判断下一步是否违反"连续两步不可操作同一位"。

1.3. 搜索树与状态空间图

状态空间图：每个状态是一个节点；每个合法行动是边；图可能有环。

搜索树：根是初始状态；每条从根到某节点的路径表示一个候选计划；节点可以重复包含同一个状态；实际问题通常无法展开整棵树。

• 树搜索不检查重复状态，容易陷入环。
• 图搜索使用 explored/closed 集合，避免重复扩展。

1.4. 通用搜索框架

1
2
3
4
5
6
7
8
9
10
11
12

frontier = [initial node]
explored = empty
while frontier not empty:
    n = choose_node(frontier, strategy)
    if goal_test(n.state): return solution_path(n)
    add n.state to explored
    for each successor s of n.state:
        if s not in explored/frontier:
            add child node to frontier
        else if new path is better:
            update frontier
return failure

不同搜索算法本质区别在于 choose_node 和 frontier 的组织方式。

• 生成 (Generate)：计算出一个后继节点，并把它放进 frontier 里等待。
• 扩展 (Expand)：从 frontier 中按照 choose_node 取出要扩展的节点，并计算它所有的后继节点。

1.5. 评价搜索策略的四个指标

• 完备性 (completeness)：若存在解，是否一定能找到。
• 最优性 (optimality)：是否保证找到最低路径代价的解。
• 时间复杂度：通常用分支因子 $b$、最浅目标深度 $d$、最大深度 $m$ 表示。
• 空间复杂度：搜索过程中最多存多少节点。

符号：

• $b$：branching factor，每个节点最多后继数。
• $d$：最浅目标深度。
• $m$：搜索树最大深度，可能无限。
• $C^*$：最优解代价。
• $\varepsilon$：最小正单步代价。

2. 无信息搜索算法

2.1. 无信息搜索算法对比表

无信息搜索仅使用从问题定义中获取到的信息（初始状态，状态转移规则，目标状态测试条件），没有任何其他启发式信息。

• 2021 选择题：所有边代价为 1，没有启发式，又要求省空间并保证最优，选迭代加深 DFS。
• 2020 判断题：BFS 是 UCS 的特例。若每条边单步代价相同，UCS 按 $g$ 递增扩展，等价于按深度扩展，因此正确。

2.2. 广度优先搜索（BFS）

BFS 用队列：

1
2

1. pop from front
2. push children to back

性质：

• 按深度逐层扩展。
• 当所有边代价相同，第一次找到目标就是最浅目标，也是最优解。
• 空间爆炸严重，因为要保存整层 frontier。

考试手算规则：

1. 从左到右生成子节点。
2. 同层先生成者先扩展。
3. 若题目规定并列按字母序，按题目来。

2.3. 代价一致搜索（UCS）

BFS 的升级版，应对每步代价不同的情况。UCS 每次扩展 $g(n)$ 最小的节点，使用优先队列来选出 $g(n)$ 最小的节点：

$$g(n) \triangleq \text{从初始节点到 } n \text{ 的已知路径代价} = \text{父节点 } g + \text{cost}(p, n)$$

操作步骤：

1. 初始化：将起点放入优先队列，累计代价设为 0。准备一个空的"已探索集合"（记录去过的地方，防止绕圈）。
2. 循环检查队列：
   • 如果优先队列空了，说明找不到路，宣告失败。
   • 弹出队列中代价最小的节点。
   • 目标测试：如果这个节点是终点，宣告成功！直接输出到达这里的路径。
3. 扩展节点：
   • 将刚弹出的节点加入"已探索集合"。
   • 观察它的所有邻居节点，计算到达每个邻居的新累计代价（当前节点累计代价 + 走到邻居的单步代价）。
4. 状态更新（UCS 最关键的一步）：
   • 如果邻居既不在队列里，也不在已探索集合里 → 直接作为新发现加入优先队列。
   • 如果邻居已经在优先队列里，但你刚算出的新代价比队列里记录的代价更低 → 发现了一条抄近道的路！立即更新队列里该节点的代价和父节点信息。
5. 返回第 2 步继续循环。

性质：

• 只要所有单步代价非负，且存在最小正代价，就完备。
• 保证最优。
• BFS 是"所有单步代价相同"的 UCS。

关键细节：

• 目标测试应该在弹出 frontier 准备扩展时做，而不是刚生成目标时就停。因为刚生成的目标路径不一定是最低代价。
• 若发现到同一状态的更低代价路径，需要更新 frontier。

2.4. 深度优先搜索（DFS）

DFS 用栈：

1
2

1. pop from top
2. push children so that leftmost child is expanded first

性质：

• 空间低，只保存当前路径和旁支。
• 不完备：无限深路径会卡住。
• 不最优：先找到的深层解可能代价很差。

适合：状态空间很大但解很深；只需要一个解；有深度上界或不会出现无限分支。

2.5. 深度有限搜索（DLS）

DLS 给 DFS 加深度限制 $l$：

• 深度超过 $l$ 不再展开。
• 可以返回三种结果：success、failure、cutoff。
• 若 $l < d$，找不到解；若 $l$ 太大，又退化为 DFS。

2.6. 迭代加深搜索（IDS）

IDS 依次运行：

1
2
3
4

DLS(limit=0)
DLS(limit=1)
DLS(limit=2)
...

为什么重复搜索仍然不亏？因为树中绝大多数节点在最深层，浅层重复展开的代价相对小。

性质：

• BFS 的完备性和单位代价最优性。
• DFS 的低空间复杂度。
• 单位代价搜索中非常常考。

2.7. 双向搜索

思路：同时从初始状态和目标状态搜索，直到两个 frontier 相遇。

复杂度：理想情况下从 $O(b^d)$ 降为 $O(b^{d/2})$。

限制：

• 必须能反向生成前驱。
• 目标状态要明确。
• 要能快速检测两个 frontier 是否相交。

3. 建模与手算模板

3.1. 状态空间建模模板

3.1.1. 罗马尼亚路径规划

• 状态：所在城市。
• 初始状态：Arad。
• 行动：沿道路开往相邻城市。
• 转移模型：$\text{Result}(\text{In(Arad)}, \text{Go(Sibiu)}) = \text{In(Sibiu)}$。
• 目标测试：是否在 Bucharest。
• 路径代价：道路距离之和。

3.1.2. 水壶问题

三壶容量为 12、8、3，加水目标 1 加仑：

1
2
3
4
5
6

state = (V12, V8, V3)
0 <= Vi <= Ci
initial = (0,0,0)
goal = any Vi == 1
actions = Fill(i), Empty(i), Pour(i,j)
path cost = 每步 1

倒水动作：

1
2
3

amount = min(Vi, Cj - Vj)
Vi' = Vi - amount
Vj' = Vj + amount

3.1.3. 传教士与野人

1
2
3

state = (M_left, C_left, Boat_left)
initial = (3,3,1)
goal = (0,0,0)

合法状态必须满足两岸安全：

1
2

M_left == 0 or M_left >= C_left
M_right == 0 or M_right >= C_right

动作：$\text{Cross}(m, c),\; 1 \leq m + c \leq 2$。该题检查重复状态非常必要，因为动作可逆，树搜索会反复过河。

3.2. 2020 三位数 A* 题的状态设计

题意：从三位数 $S$ 到 $G$，每步对某一位加 1 或减 1，不能进位/借位，不能进入 bad 集合，连续两步不能改同一位。

状态必须写：state = (digits, last_position)，例如：

1
2
3

(567, None)
(667, hundreds)
(677, tens)

后继函数：

1
2
3
4
5
6
7
8

for pos in {百位, 十位, 个位}:
    if pos == last_position: continue
    for delta in {-1,+1}:
        new_digit = digit[pos] + delta
        if 0 <= new_digit <= 9:
            new_number = replace(number, pos, new_digit)
            if new_number not in bad:
                successor = (new_number, pos)

路径代价：

1
2

每步 cost = 1
g(n) = 已移动步数

可采纳启发函数：$h(n) = |\text{当前百位} - \text{目标百位}| + |\text{当前十位} - \text{目标十位}| + |\text{当前个位} - \text{目标个位}|$。

理由：每一步只能改变一位且只能改变 1，因此至少需要各位数字差值之和这么多步。bad 集合和"不可连续改同一位"只会增加所需步数，不会让它更少。

若想更紧但仍简单，可考虑由于"不能连续改同一位"造成的额外等待，但考试一般写曼哈顿数字差即可。

3.3. 搜索题手算答题框架

对任何搜索树题：

1. 写 frontier 的排序依据。
2. 写已扩展节点。
3. 对每个 frontier 节点标关键值：
   • BFS/DFS：深度和生成顺序。
   • UCS：$g(n)$。
   • Greedy：$h(n)$。
   • A*：$f(n)=g(n)+h(n)$。
4. 选最优先节点。
5. 并列时按题目规则：左到右、字母序、深度优先等。

3.4. 搜索树绘制

按照题目给定的扩展顺序。扩展一个结点时，给出所有合法的后继结点；节点按照扩展顺序进行标号，只有被扩展的节点标号，目标节点被扩展时停止。

4. 考试速查

4.1. 常见判断题

• BFS 在单位代价下最优：对。
• DFS 不一定完备：对，可能无限深。
• DFS 扩展节点一定不少于 A*：错，具体取决于图和启发式。
• UCS 可以处理非单位代价并保证最优：对，要求非负代价。
• 图搜索比树搜索一定更快：不绝对，但避免重复状态通常更稳。

4.2. 最后一分钟版

• 问题形式化：状态、初始、行动/转移、目标测试、路径代价。
• 节点比状态多：父节点、动作、路径代价、深度。
• BFS：单位代价最优，空间爆炸。
• UCS：按 $g$，非负代价最优。
• DFS：省空间，不完备不最优。
• IDS：单位代价最优且省空间，考试很爱。
• 有历史限制的题，历史变量要放入状态。

4 有信息搜索

A*，启发式函数，局部搜索

目录：0. 快速定位 · 1. 最佳优先与 A* 基础 · 2. 启发式性质与证明 · 3. 局部搜索 · 4. 考试速查

0. 快速定位

• 手算 A*：看"A* 搜索流程"和"罗马尼亚例题模板"。
• 判断启发式是否 admissible/consistent：看"两个定义"。
• 多个启发式比较：看"启发式支配关系"。
• 局部搜索：看"爬山/模拟退火/束搜索/遗传算法"。

1. 最佳优先与 A* 基础

1.1. Best-First Search

最佳优先搜索维护一个优先队列 frontier，每次扩展评价函数 $f(n)$ 最小的节点：

1
2
3
4
5
6
7

best_first_search(problem, f):
    frontier = priority queue ordered by f
    insert initial node
    while frontier not empty:
        n = pop_min(frontier)
        if goal(n): return solution
        expand n and insert/update children

不同的 $f(n)$ 得到不同算法：

• 贪心最佳优先搜索：$f(n)=h(n)$。
• A* 搜索：$f(n)=g(n)+h(n)$。
• UCS：$f(n)=g(n)$。

1.2. 启发函数 h(n)

$h(n)$ 估计从节点 $n$ 到目标的最小剩余代价，如果 $n$ 是目标，则 $h(n)=0$。

例：罗马尼亚地图中，$h(n)$ 可取城市到 Bucharest 的直线距离。启发式越接近真实剩余代价 $h^*(n)$，搜索越少；但如果高估，A* 最优性可能丢失。

1.3. Greedy Best-First Search

评价函数：$f(n) = h(n)$。

特点：

• 只看"离目标看起来多近"。
• 通常很快。
• 不保证最优。
• 在图搜索中若避免重复，有限状态空间下完备；树搜索遇到环或无限空间不一定完备。

常见错误：贪心不看已经走过多远，所以可能为了小 $h$ 绕远路。

1.4. A* Search

评价函数：$f(n) = g(n) + h(n)$，其中：

• $g(n)$：从初始状态到 $n$ 的已知实际路径代价。
• $h(n)$：从 $n$ 到目标的估计最小剩余代价。
• $f(n)$：经过 $n$ 到目标的总路径代价估计。

A* 每次扩展 $f$ 最小的节点。

1.5. A* 搜索流程

1
2
3
4
5
6
7
8
9
10
11
12

frontier = priority queue by f=g+h
explored = empty
while frontier not empty:
    n = pop node with smallest f
    if goal(n): return path
    add n.state to explored
    for each successor child:
        compute g(child), h(child), f(child)
        if child.state not seen:
            push child
        else if new g is smaller:
            update parent/g/f

若题目要求手算，每个节点写：Node: g=?, h=?, f=g+h=?。并列规则按题目给定；若没给，一般按生成顺序或字母序说明即可。

2. 启发式性质与证明

2.1. 可采纳启发式 Admissible Heuristic

定义：$0 \leq h(n) \leq h^*(n)$，即永不高估真实最小剩余代价。

结论：

• 树搜索 A* 使用可采纳启发式，保证最优。
• 图搜索 A* 通常还需要一致性来简单保证最优；若只可采纳但不一致，需要允许节点重开。

典型可采纳例子：

• 八数码错位块数：不在同一位置的块的数目。
• 八数码曼哈顿距离，水平竖直移动，由于每次只能移动一个棋子，不能交换两枚棋子的位置。
• 地图路径中的直线距离。
• 三位数变换题的各位数字差绝对值之和。

2.2. 一致启发式 Consistent Heuristic

定义，也叫单调性：$h(n) \leq c(n, a, n') + h(n')$（通过 $a$ 到达 $n'$），并且 $h(\text{goal}) = 0$。

直观：估计距离满足三角不等式。

重要结论：一致性 ⇒ 可采纳。

证明套路：沿着从 $n$ 到目标的最优路径反复套用三角不等式，中间的 $h$ 抵消，得到 $h(n) \leq h^*(n)$。

一致性的好处：

• A* 图搜索第一次从 frontier 弹出某状态时，该状态的最优 $g$ 已确定。
• 不需要重新打开 closed 节点。

2.3. 可采纳但不一致例子

构造路径：$A \xrightarrow{1} B \xrightarrow{10} G$

真实代价：$h^*(A) = 11,\; h^*(B) = 10,\; h^*(G) = 0$。

定义：$h(A) = 10,\; h(B) = 5,\; h(G) = 0$。

• 可采纳：$10 \leq 11,\; 5 \leq 10$。
• 不一致：

$$h(A) \leq c(A,B) + h(B) \\ 10 \leq 1 + 5 \quad \text{（错）}$$

2.4. 启发式支配关系（占优）

若两个启发式都可采纳，且对所有节点：$h_2(n) \geq h_1(n)$，则 $h_2$ 支配 $h_1$，通常扩展节点不多于 $h_1$，因为它更接近真实代价。

2021 判断题：若 $h_1$、$h_2$ 都可采纳：

$$h_3(n) = \max(h_1(n), h_2(n)) \\ h_4(n) = \min(h_1(n), h_2(n))$$

$h_3$ 仍可采纳，而且支配 $h_4$。所以在 A* 中通常更好。但"更好"若被严格理解为所有情况下扩展节点严格更少，则不一定严格；考试一般判断"max 不差于 min"。

2.5. A* 最优性证明核心

设最优解代价为 $C^*$。若 $h$ 可采纳，则最优路径上任意 frontier 节点 $n$ 有：

$$f(n) = g(n) + h(n) \leq g(n) + h^*(n) = C^*$$

任何次优目标 $G'$ 的：$f(G') = g(G') = C' > C^*$，所以 A* 不会在所有最优路径节点被处理前选中次优目标。

2.6. 加权启发式路径算法

作业题给：$f(n) = (2-w)g(n) + wh(n)$。

若 $0 \leq w < 2$，除以正数 $(2-w)$：$f'(n) = g(n) + [w/(2-w)]h(n)$。

为了保证最优，启发项系数不能超过 1：

$$\frac{w}{2-w} \leq 1 \;\Rightarrow\; w \leq 1$$

所以 $0 \leq w \leq 1$ 保证最优。

特殊情况：

• $w=0$：$f=2g$，等价 UCS。
• $w=1$：$f=g+h$，标准 A*。
• $w=2$：$f=2h$，等价贪心搜索。

2.7. 高估不超过 c 的启发式

若：$h(n) \leq h^*(n) + c$，则 A* 返回解代价 $C'$ 满足：$C' \leq C^* + c$。

证明模板：

1. A* 终止时选择目标 $G'$，所以 $C'=f(G')$。
2. 最优路径上存在 frontier 节点 $n$。
3. $f(n)=g(n)+h(n) \leq g(n)+h^*(n)+c = C^*+c$。
4. A* 选择 $G'$，所以 $C'=f(G') \leq f(n)$。
5. 得 $C' \leq C^*+c$。

2.8. 2020 三位数 A* 手算模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

(1) 567(0) [g=0, h=3, f=3]
├── 467(1) [g=1, h=4, f=5]
├── 557(2) [g=1, h=4, f=5]
├── 568(3) [g=1, h=4, f=5]
├── 566(3) [g=1, h=4, f=5]
└── (2) 577(2) [g=1, h=2, f=3]
    ├── 477(1) [g=2, h=3, f=5]
    ├── 578(3) [g=2, h=3, f=5]
    ├── 576(3) [g=2, h=3, f=5]
    └── (3) 677(1) [g=2, h=1, f=3]
        ├── 678(3) [g=3, h=2, f=5]
        ├── 676(3) [g=3, h=2, f=5]
        └── (4) 687(2) [g=3, h=2, f=5]   <-- 注：此步 f=5 且 g=3 的节点有三个，这里随机选
            ├── 587(1) [g=4, h=3, f=7]
            ├── 688(3) [g=4, h=3, f=7]
            ├── 686(3) [g=4, h=3, f=7]
            └── (5) 787(1) [g=4, h=1, f=5]
                ├── 797(2) [g=5, h=2, f=7]
                ├── 788(3) [g=5, h=2, f=7]
                ├── 786(3) [g=5, h=2, f=7]
                └── (6) 777(2) [g=5, h=0, f=5]   <-- 目标节点

2.9. 2021 搜索树题通法

题目给一棵已经扩展 A、B 的树，问不同算法下一步扩展谁：

• DFS：看当前最深、最左/最右规则。
• UCS：算 $g(n)$，选最小。
• Greedy：看 $h(n)$，选最小。
• A*：算 $f(n)=g(n)+h(n)$，选最小。

注意：题目常规定"子节点从左到右展开；并列按字母序"，必须照做。

3. 局部搜索

3.1. Local Search 局部搜索

局部搜索不关心完整路径，只关心当前状态本身。适合：

• 状态空间巨大。
• 只要最终配置，不需要行动序列。

典型：N 皇后、排课、布局优化。

核心思想：

1
2
3

current = some state
repeat:
    move to a neighbor according to objective function

3.2. Hill-Climbing 爬山法

每步选择邻居中评价最好的状态。

优点：内存极小；实现简单。

缺点：

• 局部最优 (local maximum/minimum)。
• 平台 (plateau)：邻居评价一样，走不动。
• 山脊 (ridge)：需要一串绕行才能上升，单步贪心困难。

变体：

• 随机重启爬山：从多个随机初始点开始。
• first-choice hill climbing：随机看邻居，找到更好就走。
• stochastic hill climbing：按改进程度概率选择。

3.3. Simulated Annealing 模拟退火

允许以一定概率走向更差状态，避免局部最优。接受更差状态的概率：$P = \exp(\Delta E / T)$。若是最大化问题，$\Delta E = \text{value(new)} - \text{value(current)}$，更差时为负。温度 $T$ 越高越容易接受坏动作，越低越像爬山。

流程：

1
2
3
4
5
6
7
8

current = initial
for t = 1..:
    T = schedule(t)
    if T == 0: return current
    next = random neighbor
    DeltaE = value(next) - value(current)
    if DeltaE > 0: current = next
    else current = next with probability exp(DeltaE/T)

理论：若降温足够慢，可收敛到全局最优；实际中用于近似优化。

3.4. Local Beam Search 局部束搜索

同时保留 $k$ 个状态：

1
2
3
4

start with k random states
repeat:
    generate all successors of k states
    choose best k among all successors

区别于随机重启：

• 随机重启是多条搜索互不交流。
• 束搜索中好的状态会占据资源，信息会共享。

缺点：容易所有束集中到同一区域，失去多样性。

3.5. Genetic Algorithm 遗传算法

基本元素：

• 个体：候选解，通常编码为字符串。
• 适应度函数 (fitness)：评价个体好坏。
• 选择 (selection)：适应度高的更容易繁殖。
• 交叉 (crossover)：两个父代片段组合。
• 变异 (mutation)：随机修改少量基因。

流程：

1
2
3
4
5
6
7

population = random individuals
repeat:
    evaluate fitness
    select parents
    crossover
    mutate
    form next generation

优点：全局探索能力强。缺点：参数多、收敛慢、不保证最优。

4. 考试速查

4.1. 常见判断题

• 可采纳启发式永不高估：对。
• 一致启发式一定可采纳：对。
• 可采纳启发式一定一致：错。
• $\max(h_1, h_2)$ 若二者可采纳，仍可采纳：对。
• 贪心最佳优先搜索一定最优：错。
• A* 中 $g$ 是已经走过的代价，$h$ 是估计剩余代价：对。

4.2. 最后一分钟版

• Greedy：$f=h$，快但不最优。
• A*：$f=g+h$，$h$ 可采纳/一致时保证最优。
• Admissible：$h \leq h^*$。
• Consistent：$h(n) \leq c(n, n') + h(n')$。
• 一致推出可采纳。
• max 组合启发式比 min 更强。
• 局部搜索不保路径，只保当前状态；爬山怕局部最优，退火能偶尔走差。