UC Berkeley CS 170 Fall 2023 作业 10（选做）

我们可以将每名秘密特工 \(i\) 视为一个单位的流，希望把它从 \(s_i\) 移动到任意顶点 \(\in T\)。为此，我们将原图建模为流网络：

1. 将每条边的容量设为 \(\infty\)。
2. 添加一个新的顶点 \(t\)（汇点），并对每个 \(t' \in T\) 添加一条边 \((t', t)\)。
3. 添加一个源点 \(s\)，并对每个 \(s_i\) 添加一条容量为 1 的边 \((s, s_i)\)。这样做将最大流限制为 \(k\)。
4. 为了保证每个城市最多有 \(c\) 名特工经过，我们需要对每个顶点施加容量 \(c\) 的约束。实现方式如下：对每个要添加约束的顶点 \(v\)，创建两个顶点 \(v_\text{in}\) 和 \(v_\text{out}\)。\(v_\text{in}\) 拥有 \(v\) 的所有入边，\(v_\text{out}\) 拥有 \(v\) 的所有出边。同时添加一条从 \(v_\text{in}\) 到 \(v_\text{out}\) 的有向边，边容量为 \(c\)。

如果最大流确实为 \(k\)，那么由于所有容量都是整数，计算最大流的 Ford-Fulkerson 算法将输出一个整数流（所有流量值均为整数的流）。因此，我们可以从每名秘密特工 \(i\) 出发，沿着流中从 \(s_i\) 到 \(T\) 中任意顶点的路径追踪。遍历所有特工即可得到一个解。

解法一：使用 \(D + 2\) 个顶点。

算法描述：为每天 \(d = 1 \dots D\) 创建一个顶点。同时创建一个起点 \(s\) 和一个终点 \(t\)，为方便起见分别将其索引设为 \(0\) 和 \(D + 1\)。

然后，对 \(u, v \in \{0, \dots, D\}\)，如果存在某个教练从第 \(v+1\) 天到第 \(u\) 天可用，则创建一条边 \(u \to v\)，并将其权重（容量）设为具有该可用范围的教练数量。注意我们为了计算目的将顶点 \(s\) 视为索引 \(0\)。此外，添加一条从顶点 \(D\) 到终点 \(t\) 的边，权重为 \(k\)。

检查是否存在有效调度的方法是检查从 \(s\) 到 \(t\) 的最大流是否等于 \(k\)。

解法二：使用 \(n + 2\) 个顶点。

算法描述：为每名教练 \(i = 1 \dots n\) 创建一个顶点，加上 \(s\) 和 \(t\)。然后，如果 \(a_j = b_i + 1\)，则用单位容量边连接顶点 \(i\) 和 \(j\)。将所有满足 \(a_i = 0\) 的顶点连接到 \(s\)，将所有满足 \(b_i = D\) 的顶点连接到 \(t\)。

正确性类似于 \(D+2\) 解：从 \(s\) 到 \(t\) 的路径对应于覆盖所有 \(D\) 天的教练序列。

注意：\(n+2\) 解优于 \(D+2\) 解，因为 \(D\) 只是作为参数给出（而我们给出的是 \(n\) 名教练的列表），所以 \(D+2\) 顶点解实际上是伪多项式时间。

(a) 收益矩阵如下（你是行玩家）：

(b) 设 \(r, p, s\) 分别是你出 rock、paper、scissors 的概率。设 \(z\) 表示在对手也最优出牌时的期望收益。

\[ \begin{aligned} \max \quad & z \\ \text{s.t.} \quad & 2p - s \geq z && \text{(对手选择 rock)} \\ & 4s - 2r \geq z && \text{(对手选择 paper)} \\ & r - 4p \geq z && \text{(对手选择 scissors)} \\ & r + p + s = 1 \\ & r, p, s \geq 0 \end{aligned} \]

(c) 为你自己（最大化者）建立的 LP：

\[ \begin{aligned} \max \quad & z \\ \text{s.t.} \quad & -10r + 4p + 6s \geq z && \text{(对手选择 rock)} \\ & 3r - p - 9s \geq z && \text{(对手选择 paper)} \\ & 3r - 3p + 2s \geq z && \text{(对手选择 scissors)} \\ & r + p + s = 1 \\ & r, p, s \geq 0 \end{aligned} \]

最优策略为 \(r = 0.3346\)，\(p = 0.5630\)，\(s = 0.1024\)，最优收益为 \(-0.48\)。

(d) 为你的朋友（最小化者）建立的 LP：

\[ \begin{aligned} \min \quad & z \\ \text{s.t.} \quad & -10r + 3p + 3s \leq z && \text{(你选择 rock)} \\ & 4r - p - 3s \leq z && \text{(你选择 paper)} \\ & 6r - 9p + 2s \leq z && \text{(你选择 scissors)} \\ & r + p + s = 1 \\ & r, p, s \geq 0 \end{aligned} \]

