Midterm 复习资料|范围与搜索
讲师通知的考试安排与范围、Tutorial 1 概念点、搜索策略、爬山法与 A* 的计算、英文作答与成立条件。
手机上宽表格可左右滑动;自测答案默认收起,点击题目下方按钮查看。
使用边界:2026-11-04 课堂期中复习,非官方材料;考试安排按讲师通知整理,正式要求以讲师通知和课堂公告为准。主体覆盖 L01–L07、Tutorial 1–5 与 Assignment 1;通知列出的课件只到 Lecture 7,L08 放在第 08 节作范围存疑附节。练习题均为自拟,不是往年真题或预测卷。
复习资料:范围与搜索 · 概率与逻辑 · 机器学习与聚类 · 神经网络与 L08 附节
先做题再看解析:A 搜索 · B 概率 · C 逻辑 · D 机器学习 · E 聚类与神经网络 · F 论文与 PyTorch
00|考试信息与范围边界
| 项目 | 内容 | 出处 |
|---|---|---|
| 形式 | In-Class Test (Mid-term),课堂内笔试,不写代码 | 讲师通知 |
| 时间 | 2026-11-04(周三,第 10 周)15:40–18:10,共 2.5 小时 | 讲师通知 |
| 地点 | PolyU N001 | 讲师通知 |
| 占比 | 8% | L01 p.19 |
| 范围 | Week 1(9-02)至 Week 8(10-21):Lecture slides 1–7、Tutorial slides、与期中相关的 assignment | 讲师通知 |
| 可带 | 一张 A4 纸双面手写笔记(TA 会检查,打印件不行);普通非编程计算器 | 讲师通知 |
| 必带 | 学生证 | 讲师通知 |
| 纪律 | 缺考严重影响成绩;严禁抄袭;有疑问直接问讲师 | 讲师通知 |
覆盖范围:本册主体对应 L01–L07、Tutorial 1–5(含 T03a 搜索练习和 T03 PyTorch notebook 的概念点)以及 Assignment 1 的五类题型(BFS 表格、爬山搜索树、DFS 用栈的理由、贝叶斯、化范式)。课程表上第 8 周(10-21)讲的是 Lecture 8 Information Systems,通知列出的课件却只到 Lecture 7,所以 L08 只在第 08 节放精简速记,是否考以讲师答复为准。第 9 周的嘉宾讲座不在通知范围内,本册不收。
不写代码意味着什么:T03 的 PyTorch 内容按概念复习,例如张量形状、训练循环的步骤顺序、梯度为什么要清零、网络每层输出尺寸,写在第 06、07 节。计算器只能做数值,sigmoid、softmax 里的 eˣ 和 ln 要会按,推导步骤仍要写在卷面上。
Tutorial 1(读论文)的概念点:这一讲没有计算,只可能考概念,英文要能说清以下几句。
- 📌 Papers in top conferences and journals are generally reliable; preprints and workshop papers need extra checking.(T01 p.4–12)
- 📌 Google Scholar searches broadly, DBLP gives accurate venue information and BibTeX, and the library provides full text.(T01 p.4–12)
- 📌 A paper usually has eight parts; the Introduction is the most important because it states what is broken or missing.(T01 p.13–21)
- 📌 Read a paper in several passes: the first pass only decides whether to keep reading; later passes may skip the mathematics.(T01 p.22–28)
- 📌 Surveys give future directions and recent top-conference papers give research gaps; a new method either transfers an idea from another field or improves an existing method.(T01 p.29–35)
怎么用:每块分三件事——必须会算的、必须会用英文说清的、成立条件和常见误区。📌 标的是考点,括号里是回查出处,格式为讲次加 PDF 页序(例如 L02 p.61 指 Lecture 2 课件 PDF 的第 61 页,部分课件的页脚印刷页码与页序不一致,以页序为准)。读完一块就去做对应的自拟练习,做完再展开解析。
01|搜索:问题表述、盲目搜索与启发式
必须会算的
- 📌 BFS 与 DFS 的复杂度代入:BFS 时间、空间都是 O(bᵐ⁺¹),DFS 时间 O(bᵈ)、空间 O(d·b)。b 是分支因子,m 是最浅解的深度,d 是树深,d 可以远大于 m(L02 p.15、p.24–26、p.36–38)。
- 📌 Open/Close 表的手推:open 用队列就是 BFS,用栈就是 DFS;展开一个节点时,已在 Open 或 Close 里的节点不重复加入(L02 p.18、p.22、p.31;T02 p.7)。
- 📌 状态空间计数:八数码生成测试共 9! = 362,880 种排列;井字棋利用对称性后第一层 3 种、第二层 12 种,上限 12×7! = 60,480(L02 p.13、p.44)。
- 📌 八数码两个启发函数:不在位方块数、各方块到目标位置的距离之和;课件结论是距离之和更准(L02 p.54)。
- 📌 有向图上手推 BFS、DFS:箭头方向决定孩子;按题面给的顺序规则加入(升序或降序),DFS 想先访问的孩子要最后入栈;出队时才判目标;每一步都写 Open 和 Close(T02 p.5–10;A1 Q1、Q3)。
- 📌 爬山法:每步取评价最好的邻居,没有更好的邻居就停;四皇后题里状态是每列皇后的行号,邻居是交换两列,目标函数是冲突对数,同分时按题面规则取(L02 p.48;T03a p.11–14)。
- 📌 爬山法搜索历史树:每层画出当前节点的全部孩子并标分,只展开最好的一个,落选的兄弟不再展开,最好的孩子不比当前好就停,不回溯(L02 p.47;A1 Q2)。
- 📌 贪心与搜索空间:数字树上每步取最大,和为 19,全局最优是 23;V 个词、长度 L 的序列共 Vᴸ 个(5⁴ = 625);beam search 每步保留得分最高的 K 条部分序列,K = 1 就是贪心(T03a p.15–19)。
- 📌 A* 手推:f = g + h,每次从 Open 取 f 最小的节点;新路径让 g 变小就更新,已在 Close 里的要移回 Open;目标节点被取出时才结束(L02 p.55、p.61–67;T03a p.25–33)。
必须会用英文说清的
- 📌 A search problem is defined by the current state, the goal state, the actions and their cost; the solution is a path, not just the final state.(L02 p.4)
- 📌 Search strategies are compared by completeness, optimality, time complexity and space complexity.(L02 p.7)
- 📌 BFS expands the shallowest node first using a FIFO queue; DFS expands the deepest node first using a LIFO stack.(L02 p.18、p.31)
- 📌 Best-first search orders nodes by h(n) only; Algorithm A orders nodes by f(n) = g(n) + h(n).(L02 p.52、p.55)
- 📌 If h(n) ≤ h*(n) for every node, Algorithm A is called A*, and A* is admissible: it is guaranteed to find an optimal path when one exists.(L02 p.58、p.60)
- 📌 Hill climbing can get stuck at a local maximum, on a plateau, or on a ridge.(L02 p.50;T03a p.7–9)
- 📌 DFS uses a stack because the node added last is expanded first, so the search keeps going deeper; with a queue the same algorithm becomes BFS.(L02 p.22、p.31;A1 Q3)
成立条件和常见误区
- BFS 完备、找到的是边数最少的解;边上代价不相等时,边数最少不等于代价最小(L02 p.24–26)。
- DFS 在有环或无限深的空间里不完备;加 Close 表查重后,在有限空间里才完备。去掉查重的 DFS 在有环图上可能无限循环(L02 p.36–38;T02 p.15)。
- admissible 是算法的属性,指保证找到最优解;BFS 在课件里也被称为 admissible(L02 p.58)。启发函数满足 h ≤ h* 才能把 Algorithm A 叫作 A*。
- A* 碰到目标时不能立刻停,要等目标从 Open 被取出(L02 p.65;T03a p.29)。补充:图搜索若把 Close 里的节点永久关闭,需要启发函数一致;只满足 h ≤ h* 时要允许重开节点(T03a p.31–34)。
- 最佳优先只看 h,不完备、不最优(L02 p.57)。爬山法也只保证停在局部最优。
- 课件里 ridge 指山脊;平台(plateau)是附近评价都一样,局部最大是附近没有更好的点(L02 p.50;T03a p.7–9)。
- 访问顺序不等于解路径,答题时两样分开写(T02 p.7)。
- 题面的排序规则逐条照做:同层节点按字母序出队、Close 表新节点放前面还是后面、目标在哪一步判定,课件例子和题面不同时按题面,并写一句采用的读法(L02 p.19;A1 Q1)。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。