算法分析与设计

Appearance

4.10 综合练习 ​

"练习是检验理解的唯一标准。" — 教学原则

层次一：基础证明 ​

练习 1：DFS 环检测 ​

题目：证明 DFS 发现后向边当且仅当图有环。

提示：

  • （→）后向边 u → v 意味着 v 是 u 的祖先
  • （←）DFS 沿环遍历，最后一条边指向灰色顶点

练习 2：切割性质证明 ​

题目：用切割性质证明 Kruskal 算法的正确性。

提示：

  • 每次选择最小边 e
  • 证明 e 必在某棵 MST 中（使用切割性质）
  • 归纳完成

练习 3：Dijkstra 追踪 ​

题目：手动追踪 Dijkstra 优先队列状态。

图结构：
    A --4--> B --1--> C
    |        |        |
    1        2        5
    v        v        v
    D --3--> E --2--> F

源点：A

要求：

  1. 画出优先队列的每一步状态
  2. 记录每次取出的顶点和距离更新
  3. 写出最终的最短路径树

练习 4：白色路径定理 ​

题目：证明白色路径定理。

陈述：顶点 v 是顶点 u 的后代，当且仅当在发现 u 时，存在一条从 u 到 v 的全由白色顶点组成的路径。

练习 5：并查集复杂度 ​

题目：计算并查集路径压缩后的树高度。

初始：10 个顶点，各自为根
操作：
union(0, 1), union(2, 3), union(4, 5), union(6, 7), union(8, 9)
union(0, 2), union(4, 6), union(0, 4), union(0, 8)
find(9)  # 触发路径压缩

问题：
1. 画出路径压缩后的树结构
2. 计算树高度
3. 解释 α(n) 为什么 ≤ 4

层次二：LLM 协同 ​

练习 6：课程排课建模 ​

场景：某专业有 8 门必修课，先修关系如下：

  • C1 需要先修 C0
  • C2 需要先修 C0
  • C3 需要先修 C1, C2
  • C4 需要先修 C3
  • C5 需要先修 C3
  • C6 需要先修 C4, C5
  • C7 需要先修 C6

LLM 任务：

让 LLM：
1. 建模为图问题（定义顶点、边）
2. 实现拓扑排序
3. 求合法修课顺序

人判断：

  • 建模是否正确？
  • 是否包含环检测？
  • 如果加入约束"C5 需要先修 C7"，会发生什么？

练习 7：网络路由建模 ​

场景：某网络有 6 个路由器，延迟矩阵：

     R1   R2   R3   R4   R5   R6
R1   0    10   inf  30   inf  inf
R2   10   0    20   inf  inf  inf
R3   inf  20   0    10   20   inf
R4   30   inf  10   0    inf  20
R5   inf  inf  20   inf  0    10
R6   inf  inf  inf  20   10   0

LLM 任务：

让 LLM：
1. 建模为图问题
2. 选择合适的最短路径算法
3. 求 R1 到所有路由器的最短路径

人判断：

  • 建模是否正确？
  • 算法选择是否正确（为什么不用 Bellman-Ford）？
  • 如果 R3→R4 的延迟变为 -5，还能用 Dijkstra 吗？

练习 8：物流分配建模 ​

场景：某物流公司有 3 个仓库、5 个配送中心、10 个零售商。每条运输线有容量限制。

LLM 任务：

让 LLM：
1. 建模为网络流问题
2. 定义源点、汇点
3. 解释容量约束

人判断：

  • 建模是否正确？
  • 容量约束是否正确建模？
  • 如何从最大流结果得到实际配送方案？

练习 9：LLM 实现拓扑排序 ​

LLM 任务：

让 LLM 实现拓扑排序。

图结构：
顶点：{A, B, C, D, E}
边：A→B, A→C, B→D, C→D, D→E

要求：
1. 使用 Kahn 算法（入度法）
2. 包含环检测
3. 如果有环，返回错误

人判断：

  • 构造让 LLM 忽略环检测的测试用例
  • 例如：添加边 E→A，形成环

练习 10：LLM 选择最短路径算法 ​

场景：

场景顶点数边数权重特征任务
A10^410^5非负单源
B10^410^5可能有负单源
C10^310^6非负全源
D10^610^7非负单源

LLM 任务：

对每个场景，让 LLM 选择最短路径算法，并解释理由。

人判断：

  • LLM 的选择是否正确？
  • 理由是否充分？
  • 是否考虑了稀疏性？

层次三：Agent 设计 ​

练习 11：图建模 Agent ​

目标：设计一个 Agent，输入自然语言问题描述，自动识别是否为图问题，建模为图，选择算法。

设计要点：

输入：自然语言问题描述

输出：
- 是否为图问题（布尔值 + 置信度）
- 图建模（顶点、边、权）
- 推荐算法类别
- 算法选择理由

流程：
1. 关键词识别（依赖、路径、分配、连通）
2. 实体抽取（识别可能的顶点和边）
3. 关系建模（定义边和权重）
4. 算法匹配（基于图特性选择）
5. 置信度评估

测试用例：

  • "课程排课问题"
  • "配送路线优化"
  • "社交网络好友推荐"
  • "蛋白质相互作用分析"

练习 12：知识图谱 RAG Agent ​

目标：设计一个 Agent，基于知识图谱进行问答。

设计要点：

输入：自然语言问题

输出：答案 + 推理路径

流程：
1. 实体识别（从问题中提取实体）
2. 关系抽取（识别问题中的关系）
3. KG 查询（构建 SPARQL 或图遍历）
4. 路径检索（BFS/DFS 找相关路径）
5. 上下文构建（将路径转为文本）
6. LLM 生成答案

示例：

问题："姚明的妻子的出生地是哪里？"

推理路径：
姚明 → 配偶 → 叶莉 → 出生地 → 上海

答案："姚明的妻子叶莉出生于上海。"

练习 13：推理验证 Agent ​

目标：设计一个 Agent，验证 LLM 推理链的一致性。

设计要点：

输入：LLM 的推理链（文本）

输出：
- 推理图（DAG）
- 一致性评估（通过/警告/失败）
- 问题列表（如有）

流程：
1. 解析推理链（识别前提和结论）
2. 构建推理图（DAG）
3. 检测循环矛盾（环检测）
4. 检查前提完整性
5. 验证推理步骤

示例：

推理链：
"所有猫都是动物。Tom 是一只猫。所以 Tom 是动物。"

推理图：
P1: 所有猫 → 动物
P2: Tom → 猫
C: Tom → 动物

一致性：通过

练习 14：图算法选择 Skill ​

目标：设计一个 Skill，输入图特性，自动选择算法和表示。

设计要点：

输入：
- 图特性（顶点数、边数、是否有向、是否有权）
- 任务类型（遍历、最短路、生成树、流）
- 特殊约束（负权、环检测）

输出：
- 推荐的图表示
- 推荐的算法
- 复杂度预估
- 实现代码

决策树：
- E << V² → 邻接表
- E ≈ V² → 邻接矩阵
- 单源最短路 + 非负权 → Dijkstra
- 单源最短路 + 可能负权 → Bellman-Ford
- 全源最短路 + 稠密 → Floyd-Warshall

小结 ​

层次一：基础证明和手工计算，巩固理论理解。

层次二：LLM 协同练习，培养审查和判断能力。

层次三：Agent 设计，综合应用人机分工原则。

评分标准 ​

层次通过标准
层次一正确完成 3/5 题
层次二正确判断 4/5 题
层次三完成 2/4 个设计

新时代的算法课程