你朋友的最优策略为 \(r = 0.2677\)，\(p = 0.3228\)，\(s = 0.4094\)。该博弈值为 \(-0.48\)，即你的收益。你朋友的收益为你的收益的相反数，即 \(0.48\)，因为博弈是零和的。

（评分说明：等价的 LP 均可接受。(d) 部分最大化你朋友的收益而非最小化你的收益也可以。策略可以用分数或接近解的小数表示，只要 LP 正确即可。）

(a) 概率为 \(0\)。无论列玩家选择哪个选项，行玩家选择 E 总是比选择 D 获得更高的收益，因此任何涉及以非零概率选择 D 的策略都可以通过改为选择 E 来改进。

(b) 概率为 \(0\)。我们知道行玩家绝不会选择 D，即总是选择 E 或 F。但在这种情况下，列玩家选择 B 总是比选择 A 更好（只有当行玩家选择 D 时 A 才更好）。也就是说，在行玩家最优行事的前提下，B 支配 A。

(c) 基于前两部分，我们只需考虑行玩家选择 E 或 F、列玩家选择 B 或 C 的概率。查看对应这些选项的 \(2 \times 2\) 子矩阵，可以得出行玩家的最优策略是以 \(1/2\) 的概率选择 E 和 F，同理列玩家应以 \(1/2\) 的概率选择 B 和 C。

(a) 给定图 \(G\) 和预算 \(b\)，我们首先对实例 \((G, b)\) 运行决策算法。如果它返回 "FALSE"，则报告 "无解"。

如果返回 "TRUE"，则存在解，我们按如下方式找到它：

• 任选一个节点 \(v \in G\) 并将其删除，同时删除任何关联的边。

• 对实例 \((G \setminus \{v\}, b-1)\) 运行决策；如果它说 "TRUE"，则将 \(v\) 加入顶点覆盖。否则，将 \(v\) 及其边放回 \(G\)。

• 重复直到 \(G\) 为空。

正确性：如果没有解，我们显然报告无解。如果有解，则我们的算法测试各个节点，看它们是否属于某个大小为 \(b\) 的顶点覆盖（可能有多个）。当且仅当 \(v\) 属于某个这样的覆盖时，子图 \(G \setminus \{v\}\) 必须有一个大小不超过 \(b-1\) 的顶点覆盖。归纳地应用此论证。

运行时间：在找到一个属于 \(b\) 顶点覆盖的 \(v\) 并递归之前，我们可能测试每个顶点一次。因此我们调用决策过程 \(O(n^2)\) 次。这可以通过不重复考虑任何顶点来收紧到 \(O(n)\)。由于一次调用决策花费多项式时间，我们整体具有多项式复杂度。

注意：这种归约可以看作是一种贪心算法，在其中我们一次发现（或消除）一个顶点。

(b) 对顶点覆盖的大小 \(b\) 进行二分搜索。

正确性：该算法正确的原因与二分搜索相同。

运行时间：最小顶点覆盖的大小对于非空图至少为 \(1\)，至多为 \(|V|\)，因此搜索黑盒将被调用 \(O(\log |V|)\) 次，整体给出多项式复杂度。

最后，由于解决优化问题允许我们回答决策问题（想想为什么），我们看到所有三个问题都可以相互归约！

算法描述：设 \(G = (V, E)\) 为最小顶点覆盖（MVC）问题的一个实例。创建最小集合覆盖（MSC）问题的一个实例，其中 \(U = E\)，且对每个 \(u \in V\)，集合 \(S_u\) 包含所有与 \(u\) 关联的边。

设 \(C_S = \{S_{u_1}, S_{u_2}, \dots, S_{u_k}\}\) 是一个集合覆盖，其中 \(k = |C_S|\)。则我们对应的顶点覆盖为 \(C_V = \{u_1, u_2, \dots, u_k\}\)。

正确性：为了看出 \(C_V\) 是一个顶点覆盖，任取 \((u, v) \in E\)。由于 \((u, v) \in U\)，存在某个集合 \(S_{u_i}\) 包含 \((u, v)\)，所以 \(u_i\) 等于 \(u\) 或 \(v\)，且 \((u, v)\) 在顶点覆盖中被覆盖。因此，\(G\) 中的每个顶点覆盖都对应 \(U, S\) 中的一个集合覆盖。

现在任取一个顶点覆盖 \(u_1, \dots, u_k\)。为了看出 \(S_{u_1}, \dots, S_{u_k}\) 是一个集合覆盖，任取 \((u, v) \in E\)。根据顶点覆盖的定义，存在某个 \(i\) 使得 \(u = u_i\) 或 \(v = u_i\)。所以 \((u, v) \in S_{u_i}\)，因此 \(S_{u_1}, \dots, S_{u_k}\) 是一个集合覆盖。因此，\(U, S\) 中的每个集合覆盖都对应 \(G\) 中的一个顶点覆盖。

