← COMP5511 全部讲次
Q01

Midterm 自拟练习|A 搜索

自拟练习 A 搜索:英文题干,逐题折叠中文解析、英文参考答案与回查页码。

手机上宽表格可左右滑动;自测答案默认收起,点击题目下方按钮查看。

使用边界:2026-11-04 课堂期中复习,非官方材料;考试安排按讲师通知整理,正式要求以讲师通知和课堂公告为准。主体覆盖 L01–L07、Tutorial 1–5 与 Assignment 1;通知列出的课件只到 Lecture 7,L08 放在第 08 节作范围存疑附节。练习题均为自拟,不是往年真题或预测卷。

复习资料:范围与搜索 · 概率与逻辑 · 机器学习与聚类 · 神经网络与 L08 附节

先做题再看解析:A 搜索 · B 概率 · C 逻辑 · D 机器学习 · E 聚类与神经网络 · F 论文与 PyTorch

怎么做:先只看题面,用英文作答,写出公式和每一步,再展开解析核对。解析里的数值都用 python 复算过;每题末尾给回查出处,页码为 PDF 页序。

A 搜索

A1 · A* hand trace

Consider a directed graph with start S and goal G. Edge costs: S→A 1, S→B 4, A→B 2, A→C 5, B→C 1, B→G 6, C→G 2. Heuristic values: h(S) = 5, h(A) = 4, h(B) = 2, h(C) = 1, h(G) = 0.

(a) Run A* with an Open list and a Close list. After each expansion, write the Open list with g and f values. (b) Give the order in which nodes are expanded, the path returned and its cost.

A1 · 查看答案与解析

推理过程:每次从 Open 取 f = g + h 最小的节点;新路径让某节点的 g 变小就更新它。

展开 展开后的 Open(g, f) Close
S(f = 5) A(1, 5),B(4, 6) S
A(f = 5) B(3, 5),C(6, 7) S, A
B(f = 5) C(4, 5),G(9, 9) S, A, B
C(f = 5) G(6, 6) S, A, B, C
G(f = 6) 取出目标,结束

展开 A 时,经 A 到 B 的 g = 1 + 2 = 3,比原来的 4 小,B 的 f 从 6 降到 5;展开 B 时 C 的 g 从 6 降到 4;展开 C 时 G 的 g 从 9 降到 6。

答案:展开顺序 S, A, B, C, G;路径 S→A→B→C→G,代价 6。

English: A* always expands the node with the smallest f = g + h, updates a node when a cheaper path is found, and stops only when the goal is removed from Open.

易错点:展开 B 时 G 已经进了 Open(f = 9),这时不能停。逐项检查 h ≤ h*:h* 分别为 S 6、A 5、B 3、C 2,所以这个 h 可采纳。

回查:L02 p.55、p.60–67;T03a p.25–33。

A2 · Best-first versus A*

Use the same graph and heuristic as A1. Run greedy best-first search, which orders the Open list by h(n) only. Which path does it return, what is its cost, and why can it differ from A*?

A2 · 查看答案与解析

推理过程:Open 只按 h 排序。展开 S 得 A(h = 4)、B(h = 2),取 B;展开 B 得 C(h = 1)、G(h = 0),取 G,结束。

答案:路径 S→B→G,代价 4 + 6 = 10,比 A1 的最优代价 6 贵。

English: Best-first search ignores the cost already paid, g(n), so it may follow a path that looks close to the goal but is expensive; it is neither complete nor optimal in general.

易错点:别把这里的 best-first 和 BFS(breadth-first)混写成同一个缩写。

回查:L02 p.52、p.57。

A3 · Eight-puzzle heuristics

Goal state (0 = blank), rows from top to bottom: 1 2 3 / 4 5 6 / 7 8 0. Current state: 8 1 3 / 4 0 2 / 7 6 5.

(a) Compute h₁ = number of misplaced tiles (do not count the blank). (b) Compute h₂ = sum of the distances of the tiles from their goal positions (horizontal plus vertical moves). (c) Which heuristic is more accurate, and why?

A3 · 查看答案与解析

推理过程:逐块对照目标位置。

