COMP4431 人工智能:从搜索、博弈、CSP 到机器学习与 Agent

人工智能不等于神经网络,更不等于调用一个大模型 API。一个完整的 AI 系统至少需要回答:怎样表示状态,怎样搜索行动序列,怎样在约束下求解,怎样面对对手,怎样从数据中学习,以及怎样在环境反馈中长期决策。

COMP4431 Artificial Intelligence 覆盖的是这条经典主线。本文把课程内容整理为一套连贯框架,并在最后说明这些基础怎样连接到今天的 Agent、深度学习与强化学习系统。

配套讲义

COMP4431:用 Agent 建立课程复习 RAG

1. 先把问题写成 Agent

理性 Agent 根据感知历史选择使期望效用最大的行动。一个任务环境可用 PEAS 描述:

  • Performance measure:怎样衡量好坏;
  • Environment:Agent 所处环境;
  • Actuators:可以执行什么动作;
  • Sensors:能观察到什么。

环境还可按以下维度分类:完全/部分可观测,确定/随机,静态/动态,离散/连续,单 Agent/多 Agent。

这些分类决定方法。例如完全可观测、确定、离散的最短路径适合图搜索;部分可观测环境需要 belief state;对抗环境需要 minimax;随机长期决策需要 MDP。

2. 状态空间与搜索问题

搜索问题由五部分组成:

(S,s0,A,T,G),(S,s_0,A,T,G),

