COMP4133AADS►练习复习

COMP4133AADS 练习复习：Week 8 Dynamic Programming 1（Shortest Path DP + MDP/VI/PI + TSP）— 含答案

Week 8 练习题复习（Dynamic Programming 1）— 含答案与思路

覆盖两份课件：DP1_.pdf（Shortest Path DP） + DP2_.pdf（Modeling for DP：MDP / Bellman / VI / PI + TSP）
数学公式已按 KaTeX 语法：行内 $...$、独立公式 $$...$$。

Part A — Shortest Path Problem by Dynamic Programming（DP1_.pdf）

图与边权（课件示例网络）

有向图顶点 {0,1,2,3,4,5,6,7}\{0,1,2,3,4,5,6,7\}，终点为 7。边与成本如下：

  • 0→1:70\to 1:7, 0→2:60\to 2:6
  • 1→4:11\to 4:1, 1→3:21\to 3:2
  • 2→3:42\to 3:4, 2→5:72\to 5:7
  • 3→4:33\to 4:3, 3→6:13\to 6:1, 3→5:23\to 5:2
  • 5→6:15\to 6:1, 5→7:55\to 7:5
  • 6→7:86\to 7:8
  • 4→7:104\to 7:10

Exercise 1 — 写出 Successor / Predecessor 集合 Si,BiS_i, B_i

题目
对任意节点 ii，定义

  • Si={j∈N∣(i,j)∈A}S_i = \{ j \in \mathcal N \mid (i,j)\in \mathcal A \}（立即后继）
  • Bi={j∈N∣(j,i)∈A}B_i = \{ j \in \mathcal N \mid (j,i)\in \mathcal A \}（立即前驱）

(1) 写出 S3S_3 与 B3B_3
(2) 写出所有节点的 SiS_i

思路

  • 看“从 i 出去”的箭头就是 SiS_i
  • 看“指向 i”的箭头就是 BiB_i

答案
1)

  • S3={4,5,6}S_3 = \{4,5,6\}
  • B3={1,2}B_3 = \{1,2\}
  1. 全部 SiS_i：
  • S0={1,2}S_0=\{1,2\}
  • S1={3,4}S_1=\{3,4\}
  • S2={3,5}S_2=\{3,5\}
  • S3={4,5,6}S_3=\{4,5,6\}
  • S4={7}S_4=\{7\}
  • S5={6,7}S_5=\{6,7\}
  • S6={7}S_6=\{7\}
  • S7=∅S_7=\varnothing

Exercise 2 — Backward DP：计算所有 ViV_i 并给出最短路

题目
定义 ViV_i 为从节点 ii 到终点 7 的最短路径长度。写出递推并计算所有 ViV_i，最后给出从 0 到 7 的最短路径与长度。

思路（Backward DP 模板）

  • 终止条件：V7=0V_7 = 0
  • 递推式（Bellman 型）：

Vi=minj∈Si{cij+Vj},∀iV_i = \min_{j\in S_i}\{c_{ij}+V_j\},\quad \forall i

  • 本图是 DAG，可从终点往前逐层 label 计算

答案（逐步计算）

  • V7=0V_7=0
  • V4=10+V7=10V_4=10+V_7=10
  • V6=8+V7=8V_6=8+V_7=8
  • V5=min{1+V6,5+V7}=min{9,5}=5V_5=\min\{1+V_6,\;5+V_7\}=\min\{9,5\}=5
  • V3=min{3+V4,1+V6,2+V5}=min{13,9,7}=7V_3=\min\{3+V_4,\;1+V_6,\;2+V_5\}=\min\{13,9,7\}=7
  • V1=min{1+V4,2+V3}=min{11,9}=9V_1=\min\{1+V_4,\;2+V_3\}=\min\{11,9\}=9
  • V2=min{4+V3,7+V5}=min{11,12}=11V_2=\min\{4+V_3,\;7+V_5\}=\min\{11,12\}=11
  • V0=min{7+V1,6+V2}=min{16,17}=16V_0=\min\{7+V_1,\;6+V_2\}=\min\{16,17\}=16

最短距离

V0=16V_0 = 16

最短路径（回溯 argmin）
0→1→3→5→70\to 1\to 3\to 5\to 7（总成本 16）。