方块 当前位置(行, 列) 目标位置 是否不在位 距离
8 (0, 0) (2, 1) 是 3
1 (0, 1) (0, 0) 是 1
3 (0, 2) (0, 2) 否 0
4 (1, 0) (1, 0) 否 0
2 (1, 2) (0, 1) 是 2
7 (2, 0) (2, 0) 否 0
6 (2, 1) (1, 2) 是 2
5 (2, 2) (1, 1) 是 2

答案:h₁ = 5,h₂ = 3 + 1 + 2 + 2 + 2 = 10。距离之和更准,因为它能区分差一格和差三格,不在位方块数把两者都算成 1。

English: The sum of distances is more accurate than the number of misplaced tiles because it measures how far each tile is from its goal position.

易错点:空格不计入;距离按横竖步数计。

回查:L02 p.53–54。

A4 · Complexity

A search tree has branching factor b = 3. The shallowest goal is at depth m = 4, and the tree depth is d = 10.

(a) Using the bounds in the lecture, estimate the number of nodes BFS may generate. (b) Give the time and space bounds of DFS for this tree. (c) Explain in one sentence why DFS needs much less memory.

A4 · 查看答案与解析

推理过程:代入课件的界。BFS 时间与空间 O(bᵐ⁺¹):3 的 5 次方是 243。DFS 时间 O(bᵈ):3 的 10 次方是 59049;空间 O(d·b):10 乘 3 得 30。

答案:(a) 约 243 个节点;(b) 时间约 59049,空间约 30;(c) DFS 只需保存当前路径和路径上各节点未展开的兄弟。

English: BFS must keep the whole frontier of the shallowest levels, whereas DFS only stores the current path plus the unexpanded siblings along it.

易错点:m 与 d 不能混用;BFS 用的是最浅解深度 m,DFS 时间用的是树深 d。

回查:L02 p.15、p.24–26、p.36–38。

A5 · True or false with a reason

Answer True or False and give one reason for each.

(a) Hill climbing always finds the global maximum if it runs long enough. (b) A* may stop as soon as the goal node is generated and added to Open. (c) A heuristic that never overestimates the true remaining cost turns Algorithm A into A*. (d) BFS always returns the cheapest path when edge costs differ.

A5 · 查看答案与解析

答案:

(a) False。爬山法没有更好的邻居就停,可能停在局部最大、平台或山脊。

(b) False。目标被取出时才结束;生成时 Open 里可能还有 f 更小的节点(L02 p.65;T03a p.29)。

(c) True。h ≤ h* 时 Algorithm A 叫作 A*(L02 p.60)。

(d) False。BFS 找到的是边数最少的路径,边代价不等时不一定代价最小。

English: (a) It can get stuck at a local maximum, a plateau or a ridge. (b) The search ends only when the goal is selected for expansion. (c) If h(n) ≤ h*(n) for all n, the algorithm is A*. (d) BFS minimises the number of edges, not the total cost.

易错点:每题都要写理由,只写 True 或 False 不够。

回查:L02 p.24–26、p.48–50、p.60、p.65。

A6 · BFS and DFS on a directed graph

A directed graph has the edges S→A, S→B, A→C, A→D, B→D, C→A, C→E, D→G and E→G. The start is S and the goal is G. Children are added in alphabetical order, a node already in Open or Close is not added again, new nodes are appended to the end of Close, and the goal test is done when a node is removed from Open.

(a) Run BFS. Write Open and Close after each expansion, and give the path found. (b) Run DFS with a stack so that children are visited in alphabetical order. Give the order in which nodes are removed from Open and the path found. (c) What happens if DFS does not check Open and Close before adding a node?

A6 · 查看答案与解析

推理过程:BFS 用队列,DFS 用栈;想按字母序先访问 C 再访问 D,就要按降序入栈,C 最后入栈、最先出栈。

BFS 展开 Open Close
S A, B S
A B, C, D S, A
B C, D S, A, B
C D, E S, A, B, C
D E, G S, A, B, C, D
E G S, A, B, C, D, E
G 出队 空 判定到达目标

展开 B 时 D 已在 Open,不再加入;展开 C 时 A 已在 Close,也不加入。

答案:(a) 路径 S→A→D→G,3 条边。(b) DFS 出栈顺序 S, A, C, E, G,路径 S→A→C→E→G,4 条边,比 BFS 多一条。(c) 不查重时 C 的孩子 A 会再次入栈,出栈顺序变成 S, A, C, A, C, A……,在 A 和 C 之间无限循环。

