知识焦点
先建立概念地图
- shortest paths
- BFS
- Dijkstra
- Bellman-Ford
- arbitrage
- greedy algorithm
- Huffman coding
- maximum spanning tree
CS170 · 作业 5
UC Berkeley CS 170 2023 年秋季学期选做作业 5，共 8 道题：学习小组、统计最短路径数、美国最伟大的公路、套利、乘积之和（任务分配）、被操控的锦标赛、二十问（Huffman 编码）、避免冲突（最大割近似）。涉及 BFS、Dijkstra、Bellman-Ford、贪心、Huffman 编码、最大生成树等算法。
知识焦点
建议顺序
先完整作答，再按需展开提示；最后才展开官方参考解答并逐步核对证明与计算。
本地来源
题面与解答均由本地一手资料整理：hw05.pdf、hw05-sol.pdf
本地一手资料完整提取 · 作业
本节按本地一手资料完整整理，共 8 道大题。本地官方解答已收录 7/8 道并默认折叠；其余题目会明确标注无本地官方解答。
hw05.pdf、hw05-sol.pdf列出学习小组成员的姓名与 SID。若无合作者，必须明确写出 "none"。
本题为课程行政要求，如实填写合作者姓名与 SID；若无则写 "none"。
本地资料未提供这道题的官方解答；页面只保留题面与非答案式提示。
题面来源：hw05.pdf · 1 · confidence: high
给定一个无向无权图 \(G\) 和一个顶点 \(s\)，设 \(p(v)\) 为从 \(s\) 到 \(v\) 的最短路径（shortest paths）的数量。本题中我们约定 \(p(s) = 1\)。给出一个运行时间为 \(O(|V| + |E|)\) 的算法，计算所有顶点 \(v\) 的 \(p(v) \bmod 1337\)。只需给出主要思想和运行时间分析。
注意：作为附加问题，请思考：若我们计算的是 \(p(v)\) 而非 \(p(v) \bmod 1337\)，运行时间是否保持不变。
按 BFS 的层次顺序处理顶点：当处理顶点 \(v\) 时，所有可能作为最短路径前驱的邻居 \(u\) 都已被处理。尝试用这些 \(u\) 的 \(p(u)\) 之和来表示 \(p(v)\)。
自检：若 \(v\) 的距离为 \(d\)，哪些邻居 \(u\) 可能贡献到 \(p(v)\)？距离为 \(d\) 或 \(d+1\) 的邻居能否被排除？
主要思想：若顶点 \(v\) 与 \(s\) 的距离为 \(d > 0\)，则任意一条到 \(v\) 的最短路径的前 \(d-1\) 条边构成一条到 \(v\) 的某个邻居的最短路径，且该邻居与 \(s\) 的距离为 \(d-1\)。进一步，从到 \(v\) 的最短路径到其距离为 \(d-1\) 的邻居的最短路径之间的映射是一个双射。因此，令 \(N(v)\) 表示 \(v\) 的所有与 \(s\) 距离为 \(d-1\) 的邻居组成的集合，我们有 \(p(v) = \sum_{u \in N(v)} p(u)\)。
算法如下：首先用 BFS 计算 \(s\) 到所有顶点的距离。然后令 \(p(s)=1\)，再按距离递增的顺序处理其余顶点，对每个顶点 \(v\) 计算 \(p(v) \bmod 1337 = \sum_{u \in N(v)} p(u) \bmod 1337\)。由于按距离递增顺序处理顶点，\(N(v)\) 中的每个 \(u\) 对应的 \(p(u)\) 都已被计算。
复杂度分析：BFS 耗时 \(O(|V| + |E|)\)。从邻居计算 \(p(v) \bmod 1337\) 耗时 \(O(\deg(v))\)，因此计算所有 \(p(v) \bmod 1337\) 的总时间为 \(O(|E|)\)。
若没有 \(\bmod 1337\) 而要求精确的 \(p(v)\)，则运行时间会更高，因为到 \(v\) 的长度为 \(d\) 的路径数可能关于 \(d\) 指数增长，对这些数的算术运算不再是常数时间。
解答来源：hw05-sol.pdf · 1 · confidence: high
题面来源：hw05.pdf · 1 · confidence: high
可以说，在美国最棒的事情之一就是来一场经典的美式公路旅行。美国有许多令人惊叹的公路（想想 Pacific Coast Highway、Route 66 等）。一位勇敢的旅行者决定穿越美国，寻找精彩的驾驶体验。求一条至少经过 \(k\) 条这种精彩公路的最短路径的长度。
假设美国的公路可以表示为一个有向加权图 \(G = (V, E, d)\)，旅行者希望从"精彩"公路的子集 \(R \subseteq E\) 中至少行驶 \(k\) 条公路。此外，假设旅行者从家 \(a \in V\) 出发并最终回到 \(a\)。你还可以假设旅行者不介意重复经过 \(R\) 中的公路，即从 \(R\) 中选出的 \(k\) 条公路不必互不相同。
设计一个高效的算法来解决这个问题。给出包含三部分（three-part solution）的解答，运行时间用 \(n = |V|\)、\(m = |E|\)、\(k\) 表示。
尝试用"层"来记录已经经过了多少条 \(R\) 中的公路：每经过一条 \(R\) 中的边就上升一层；到达第 \(k\) 层意味着已使用至少 \(k\) 条 \(R\) 中的公路。
自检：构造出的图 \(G'\) 有多少个顶点？从 \(a\) 在第 0 层的副本到 \(a\) 在第 \(k\) 层的副本的最短路径，是否一定对应 \(G\) 中一条合法路径？
主要思想：我们希望构造一个新图 \(G'\)，使得可以在 \(G'\) 上运行 Dijkstra 算法来求解。
首先创建 \(k+1\) 个 \(G\) 的副本，记为 \(G_0, G_1, \ldots, G_k\)。这些副本包含 \(G\) 的所有边、顶点以及相同的边权。用 \(v_i\) 表示顶点 \(v\) 在 \(G_i\) 中的副本。对每条道路 \((u, v) \in R\)，我们额外添加边 \((u_0, v_1), (u_1, v_2), \ldots, (u_{k-1}, v_k)\)，其权重与 \((u, v)\) 相同。创建这些副本的直觉是：每当在 \(G'\) 中使用一条对应于 \(R\) 中边的边时，我们就前进到 \(G\) 的下一个副本，而这是前进到下一个副本的唯一方式。因此，若已从 \(a_0\) 到达 \(v_i\)，则可确定到目前为止已使用了至少 \(i\) 条 \(R\) 中的边。
现在考虑 \(G'\) 中任意一条从 \(a_0\) 到 \(a_k\) 的路径 \(p'\)。若将其中每条 \((u_i, v_i)\) 或 \((u_i, v_{i+1})\) 替换为 \(G\) 中对应的边 \((u, v)\)，则得到 \(G\) 中一条从 \(a\) 回到自身的路径 \(p\)。进一步，由于该路径从 \(a_0\) 到达 \(a_k\)，它包含 \(k\) 条形如 \((u_i, v_{i+1})\) 的边，其中 \((u, v)\) 是 \(R\) 中的边。因此 \(p\) 至少包含 \(k\) 条 \(R\) 中的边。
算法即为：按上述方式构造 \(G'\)，用 Dijkstra 算法求出从 \(a_0\) 到 \(a_k\) 的最短路径 \(p'\)，然后输出 \(G\) 中对应的路径 \(p\)。
正确性：假设 \(G\) 中存在一条比该算法产生的路径更短的合法路径 \(p\)。考虑在 \(G'\) 中通过修改 \(p\)、使其在每次经过 \(R\) 中的边时前进到下一个副本所形成的等价路径 \(p'\)。由于 \(p\) 合法，\(p'\) 必须从 \(G_0\) 中的 \(a\) 到达 \(G_k\) 中的 \(a\)。但这意味着 \(p'\) 是 \(G'\) 中一条比 Dijkstra 算法求得的路径更短的路径，矛盾。
复杂度：由于 \(G'\) 包含 \(k+1\) 个 \(G\) 的副本，Dijkstra 算法的运行时间为 \(O((km + kn) \log(kn))\)。
解答来源：hw05-sol.pdf · 1-2 · confidence: high
题面来源：hw05.pdf · 1-2 · confidence: high
最短路径算法也可以应用于货币交易。假设有 \(n\) 种货币 \(C = \{c_1, c_2, \ldots, c_n\}\)，例如美元、欧元、比特币、狗狗币等。对于任意两种货币 \(c_i, c_j\)，存在一个汇率 \(r_{i,j}\)：你可以以 1 单位货币 \(c_i\) 的价格购买 \(r_{i,j}\) 单位货币 \(c_j\)。假设 \(r_{i,i} = 1\) 且对所有 \(i, j\) 有 \(r_{i,j} \geq 0\)。
外汇市场组织（FEMO）聘请了 CS170 校友 Oski，来确保不可能通过一系列兑换产生利润；即对于任意货币 \(i \in C\)，不可能从 1 单位货币 \(i\) 开始，经过一系列兑换，最终得到超过 1 单位货币 \(i\)。（这就是套利（arbitrage）。）
更精确地说，当存在一系列货币 \(c_{i_1}, \ldots, c_{i_k}\) 使得 \(r_{i_1,i_2} \cdot r_{i_2,i_3} \cdots r_{i_{k-1},i_k} \cdot r_{i_k,i_1} > 1\) 时，就可能发生套利。这意味着从 1 单位货币 \(c_{i_1}\) 开始，依次兑换为 \(c_{i_2}, c_{i_3}, \ldots, c_{i_k}\)，最后换回 \(c_{i_1}\)，最终会得到超过 1 单位的 \(c_{i_1}\)。这种异常在外汇市场上只持续不到一分钟，但它们提供了获利的机会。
我们说一组汇率是无套利的（arbitrage-free），当不存在这样的序列，即不可能通过一系列兑换获利。
(a) 对以下问题给出一个高效的算法：给定一组无套利的汇率 \((r_{i,j})_{i,j \in n}\)，以及两种特定货币 \(a, b\)，找出将货币 \(a\) 兑换为货币 \(b\) 的最有利可图的兑换序列。即，如果你有固定数量的货币 \(a\)，输出一个能兑换到最多货币 \(b\) 的兑换序列。
(b) Oski 厌倦了手动检查汇率，请你帮他写一个程序来完成他的工作。给出一个高效算法来检测套利的可能性。你可以使用与 (a) 相同的图表示。
对于 (a) 和 (b) 两部分，都给出包含三部分的解答。
将汇率取负对数后，乘积最大化问题会变成什么样？取负对数后，最大化乘积就变成了最小化某个和。
对于 (b)：在最短路径问题中，什么结构的存在意味着可以无限降低总权重？如何用标准算法检测它？
(a) 主要思想：将货币表示为完全有向图 \(G\) 的顶点集 \(V\)，将汇率表示为图中的边 \(E\)。求 \(a\) 到 \(b\) 的最优汇率等价于求汇率乘积最大的路径。为将其转化为最短路径问题，将边权设为汇率的负对数，即令 \(w_{ij} = -\log r_{ij}\)。由于边权可能为负，我们使用 Bellman-Ford 算法来求最短路径。
正确性证明：要将 \(c_a\) 最有利地兑换为 \(c_b\)，需要找到一条路径 \(c_{i_1}, c_{i_2}, \ldots, c_{i_k}\) 使得乘积 \(r_{i_1,i_2} \cdot r_{i_2,i_3} \cdots r_{i_{k-1},i_k}\) 最大。这等价于最小化 \(\sum_{j=1}^{k-1} (-\log r_{ij,i_{j+1}})\)。因此，只需在权值为 \(w_{ij} = -\log r_{ij}\) 的图 \(G\) 中求最短路径即可。整个算法的正确性由 Bellman-Ford 的正确性保证。
复杂度：与 Bellman-Ford 相同，由于图是完全图，为 \(O(|V|^3)\)。
(b) 主要思想：在 \(|V|\) 轮之后再额外迭代一次更新过程。若任意距离被更新，则必然存在负权环，即存在环使得 \(\sum_{j=1}^{k-1} (-\log r_{ij,i_{j+1}}) < 0\)，这意味着 \(\prod_{j=1}^{k-1} r_{ij,i_{j+1}} > 1\)，符合要求。
正确性证明：与修改 Bellman-Ford 以寻找负权边的证明相同。
复杂度：与 Bellman-Ford 相同，\(O(|V|^3)\)。
注：两道题也可以用 Bellman-Ford 的变体来求解，该变体针对乘法和最大化而非加法和最小化。
解答来源：hw05-sol.pdf · 2-3 · confidence: high
题面来源：hw05.pdf · 2-3 · confidence: high
这个问题引导你为一个贪心算法（greedy algorithm）写出正确性证明。你有 \(n\) 个计算任务需要完成，任务 \(i\) 需要 \(t_i\) 单位 CPU 时间才能完成。你还可以使用 \(n\) 台机器来分配这些任务。由于机器需求很高，每台机器只能分配一个任务。第 \(j\) 台机器每单位 CPU 时间花费 \(c_j\) 美元，因此将任务 \(i\) 分配给机器 \(j\) 将花费 \(t_i \cdot c_j\) 美元（每台机器完成同一任务所需 CPU 时间相同）。你的目标是找到一种将任务分配给机器的方案，使得总成本最小。
假设任务和机器已按互不相同的运行时间/成本排序，即 \(t_1 > t_2 > \ldots > t_n\) 且 \(c_1 > c_2 > \ldots > c_n\)。
(a) 描述使总成本最小的任务分配方案（无需证明）。
(b) 给定一个任务分配方案，考虑如下修改：如果存在一对任务 \(i, j\)，使得任务 \(i\) 被分配给机器 \(i'\)，任务 \(j\) 被分配给机器 \(j'\)，且 \(t_i > t_j\) 以及 \(c_{i'} > c_{j'}\)，则将任务 \(i\) 改分配给机器 \(j'\)，任务 \(j\) 改分配给机器 \(i'\)。 证明该修改会降低分配方案的总成本。
(c) 利用 (b) 证明你在 (a) 中选择的方案具有最小总成本（提示：证明对于除你在 (a) 中选择的方案之外的任意其他分配，都可以应用 (b) 中的修改。由此得出 (a) 中的方案是最优的。）
在 (a) 中，先尝试将最长的任务分配给最便宜的机器，观察是否能得到最小成本。在 (b) 中，计算交换前后成本的差式并因式分解。
自检：在 (c) 中，若一个分配无法再应用 (b) 中的修改，则每个任务与机器之间必须满足什么顺序关系？
(a) 将最长的任务（任务 1）分配给最便宜的机器（机器 \(n\)），第二长的任务（任务 2）分配给第二便宜的机器（机器 \(n-1\)），依此类推。
(b) 除任务 \(i\) 和 \(j\) 外，其他任务的计算成本不受影响。任务 \(i\) 和 \(j\) 的旧成本为 \(t_i c_{i'} + t_j c_{j'}\)，新成本为 \(t_i c_{j'} + t_j c_{i'}\)。成本减少量为 \(t_i c_{i'} + t_j c_{j'} - t_i c_{j'} - t_j c_{i'} = (t_i - t_j)(c_{i'} - c_{j'})\)，由于 \(t_i > t_j\) 且 \(c_{i'} > c_{j'}\)，该值为正。
(c) 假设某个任务分配方案无法再应用 (b) 中的修改。则任务 1 必须被分配给机器 \(n\)——否则任务 1 与被分配给机器 \(n\) 的某个任务满足 (b) 的条件。在已知任务 1 分配给机器 \(n\) 后，同理可推出任务 2 必须分配给机器 \(n-1\)，依此类推。因此该分配方案恰好就是 (a) 中选择的方案。
于是，对于除 (a) 中方案之外的每一个其他分配，都存在另一个总成本更低的分配，即前者不是最优的。这说明 (a) 中的方案是最优分配。
解答来源：hw05-sol.pdf · 3 · confidence: high
题面来源：hw05.pdf · 2-3 · confidence: high
Peter 负责组织一个有 \(n\) 支球队的足球锦标赛。锦标赛是单淘汰制（single-elimination）：若球队 \(i\) 和 \(j\) 比赛，输的一方出局且不能再比赛。没有平局。
Peter 不太靠谱的朋友 Jeff 给了他以下内部信息：若球队 \(i\) 和 \(j\) 比赛，则他们将在这场比赛中共得到 \(f(i,j) \geq 0\) 分，并且 Jeff 可以操纵比赛使他选择的球队获胜。Peter 希望找到一个锦标赛赛程，使得 (1) 锦标赛中得分总和最大，并且 (2) 他最喜欢的球队 \(i^*\) 赢得锦标赛。给出一个高效算法解决此问题并提供其运行时间；无需正确性证明。
注：球队在锦标赛中不需要比赛相同场次的比赛。例如，若球队为 \(\{1, 2, 3, 4\}\)，则一个有效的锦标赛赛程（其中 \((i, j)\) 表示 \(i\) 与 \(j\) 比赛且 \(i\) 获胜）为 \([(1, 2), (1, 3), (4, 1)]\)。这里球队 4 赢得锦标赛。
每场比赛淘汰一支球队，最终只剩一支冠军。整个锦标赛的得分总和与所选的"比赛集合"（边的集合）有什么关系？为了使 \(i^*\) 夺冠，在构造赛程时需要保证什么？
自检：赛程对应的树中，\(i^*\) 应处于什么位置？
令 \(G = (V, E)\) 为 \(n\) 个顶点上的完全图，边权 \(\ell(i,j) = f(i,j)\)。关键观察是：一个锦标赛赛程对应图中的一棵树，且该树的权重等于该赛程下锦标赛所有比赛的总得分。因此，令 \(T\) 为 \(G\) 的最大生成树（Maximum Spanning Tree）。\(T\) 的权重即为锦标赛中可能的最大总得分。为提取比赛序列，只需从 \(i^*\) 出发运行 DFS 或 BFS，并按深度从大到小进行比赛，使深度较小的球队总是获胜。
对于运行时间，DFS/BFS 耗时 \(O(n)\)，因此 MST 算法是瓶颈。由于共有 \(O(n^2)\) 条边（完全图），耗时 \(O(|E| \log |V|) = O(n^2 \log n)\)。
解答来源：hw05-sol.pdf · 4 · confidence: high
题面来源：hw05.pdf · 4 · confidence: high
你的朋友向你挑战猜词游戏"二十问"的一个变体。首先，他们按照已知的概率分布 \((p_1, p_2, \ldots, p_n)\) 选择一个词 \((w_1, w_2, \ldots, w_n)\)，即词 \(w_i\) 被选中的概率为 \(p_i\)。然后，你提出是/否问题，直到你确定选中的是哪个词。你可以提出任何是/否问题，即你可以用"这个词在 \(S\) 中吗？"这样的问题来排除任意一个可能词的子集 \(S\)。
定义一个猜测策略的代价为确定所选词所需的期望查询次数，令最优策略为代价最小的策略。设计一个 \(O(n \log n)\) 的算法来确定最优策略的代价。
给出包含三部分的解答。
注：本题只考虑确定性（deterministic）猜测策略。包含随机化策略不会改变答案，但会使正确性证明更困难。
每次是/否回答将候选词集一分为二。这与哪种经典数据编码问题类似？该问题的最优解法是什么？
自检：最优策略的代价与最优编码的什么量相等？为何前缀无关性成立？
此解法受到以下观察的启发：在二进制编码中，每读取一位码字都会进一步缩小被编码符号的可能范围，正如游戏中每个问题的作用。这种对应关系在正确性证明中得以严格化。
主要思想：在 \((w_1 \cdots w_n)\) 上、以 \((p_1 \cdots p_n)\) 为权重构建一棵 Huffman 树（Huffman tree），并返回对应编码下码字的期望长度。
正确性证明：注意，任何猜测策略都给出词 \((w_1 \cdots w_n)\) 的一个前缀无关（prefix-free）二进制编码，其中每个词 \(w_i\) 由一系列是/否回答序列编码，这些回答会让你得出 \(w_i\) 被选中的结论。该编码是前缀无关的，因为游戏仅在除一个词外所有词都被排除时才结束。
此外，任何前缀无关编码都可以如下转化为猜测策略。设 \(x_n \in \{0, 1\}^n\) 表示前 \(n\) 个问题收到的回答序列，其中 1 对应"是"，0 对应"否"。那么在第 \(n+1\) 步询问"该词是否可被编码为以 \(x_n \circ 1\) 为前缀的字符串（即当前回答后接一个'是'）"，将使得最终的回答序列构成所选词的一个合法编码。
在此对应下，期望码长等于猜测策略的代价。因此，寻找最优策略等价于寻找期望码长最小的前缀无关编码，而这正是 Huffman 编码（Huffman coding）所做的。为得到最终答案，我们计算最优策略的期望码长，这可以通过从 Huffman 树的根进行 DFS 完成。
复杂度：Huffman 树可在 \(n \log n\) 时间内构建（主要由对概率排序决定）。平均码长（即对应策略的代价）可通过 DFS 在 \(O(n)\) 时间内计算。因此总运行时间为 \(O(n \log n)\)。
解答来源：hw05-sol.pdf · 5-6 · confidence: high
题面来源：hw05.pdf · 4 · confidence: high
有 \(n\) 位客人来到一所房子参加聚会，但主人知道其中有 \(m\) 对客人互为敌人（一位客人可以与多位其他客人互为敌人）。房子里有两个房间，主人希望将客人分配到两个房间中，使得尽可能多的敌人对被拆散。客人们都在房子外面等待，急于进入，因此主人需要快速将他们分配到两个房间，即使这意味着得到的不是最优解。设计一个 \(O(n + m)\) 时间的算法，使得至少一半的敌人对被拆散。给出包含三部分的解答。
逐个将客人加入房间，每次将客人放入当前敌人较少的那个房间。分析这一贪心策略能拆散多少对敌人。
自检：当加入第 \(i\) 位客人时，假设其已入场的敌人有 \(m_i\) 位，该贪心策略至少能拆散其中几对？
主要思想：我们逐个加入客人，每次将客人放入当前其敌人较少的那个房间（若敌人数量相等，则任意选择一个房间）。
正确性证明：设 \(m_i\) 为第 \(i\) 位客人在加入时已被分配到房间的敌人数量。通过将该客人放入其敌人较少的房间，我们至少拆散了 \(m_i/2\) 对敌人。因此我们至少拆散了 \(\sum_i m_i/2\) 对敌人，而 \(\sum_i m_i\) 等于敌人对的总数，故至少拆散了一半。
运行时间：每位客人被遍历一次，我们可以根据其敌人数量成比例的时间确定将其分配到哪个房间（例如使用一个数组记录每位客人当前被分配的房间），即每对敌人最多被考虑两次，因此总时间为 \(O(n + m)\)。
（注：此问题等价于最大割（max-cut）问题：给定一个无向图，在最大割问题中我们希望将顶点划分为两个集合，使得尽可能多的边两端点在不同集合中。）
解答来源：hw05-sol.pdf · 6-7 · confidence: high
题面来源：hw05.pdf · 4 · confidence: high
hw05.pdfhw05-sol.pdf