COMP4431 人工智能:从搜索、博弈、CSP 到机器学习与 Agent
人工智能不等于神经网络,更不等于调用一个大模型 API。一个完整的 AI 系统至少需要回答:怎样表示状态,怎样搜索行动序列,怎样在约束下求解,怎样面对对手,怎样从数据中学习,以及怎样在环境反馈中长期决策。
COMP4431 Artificial Intelligence 覆盖的是这条经典主线。本文把课程内容整理为一套连贯框架,并在最后说明这些基础怎样连接到今天的 Agent、深度学习与强化学习系统。
配套讲义
- Week 1:人工智能概览与历史
- Lecture 1:AI 历史与基本问题
- Lecture 2:理性 Agent 与搜索
- Lecture 3:搜索与约束满足
- Lecture 4:CSP、博弈与剪枝
- Week 5:博弈与多智能体
- Lecture 5:机器学习、聚类与分类
- Lecture 6:分类器与支持向量机
- Lecture 7:机器学习专题
- Lecture 8:深度学习、RNN 与 CNN
- 强化学习与 Agentic AI
1. 先把问题写成 Agent
理性 Agent 根据感知历史选择使期望效用最大的行动。一个任务环境可用 PEAS 描述:
- Performance measure:怎样衡量好坏;
- Environment:Agent 所处环境;
- Actuators:可以执行什么动作;
- Sensors:能观察到什么。
环境还可按以下维度分类:完全/部分可观测,确定/随机,静态/动态,离散/连续,单 Agent/多 Agent。
这些分类决定方法。例如完全可观测、确定、离散的最短路径适合图搜索;部分可观测环境需要 belief state;对抗环境需要 minimax;随机长期决策需要 MDP。
2. 状态空间与搜索问题
搜索问题由五部分组成:
其中 是状态集合, 是初始状态, 是动作集合, 是状态转移, 是目标测试。若还考虑代价,则每条边有 。
搜索算法评价通常看:
- completeness:有解时能否找到;
- optimality:能否找到最优解;
- time complexity;
- space complexity。
3. 无信息搜索
BFS
Breadth-first search 按深度扩展节点。若每步代价相同,它完备且最优。分支因子为 、最浅解深度为 时,时间和空间约为
空间消耗是 BFS 的主要瓶颈。
DFS
Depth-first search 优先沿一条路径深入,空间约为 ,其中 是最大深度;但在无限状态空间中可能不完备,也不保证最优。
Uniform-cost search
UCS 每次扩展累计路径代价
最小的节点。边代价均为正时,它完备且最优。Dijkstra 算法可以看作图上的 UCS。
1 | from heapq import heappush, heappop |
4. 启发式搜索与 A*
启发函数 估计从节点 到目标的剩余代价。Greedy best-first search 只看 ,速度可能快,但不保证最优。
A* 使用
若 是 admissible 的,即
它从不高估真实剩余代价,树搜索版 A* 可保证最优。图搜索常要求更强的 consistency:
一致性相当于启发函数满足三角不等式,使 沿路径不下降。
启发函数通常来自 relaxed problem。例如八数码中,忽略方块阻挡可得到 Manhattan distance。越接近真实代价且计算便宜的启发函数,扩展节点通常越少。
5. Constraint Satisfaction Problem
CSP 由变量、取值域和约束组成:
普通搜索关心到达哪个状态;CSP 关心怎样给全部变量赋值并满足约束。基本方法是 backtracking,但高效求解依赖三类策略。
变量选择: MRV 优先选择剩余合法值最少的变量,先处理最可能失败的位置。
取值顺序: LCV 优先选择对其他变量限制最少的值。
约束传播: forward checking 在赋值后删除邻居不合法值;arc consistency 进一步确保每个值在相邻变量中都有支持。
这些方法体现了通用原则:尽早发现冲突,比在深层搜索后回退更便宜。
6. 对抗搜索:Minimax
双人零和博弈中,MAX 希望效用最大,MIN 希望效用最小。递归价值为
完整博弈树通常太大,因此限定深度并使用 evaluation function 估计叶节点。
Alpha-beta pruning 维护:
- :MAX 已知可以保证的最好值;
- :MIN 已知可以保证的最好值。
当 时,剩余分支不可能影响祖先选择,可以剪掉。剪枝不改变 minimax 结果,效率高度依赖走法排序;理想排序可把搜索规模从约 降到 。
7. 知识表示与概率推理
符号 AI 用命题、谓词和规则表示知识,再通过推理规则得到结论。它的优势是结构清晰、可检查;困难在于知识获取、感知到符号的转换,以及现实世界的不确定性。
Bayes 公式为
它提醒我们,证据的解释必须结合 prior。一个准确率很高的检测器,在极低患病率人群中也可能有较低的阳性预测值。
朴素 Bayes 假设特征在给定类别后条件独立:
假设通常不完全真实,但在文本等高维稀疏任务中仍可成为很强的 baseline。
8. 机器学习:从经验风险到泛化
监督学习希望从数据 学到函数 。经验风险为
训练误差低并不代表泛化好。常见控制手段包括验证集、交叉验证、正则化、早停和数据增强。
课程中的算法可以按任务理解:
| 任务 | 代表方法 | 核心假设 |
|---|---|---|
| 回归 | linear regression | 条件均值近似线性 |
| 分类 | logistic regression / SVM | 存在可学习决策边界 |
| 聚类 | k-means | 簇近似球形且由欧氏距离表达 |
| 表示学习 | neural network | 多层非线性可组合出有效特征 |
9. SVM:最大化分类间隔
线性可分时,SVM 求解
满足
几何间隔与 成正比,所以最小化 等价于最大化间隔。
软间隔引入 slack variable:
大时更重视训练误差, 小时允许更多违例以获得更宽间隔。kernel trick 则把内积替换为 ,在隐式高维空间构造非线性边界。
10. 神经网络与反向传播
一层神经元计算
多层网络通过复合函数表示复杂映射。反向传播并不是一种神秘算法,而是链式法则的高效复用。若
则梯度从输出层向前递推:
CNN 通过局部连接和权重共享利用空间结构;RNN 通过隐藏状态处理序列;LSTM 用门控缓解长期依赖中的梯度问题。模型结构的价值来自对数据结构的归纳偏置,而不只是参数更多。
11. 强化学习与 MDP
MDP 由
组成。策略 定义在状态下选择动作的概率。状态价值为
Bellman expectation equation:
最优价值满足
动态规划假设知道环境模型;Q-learning 则直接学习 action value:
括号内是 temporal-difference error。
12. 从经典 Agent 到 LLM Agent
现代 LLM Agent 仍然可以用经典框架分析:
| 经典概念 | LLM Agent 中的对应 |
|---|---|
| state | 对话历史、环境观察、工作记忆 |
| action | 工具调用、回复、写文件、执行代码 |
| transition | 工具和环境返回的新状态 |
| heuristic | 模型对下一步有用性的判断 |
| planning | task decomposition / search |
| memory | 检索库、摘要、外部状态 |
| reward | 自动评测、人类反馈、任务是否完成 |
LLM 并不会自动解决可靠性问题。一个工程化 Agent 仍需要:受约束的工具接口、状态管理、失败重试、停止条件、可观测日志、权限边界和可重复评测。
13. 实现 AI 算法时的工程习惯
1 | 问题定义 -> 最小 baseline -> 明确评价指标 |
对搜索算法,记录 expanded nodes、frontier size 和 path cost;对分类器,记录 confusion matrix、precision/recall 和校准;对 RL,至少报告多随机种子的均值与方差;对 Agent,记录任务成功率、工具错误率、成本和平均步数。
14. 自测清单
- 能否用 PEAS 描述一个真实任务?
- 能否比较 BFS、DFS、UCS 与 A* 的完备性和最优性?
- 能否解释 admissible 与 consistent heuristic?
- 能否写出 CSP 的 MRV、LCV 与约束传播?
- 能否手工执行 minimax 与 alpha-beta pruning?
- 能否从最大间隔推导 SVM 目标?
- 能否用链式法则解释反向传播?
- 能否写出 Bellman equation 和 Q-learning 更新?
- 能否把 LLM Agent 映射回 state、action、transition 与 evaluation?
经典 AI 的意义不是怀旧。搜索、约束、博弈、概率和序贯决策,今天仍然是构建可靠 Agent 与智能系统时最常用的思考语言。
COMP4431 人工智能:从搜索、博弈、CSP 到机器学习与 Agent
https://richardf123.github.io/2026/11/16/comp4431-artificial-intelligence-guide/