English: BFS finds the path with the fewest edges, S→A→D→G. DFS follows A→C→E before backtracking and returns S→A→C→E→G. Without checking Open and Close, DFS loops forever on the cycle A→C→A.

易错点:G 在展开 D 时就进了 Open,但要等它出队才算找到;边有方向,D 不能回到 B。

回查:L02 p.18–19、p.22、p.31、p.36–38;T02 p.5–15。

A7 · Hill climbing on four queens

A state (r₀, r₁, r₂, r₃) gives the row of the queen in each column, rows 0 to 3. A neighbour is obtained by swapping the values of two columns. The cost is the number of attacking pairs, to be minimised. At each step, evaluate all six neighbours and move to the one with the lowest cost; if several neighbours tie, take the swap (i, j) with the smallest i, then the smallest j. Stop when no neighbour has a lower cost than the current state.

Start from (0, 1, 2, 3). Draw the search history: at every step list all neighbours with their costs, mark the chosen one, and give the final state.

A7 · 查看答案与解析

推理过程:交换两列的值,每一行仍只有一个皇后,冲突只来自对角线。每步写出六个邻居。

当前状态(成本) 六个邻居的成本 选中
(0, 1, 2, 3),6 (0,1)→(1, 0, 2, 3) 2;(0,2) 4;(0,3) 2;(1,2) 2;(1,3) 4;(2,3) 2 交换 (0,1),(1, 0, 2, 3)
(1, 0, 2, 3),2 (0,1) 6;(0,2)→(2, 0, 1, 3) 1;(0,3) 1;(1,2) 1;(1,3) 1;(2,3) 4 交换 (0,2),(2, 0, 1, 3)
(2, 0, 1, 3),1 (0,1) 2;(0,2) 2;(0,3) 4;(1,2) 4;(1,3) 2;(2,3)→(2, 0, 3, 1) 0 交换 (2,3),(2, 0, 3, 1)
(2, 0, 3, 1),0 六个邻居分别为 1、1、4、4、1、1 没有更低的,停

答案:成本 6 → 2 → 1 → 0,停在 (2, 0, 3, 1),这是四皇后的一个解。

English: Hill climbing evaluates all neighbours, moves to the best one and stops when no neighbour is better. Here the cost falls from 6 to 2, 1 and 0, and the search stops at the solution (2, 0, 3, 1).

易错点:前两步都有四个邻居同分,必须按题面的平局规则取;搜索历史要画出全部邻居,不能只写选中的路线。这次碰巧到了全局最优,换个初态可能停在局部最优。

回查:L02 p.47–50;T03a p.10–14。

A8 · A* with a reopened node

A directed graph has edges S→A 3, S→B 1, B→A 1, A→C 1 and C→G 3. Heuristic values: h(S) = 4, h(A) = 1, h(B) = 4, h(C) = 1, h(G) = 0. Break ties in f alphabetically.

(a) Is h admissible? Is it consistent? (b) Run A*, moving a node from Close back to Open when a cheaper path to it is found. Give the expansion order, the path and its cost.

A8 · 查看答案与解析

推理过程:h* 为 S 6、B 5、A 4、C 3、G 0,每个 h 都不超过 h*,可采纳。边 B→A 上 h(B) = 4 大于 1 + h(A) = 2,不一致。

展开 展开后的 Open(g, f) Close
S A(3, 4),B(1, 5) S
A B(1, 5),C(4, 5) S, A
B A(2, 3) 重开,C(4, 5) S, B
A C(3, 4) S, B, A
C G(6, 6) S, B, A, C
G 取出目标,结束

答案:(a) 可采纳,不一致。(b) 展开顺序 S, A, B, A, C, G;路径 S→B→A→C→G,代价 6。

English: The heuristic never overestimates, so it is admissible, but h(B) > c(B, A) + h(A), so it is not consistent. When B is expanded, a cheaper path to A is found (g falls from 3 to 2), so A is moved from Close back to Open and expanded again.

易错点:A 第一次展开时 g = 3 不是最优;如果 Close 里的节点不许重开,C 的 g 会停在 4,最后返回代价 7 的路径。

回查:L02 p.55、p.60–67;T03a p.31–35。

下一页 →
Q02 Midterm 自拟练习|B 概率

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。