Exercise 3 — Forward DP：计算 FjF_j 并验证与 Backward 一致

题目
定义 FjF_j 为从起点 0 到节点 jj 的最短路径长度。写出递推并计算 F1..F7F_1..F_7。

思路（Forward DP 模板）

  • 初始条件：F0=0F_0=0
  • 递推式：

Fj=mini∈Bj{Fi+cij},∀jF_j = \min_{i\in B_j}\{F_i + c_{ij}\},\quad \forall j

  • 按拓扑序从小到大 label 计算

答案

  • F0=0F_0=0
  • F1=0+7=7F_1=0+7=7
  • F2=0+6=6F_2=0+6=6
  • F3=min{F1+2,F2+4}=min{9,10}=9F_3=\min\{F_1+2,\;F_2+4\}=\min\{9,10\}=9
  • F4=min{F1+1,F3+3}=min{8,12}=8F_4=\min\{F_1+1,\;F_3+3\}=\min\{8,12\}=8
  • F5=min{F2+7,F3+2}=min{13,11}=11F_5=\min\{F_2+7,\;F_3+2\}=\min\{13,11\}=11
  • F6=min{F3+1,F5+1}=min{10,12}=10F_6=\min\{F_3+1,\;F_5+1\}=\min\{10,12\}=10
  • F7=min{F4+10,F5+5,F6+8}=min{18,16,18}=16F_7=\min\{F_4+10,\;F_5+5,\;F_6+8\}=\min\{18,16,18\}=16

验证

F_7 = 16 \quad \text{与 Backward 的 } V_0=16 \text{一致}

Exercise 4 — 思考题：为什么“纯 Greedy”可能错？

题目
如果在每个节点都只走“当前最短边”（myopic greedy），是否一定得到最短路径？用本图举例说明。

答案（用本图构造反例）
贪心会倾向于：0→20\to2（6）→3\to3（4）→6\to6（1）→7\to7（8），总成本 6+4+1+8=196+4+1+8=19。
而最优是 0→1→3→5→70\to1\to3\to5\to7，成本 16。
所以 纯 Greedy 不保证最优；DP 的关键是把“未来的 cost-to-go”用 VjV_j 一起算进去。

Part B — Modeling for Dynamic Programming（DP2_.pdf）

Exercise 5 — MDP 基本元素辨认（Inventory 例子）

题目（课件例）
需求 d∈{0,1,2}d\in\{0,1,2\}，概率分别为 0.1,0.7,0.20.1,0.7,0.2；最大库存为 2。
(1) 写出状态空间 SS
(2) 写出动作集合 A(i)A(i)（每个状态可订货量）
(3) 解释“为什么用转移矩阵 Π(a)\Pi(a) 方便”

答案

  1. S={0,1,2}S=\{0,1,2\}（库存水平）
  • A(0)={0,1,2}A(0)=\{0,1,2\}
  • A(1)={0,1}A(1)=\{0,1\}
  • A(2)={0}A(2)=\{0\}
  1. 用矩阵 Π(a)\Pi(a)：把 “选动作 aa 后从各状态到各状态的概率” 统一写成一个矩阵，方便做线性代数推导（如 V=t+γΠVV=t+\gamma\Pi V）、也方便程序实现。

Exercise 6 — 读懂 Π(a)\Pi(a)：算一个转移概率（Inventory）