其中 SS 是状态集合,s0s_0 是初始状态,AA 是动作集合,T(s,a)T(s,a) 是状态转移,GG 是目标测试。若还考虑代价,则每条边有 c(s,a,s′)c(s,a,s')。

搜索算法评价通常看:

  • completeness:有解时能否找到;
  • optimality:能否找到最优解;
  • time complexity;
  • space complexity。

3. 无信息搜索

BFS

Breadth-first search 按深度扩展节点。若每步代价相同,它完备且最优。分支因子为 bb、最浅解深度为 dd 时,时间和空间约为

O(bd).O(b^d).

空间消耗是 BFS 的主要瓶颈。

DFS

Depth-first search 优先沿一条路径深入,空间约为 O(bm)O(bm),其中 mm 是最大深度;但在无限状态空间中可能不完备,也不保证最优。

UCS 每次扩展累计路径代价

g(n)g(n)

最小的节点。边代价均为正时,它完备且最优。Dijkstra 算法可以看作图上的 UCS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from heapq import heappush, heappop

def uniform_cost_search(start, is_goal, neighbors):
frontier = [(0, start, [])]
best = {start: 0}

while frontier:
cost, state, path = heappop(frontier)
if cost != best[state]:
continue
if is_goal(state):
return path, cost
for next_state, action, step_cost in neighbors(state):
new_cost = cost + step_cost
if new_cost < best.get(next_state, float("inf")):
best[next_state] = new_cost
heappush(frontier, (new_cost, next_state, path + [action]))
return None

4. 启发式搜索与 A*

启发函数 h(n)h(n) 估计从节点 nn 到目标的剩余代价。Greedy best-first search 只看 h(n)h(n),速度可能快,但不保证最优。

A* 使用

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

若 hh 是 admissible 的,即

0≤h(n)≤h∗(n),0\leq h(n)\leq h^*(n),

它从不高估真实剩余代价,树搜索版 A* 可保证最优。图搜索常要求更强的 consistency:

h(n)≤c(n,n′)+h(n′).h(n)\leq c(n,n')+h(n').

一致性相当于启发函数满足三角不等式,使 ff 沿路径不下降。

启发函数通常来自 relaxed problem。例如八数码中,忽略方块阻挡可得到 Manhattan distance。越接近真实代价且计算便宜的启发函数,扩展节点通常越少。

5. Constraint Satisfaction Problem

CSP 由变量、取值域和约束组成:

(X,D,C).(X,D,C).

普通搜索关心到达哪个状态;CSP 关心怎样给全部变量赋值并满足约束。基本方法是 backtracking,但高效求解依赖三类策略。

变量选择: MRV 优先选择剩余合法值最少的变量,先处理最可能失败的位置。

取值顺序: LCV 优先选择对其他变量限制最少的值。

约束传播: forward checking 在赋值后删除邻居不合法值;arc consistency 进一步确保每个值在相邻变量中都有支持。

这些方法体现了通用原则:尽早发现冲突,比在深层搜索后回退更便宜。

6. 对抗搜索:Minimax

双人零和博弈中,MAX 希望效用最大,MIN 希望效用最小。递归价值为

V(s)={U(s),s 是终局,max⁡aV(T(s,a)),s 轮到 MAX,min⁡aV(T(s,a)),s 轮到 MIN.V(s)= \begin{cases} U(s), & s\text{ 是终局},\\ \max_{a}V(T(s,a)), & s\text{ 轮到 MAX},\\ \min_{a}V(T(s,a)), & s\text{ 轮到 MIN}. \end{cases}

完整博弈树通常太大,因此限定深度并使用 evaluation function 估计叶节点。

Alpha-beta pruning 维护:

  • α\alpha:MAX 已知可以保证的最好值;
  • β\beta:MIN 已知可以保证的最好值。

当 α≥β\alpha\geq\beta 时,剩余分支不可能影响祖先选择,可以剪掉。剪枝不改变 minimax 结果,效率高度依赖走法排序;理想排序可把搜索规模从约 O(bd)O(b^d) 降到 O(bd/2)O(b^{d/2})。

7. 知识表示与概率推理

符号 AI 用命题、谓词和规则表示知识,再通过推理规则得到结论。它的优势是结构清晰、可检查;困难在于知识获取、感知到符号的转换,以及现实世界的不确定性。

Bayes 公式为

P(H∣E)=P(E∣H)P(H)P(E).P(H\mid E)=\frac{P(E\mid H)P(H)}{P(E)}.

它提醒我们,证据的解释必须结合 prior。一个准确率很高的检测器,在极低患病率人群中也可能有较低的阳性预测值。

朴素 Bayes 假设特征在给定类别后条件独立:

P(x∣y)=∏j=1pP(xj∣y).P(x\mid y)=\prod_{j=1}^pP(x_j\mid y).

假设通常不完全真实,但在文本等高维稀疏任务中仍可成为很强的 baseline。

8. 机器学习:从经验风险到泛化

监督学习希望从数据 (xi,yi)(x_i,y_i) 学到函数 fθf_\theta。经验风险为

R^(θ)=1n∑i=1nℓ(fθ(xi),yi).\hat R(\theta)=\frac1n\sum_{i=1}^n \ell(f_\theta(x_i),y_i).

训练误差低并不代表泛化好。常见控制手段包括验证集、交叉验证、正则化、早停和数据增强。

课程中的算法可以按任务理解:

任务 代表方法 核心假设
回归 linear regression 条件均值近似线性
分类 logistic regression / SVM 存在可学习决策边界
聚类 k-means 簇近似球形且由欧氏距离表达
表示学习 neural network 多层非线性可组合出有效特征

9. SVM:最大化分类间隔

线性可分时,SVM 求解

min⁡w,b12∥w∥22\min_{w,b}\frac12\|w\|_2^2

满足

yi(wTxi+b)≥1.y_i(w^Tx_i+b)\geq1.

几何间隔与 1/∥w∥1/\|w\| 成正比,所以最小化 ∥w∥2\|w\|^2 等价于最大化间隔。

软间隔引入 slack variable:

min⁡w,b,ξ12∥w∥2+C∑iξi,\min_{w,b,\xi} \frac12\|w\|^2+C\sum_i\xi_i,

yi(wTxi+b)≥1−ξi,ξi≥0.y_i(w^Tx_i+b)\geq1-\xi_i, \qquad \xi_i\geq0.

CC 大时更重视训练误差,CC 小时允许更多违例以获得更宽间隔。kernel trick 则把内积替换为 K(xi,xj)K(x_i,x_j),在隐式高维空间构造非线性边界。

10. 神经网络与反向传播

一层神经元计算

z=Wx+b,h=σ(z).z=Wx+b,\qquad h=\sigma(z).

多层网络通过复合函数表示复杂映射。反向传播并不是一种神秘算法,而是链式法则的高效复用。若

L=L(h(L)),L=L(h^{(L)}),

则梯度从输出层向前递推:

∂L∂W(l)=∂L∂z(l)∂z(l)∂W(l).\frac{\partial L}{\partial W^{(l)}} =\frac{\partial L}{\partial z^{(l)}} \frac{\partial z^{(l)}}{\partial W^{(l)}}.

CNN 通过局部连接和权重共享利用空间结构;RNN 通过隐藏状态处理序列;LSTM 用门控缓解长期依赖中的梯度问题。模型结构的价值来自对数据结构的归纳偏置,而不只是参数更多。

11. 强化学习与 MDP

MDP 由

(S,A,P,R,γ)(S,A,P,R,\gamma)

组成。策略 π(a∣s)\pi(a\mid s) 定义在状态下选择动作的概率。状态价值为

Vπ(s)=Eπ[∑t=0∞γtRt+1∣S0=s].V^\pi(s)=E_\pi\left[\sum_{t=0}^\infty \gamma^tR_{t+1}\mid S_0=s\right].

Bellman expectation equation:

Vπ(s)=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)[r+γVπ(s′)].V^\pi(s)=\sum_a\pi(a\mid s) \sum_{s',r}p(s',r\mid s,a) [r+\gamma V^\pi(s')].

最优价值满足

V∗(s)=max⁡a∑s′,rp(s′,r∣s,a)[r+γV∗(s′)].V^*(s)=\max_a \sum_{s',r}p(s',r\mid s,a) [r+\gamma V^*(s')].

动态规划假设知道环境模型;Q-learning 则直接学习 action value:

Q(s,a)←Q(s,a)+α[r+γmax⁡a′Q(s′,a′)−Q(s,a)].Q(s,a)\leftarrow Q(s,a)+\alpha [r+\gamma\max_{a'}Q(s',a')-Q(s,a)].

括号内是 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
2
3
问题定义 -> 最小 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/

作者

方楚鸣

发布于

2026-11-16

更新于

2026-11-16

许可协议

Click to play