由于每个顶点覆盖都有对应的集合覆盖（反之亦然），且最小化集合覆盖就最小化了对应的顶点覆盖，该归约成立。

(a) 将最小费用流写成线性规划。一种形式化如下：

\[ \begin{aligned} \min \quad & \sum_e \ell_e f_e \\ \text{s.t.} \quad & 0 \leq f_e \leq c_e && \forall e \in E \\ & \sum_{e \text{ 进入 } v} f_e = \sum_{e \text{ 离开 } v} f_e && \forall v \in V, v \neq s, t \\ & F + \sum_{e \text{ 进入 } s} f_e = \sum_{e \text{ 离开 } s} f_e \end{aligned} \]

(b) 算法描述：考虑图 \(G\) 上的一个最短路实例，起点为 \(s\)，终点为 \(t\)，边权为 \(\ell_e\)。令 \(F = 1\) 且对所有边 \(e\) 令 \(c_e = 1\)。在最小费用流 \(f\) 中——由 \(G\) 中流量非零的边组成的子图 \(H\)——从 \(s\) 到 \(t\) 的所有有向路径的长度都等于从 \(s\) 到 \(t\) 的最短路的长度。因此，要在 \(H\) 中找到从 \(s\) 到 \(t\) 的最短路，只需使用 DFS 或 BFS 找到 \(H\) 中 \(s\) 到 \(t\) 的任意一条路径即可。

正确性证明（非必需）：假设每个 \(\ell_e > 0\)（我们可以收缩任何 \(\ell_e = 0\) 的边）。首先，我们证明 \(H\) 是一个 DAG。如果 \(H\) 不是 DAG，则它必须包含一个环。设 \(\delta > 0\) 为该环上任意边上的最小流量。从该环上所有边的流量中减去 \(\delta\)，结果得到一个仍然从 \(s\) 到 \(t\) 输送 1 单位流的流。然而，这个流的成本比之前更小，与 \(f\) 是最小费用流矛盾。因此，\(H\) 是一个 DAG。

考虑 \(H\) 中 \(s\) 到 \(t\) 的任意路径 \(P\)。设 \(\delta\) 为该路径上任意边上的最小流量。可以将流 \(f\) 写成包括 \(P\) 在内的路径的线性组合：

\[f = \delta p + \delta_1 q_1 + \dots + \delta_k q_k\]

其中 \(p\) 和 \(q_i\) 分别是沿路径 \(P\) 和 \(Q_i\) 的单位流，\(\delta_i\) 是从 \(P, Q_1, \dots, Q_{i-1}\) 中减去流量后某条任意路径 \(Q_i\) 上的最小流量。

由于减去 \(\delta_i\) 单位的流使从 \(s\) 到 \(t\) 的流减少了 \(\delta_i\) 单位，所以 \(\delta + \sum_i \delta_i = 1\)。

由于最小费用流的目标函数是线性的，我们可以写出：

\[ \sum_e \ell_e f_e = \delta \sum_e \ell_e p_e + \sum_i \delta_i \sum_e \ell_e q_{i,e} = \delta \sum_{e \in P} \ell_e + \sum_i \delta_i \sum_{e \in Q_i} \ell_e \]

特别地，流 \(f\) 的成本是根据权重 \(\delta, \delta_1, \dots, \delta_k\) 的路径 \(P, Q_1, \dots, Q_k\) 的平均长度。因此，如果 \(P\) 或某个 \(Q_i\) 不是从 \(s\) 到 \(t\) 的最短路，可以通过将该路径上的流重新分配到 \(s\) 到 \(t\) 的某条最短路来降低 \(f\) 的成本。这意味着如果 \(f\) 具有最小成本，\(P\) 和所有 \(Q_i\) 都必须是 \(s\) 到 \(t\) 的最短路。由于 \(P\) 被选为 \(H\) 中从 \(s\) 到 \(t\) 的任意路径，\(H\) 中的所有路径都必须是 \(s\) 到 \(t\) 的最短路。

(c) 我们可以使用二分搜索来找到真正的最大流值。考虑图 \(G\) 上的一个最大流实例，容量为 \(c_e\)，我们希望从 \(s\) 到 \(t\) 输送流。按如下方式创建最小费用流实例。将容量设为等于 \(c_e\)，并让长度任意（例如对所有边 \(\ell_e = 1\)）。我们知道最大流值 \(F_{\max} \leq \sum_e c_e\)。

如果容量是整数，\(F_{\max}\) 也是整数。因此，我们可以二分搜索来找到它的真实值。对于任意 \(F\)，我们可以通过以至少 \(F\) 的值查询最小费用流实例来了解是否存在输送超过 \(F\) 单位流的流。如果存在值至少为 \(F\) 的流，它将返回一个有限成本的流。否则，程序不可行。