题目
假设当前库存为 0，订货动作 a=2a=2（订 2 件），需求随机 d∈{0,1,2}d\in\{0,1,2\}。
(1) 下一状态 s′s' 可能是什么？
(2) 分别给出 P(s′=2)P(s'=2)、P(s′=1)P(s'=1)、P(s′=0)P(s'=0)。

思路
订货后库存变为 2，再被需求消耗：s′=max(2−d,0)s' = \max(2-d,0)。

答案

  • 若 d=0d=0（0.1），s′=2s'=2
  • 若 d=1d=1（0.7），s′=1s'=1
  • 若 d=2d=2（0.2），s′=0s'=0
    因此：P(2)=0.1P(2)=0.1，P(1)=0.7P(1)=0.7，P(0)=0.2P(0)=0.2。

Exercise 7 — Bellman Equation 两种形式 + 互相转换

题目
解释两种即时项写法：

  1. 即时收益/成本只依赖 (i,a)(i,a)：f(i,a)f(i,a)
  2. 即时收益/成本依赖 (i,a,j)(i,a,j)：h(i,a,j)h(i,a,j)
    并写出它们的关系。

答案
形式 1（用 ff）：

V(i)=\operatorname{opt}_{a\in A(i)}\Big(f(i,a)+\gamma\sum_{j\in S}\pi(i,a,j)V(j)\Big)

形式 2（用 hh）：

V(i)=\operatorname{opt}_{a\in A(i)}\sum_{j\in S}\pi(i,a,j)\big(h(i,a,j)+\gamma V(j)\big)

关系（期望）：

f(i,a)=∑j∈Sπ(i,a,j)h(i,a,j)f(i,a)=\sum_{j\in S}\pi(i,a,j)\,h(i,a,j)

Exercise 8 — Bellman Operator：TT 与 TμT_\mu 是什么？（概念题）

题目
课件中把 Bellman 更新写成算子形式：V↦TVV\mapsto TV。
(1) 写出 [TV](i)[TV](i) 的定义
(2) 写出固定策略 μ\mu 下 [TμV](i)[T_\mu V](i) 的定义
(3) 用一句话说出：Value Iteration / Policy Iteration 分别在“迭代什么”。

答案

  1. 最优算子 TT：
[TV](i)=\operatorname{opt}_{a\in A(i)}\Big(f(i,a)+\gamma\sum_{j\in S}\pi(i,a,j)V(j)\Big)
  1. 固定策略算子 TμT_\mu：

[TμV](i)=f(i,μ(i))+γ∑j∈Sπ(i,μ(i),j)V(j)[T_\mu V](i)=f(i,\mu(i))+\gamma\sum_{j\in S}\pi(i,\mu(i),j)V(j)

  • Value Iteration：反复做 V(k+1)=TV(k)V^{(k+1)}=TV^{(k)}（逼近 V∗V^*）
  • Policy Iteration：反复做 Policy Evaluation（求 VμV_\mu）+ Policy Improvement（用 VμV_\mu 改进策略）

Exercise 9 — 1-state MDP：求 V∗V^* 与 VμV^\mu（课件例）

题目（课件 1-state 示例）

  • 状态：Home（1 个）
  • 动作：a1=Read,a2=Watch TVa_1=Read,\;a_2=Watch\ TV
  • 转移：必回到 Home（概率 1）
  • 即时奖励：h(i,a1,i)=2,h(i,a2,i)=3h(i,a_1,i)=2,\;h(i,a_2,i)=3
  • 折扣因子：γ=0.5\gamma=0.5
    (1) 求最优 V∗(i)V^*(i)
    (2) 若策略 μ\mu 总选 Read，求 Vμ(i)V^\mu(i)

答案
1)

V∗(i)=max{2+0.5V∗(i),3+0.5V∗(i)}=3+0.5V∗(i)V^*(i)=\max\{2+0.5V^*(i),\;3+0.5V^*(i)\}=3+0.5V^*(i)

V∗(i)=6V^*(i)=6

Vμ(i)=2+0.5Vμ(i)⇒Vμ(i)=4V^\mu(i)=2+0.5V^\mu(i)\Rightarrow V^\mu(i)=4

Exercise 10 — Value Iteration：从 V(0)=0V^{(0)}=0 开始做 3 轮（1-state）

题目
从 V(0)(i)=0V^{(0)}(i)=0 开始，算 V(1),V(2),V(3)V^{(1)},V^{(2)},V^{(3)}，看是否向 6 收敛。

答案
最优动作恒为 Watch TV：

V(k+1)(i)=3+0.5V(k)(i)V^{(k+1)}(i)=3+0.5V^{(k)}(i)

  • V(1)=3V^{(1)}=3
  • V(2)=4.5V^{(2)}=4.5
  • V(3)=5.25V^{(3)}=5.25
    收敛到 6（算子在 γ<1\gamma<1 时是 contraction）。

Exercise 11 — Policy Evaluation：线性系统 (I−γΠμ)Vμ=tμ(I-\gamma\Pi_\mu)V_\mu=t_\mu

题目
从固定策略 Bellman 方程推导线性系统，并用 1-state（总 Read）验证。

答案
固定策略：

Vμ(i)=f(i,μ(i))+γ∑j∈Sπ(i,μ(i),j)Vμ(j)V_\mu(i)=f(i,\mu(i))+\gamma\sum_{j\in S}\pi(i,\mu(i),j)V_\mu(j)

移项得：

(I−γΠμ)Vμ=tμ(I-\gamma\Pi_\mu)V_\mu=t_\mu

1-state：I=[1],Πμ=[1],tμ=[2]I=[1],\Pi_\mu=[1],t_\mu=[2]：

(1−0.5)Vμ=2⇒Vμ=4(1-0.5)V_\mu=2\Rightarrow V_\mu=4

Part C — TSP as an Episodic DP（DP2_.pdf）

Exercise 12 — TSP（3 城市）求最优 tour 与最小成本（课件 Question）

题目（课件给定成本矩阵）
从 A 出发，访问 A,B,C 各一次并回到 A。成本矩阵：

From \ To A B C
A 0 2 5
B 3 0 1
C 4 6 0

求最优 tour 与最小成本。

思路（3 城市可直接枚举，也可用 DP 状态）
从 A 出发只有两种不同 tour：

  • A→B→C→A
  • A→C→B→A

答案

  • A→B→C→A：2+1+4=72+1+4=7
  • A→C→B→A：5+6+3=145+6+3=14
    最优：A→B→C→A，最小成本 =7=7。

Exercise 13 — Bitmask：为什么 0b111=70b111=7？如何更新 mask？（课件题）

题目
(1) 解释 0b1110b111 为什么代表“三城都访问过”，它对应十进制多少？
(2) 城市编号 A=0,B=1,C=2，当前 mask 为 0b0010b001（只访问过 A），下一站去 B，新的 mask 是多少？
(3) 给出一般终止 mask 公式。

答案

  1. 0b111=1⋅22+1⋅21+1⋅20=70b111=1\cdot2^2+1\cdot2^1+1\cdot2^0=7。每一位为 1 表示对应城市已访问。
  2. 更新规则：newMask = mask | (1 << nextCity)

    0b001∣(1≪1)=0b001∣0b010=0b0110b001\;|\;(1\ll 1)=0b001\;|\;0b010=0b011

  3. 若共有 nn 个城市，则终止 mask：
\text{TERMINAL\_MASK}=(1\ll n)-1

Exercise 14 — 思考题：为什么 VI 里“没有显式的 π\pi（policy）”？

题目（课件 Why No Explicit π?）
Value Iteration 在更新时只算 VV，看起来没有直接输出策略 μ\mu。为什么？

答案
Value Iteration 先求 V∗V^*（值函数固定点），策略是 事后从 V∗V^* 用 greedy 得到：

μ∗(i)=argmina∈A(i)(f(i,a)+γ∑jπ(i,a,j)V∗(j))\mu^*(i)=\arg\min_{a\in A(i)}\Big(f(i,a)+\gamma\sum_j\pi(i,a,j)V^*(j)\Big)

也就是说：VI “隐式地”在靠近最优策略，但先把最优价值算准，再从价值反推出策略。

一页速记（考前 60 秒）

  • Backward DP（最短路）：

V7=0,Vi=minj∈Si(cij+Vj)V_7=0,\quad V_i=\min_{j\in S_i}(c_{ij}+V_j)

  • Forward DP（最短路）：

F0=0,Fj=mini∈Bj(Fi+cij)F_0=0,\quad F_j=\min_{i\in B_j}(F_i+c_{ij})

  • Bellman Optimality（MDP）：
V(i)=\operatorname{opt}_{a\in A(i)}\Big(f(i,a)+\gamma\sum_{j\in S}\pi(i,a,j)V(j)\Big)
  • Value Iteration：V(k+1)=TV(k)V^{(k+1)}=TV^{(k)}（γ<1\gamma<1 时收敛到 V∗V^*）
  • Policy Iteration：Policy Evaluation（解线性系统） + Policy Improvement（greedy 改进）
  • TSP 状态常写：(current,visitedMask)(current, visitedMask)，终止 mask：(1≪n)−1(1\ll n)-1