COMP5270 Assignment 2 完整题解

Posted on In Word count in article: 4.4k Reading time ≈ 16 mins.
COMP5270 Assignment 2 完整题解，涵盖 Problem 1（Karger 算法枚举最小割）和 Problem 2 (a-f)（Pairwise Independent Hash Functions、图生成、随机化 MaxCut、哈希去随机化、条件期望去随机化、运行时间比较）。

COMP5270 Assignment 2 完整题解

本题解合并 Problem 1 与 Problem 2(a)–2(f) 的所有子问题，按题目顺序排列。

Problem 1 — Karger 算法列出所有最小割

中文题目

简要说明如何修改 Karger 算法，使它能够以高概率（例如 99%）列出一个图的所有最小割（minimum cuts）。同时分析你的算法时间复杂度。

原题

Briefly explain how to modify Karger's algorithm to list, with high probability (say 99%), all minimum cuts of a graph. What is the time complexity of your algorithm?

知识点

  • Karger contraction algorithm
  • minimum cut / global min-cut
  • 随机算法重复放大成功概率
  • union bound
  • 最小割数量上界
  • 高概率枚举（high-probability enumeration）

核心思路

普通的 Karger contraction algorithm 一次运行，只会随机输出一个 cut。要把它改成"列出所有 minimum cuts"，最直接的方法不是改 contraction 过程本身，而是：

  • 独立重复运行 Karger 算法很多次
  • 每次得到一个 cut 后，计算它的 cut size
  • 维护当前见过的最小 cut size
  • 只保留所有大小等于这个最小值的 cuts
  • 对这些 cuts 做去重，最后输出去重后的结果集合

换句话说，这里真正的修改是把"单次随机输出一个最小割候选"变成"多次采样并收集所有采样到的 minimum cuts"。

为什么这样能找到所有 minimum cuts

Karger 算法的经典结论是，对于一个有 \(n\) 个顶点的图，任意一个固定的 minimum cut 在一次运行中被输出的概率至少为

\[ \frac{2}{n(n-1)}. \]

设某个特定 minimum cut 为 \(C\)。如果我们独立运行算法 \(r\) 次，那么一次都没有采到 \(C\) 的概率至多为

\[ \left(1-\frac{2}{n(n-1)}\right)^r. \]

当 \(r = \Theta(n^2 \log n)\) 时，这个概率会下降到非常小。

另一方面，一个图的 minimum cuts 总数至多为

\[ \binom{n}{2} = \frac{n(n-1)}{2}. \]

所以我们可以对所有 minimum cuts 使用 union bound。只要把重复次数取成足够大的 \(c n^2 \log n\)，就能保证"漏掉至少一个 minimum cut"的总概率低于 \(1\%\)，也就是以至少 99% 的概率列出全部 minimum cuts。

算法描述

  1. 设 best = +∞，设集合 S = ∅
  2. 重复运行 Karger 算法 \(r = \Theta(n^2 \log n)\) 次
  3. 每次得到 cut \(C\)，记其大小为 \(|C|\)
  4. 如果 \(|C| < best\)，则更新 best = |C|，并把 S 重置为只包含 \(C\)
  5. 如果 \(|C| = best\)，则把 \(C\) 加入 S
  6. 对 cuts 做规范化表示并去重（例如始终用两侧顶点集里字典序较小的那侧表示），避免同一个 cut 被重复存储
  7. 输出 S

时间复杂度

如果一次 Karger 运行耗时 \(O(n^2)\)，总共运行 \(O(n^2 \log n)\) 次，则

\[ \boxed{O(n^4 \log n).} \]

去重带来的额外开销不会改变这个主导项。

可直接交作业的短答案

Run Karger's algorithm independently \(O(n^2\log n)\) times, keep every cut whose size equals the minimum found, and deduplicate them. Since each fixed minimum cut is found with probability at least \(2/(n(n-1))\), and there are at most \(n(n-1)/2\) minimum cuts, this lists all minimum cuts with probability at least \(99\%\). If one run takes \(O(n^2)\), the total running time is \(O(n^4\log n)\).

一点补充理解

这道题的关键不是设计一个全新的算法，而是把 Karger 的"单个最小割采样器"升级成"最小割全集收集器"。核心工具只有两个：单个 minimum cut 的命中概率下界，加上 minimum cut 总数的上界与 union bound。本质上是在练习：把一个 randomized existence guarantee，转成 high-probability enumeration guarantee。

Problem 2(a) — Pairwise Independent Hash Functions

中文题目

实现课程中讲到的两两独立哈希函数族（pairwise independent hash functions）。

原题

Implement the family of pairwise independent hash functions seen in the unit.

知识点

  • universal hashing
  • pairwise independence
  • 模素数线性哈希
  • rejection sampling
  • 只用 random.getrandbits(k) 生成随机数

核心思路

课程里最标准的一族两两独立哈希函数是：

\[ h_{a,b}(x)=((ax+b) \bmod p) \bmod m \]

其中 \(p\) 是大于输入范围的素数，\(a \in \{1,2,\dots,p-1\}\)，\(b \in \{0,1,\dots,p-1\}\)，\(m\) 是哈希值范围（桶的个数）。随机选 \(a,b\) 后得到一个具体哈希函数 \(h_{a,b}\)，该族满足 pairwise independence。

为什么这个构造可行

在模素数 \(p\) 的域上，映射 \(x \mapsto ax+b \pmod p\) 是随机线性哈希的经典构造。对任意 \(x_1 \neq x_2\) 与任意目标值 \(y_1,y_2\)，联立方程

\[ ax_1+b \equiv y_1 \pmod p,\qquad ax_2+b \equiv y_2 \pmod p \]

有唯一解 \((a,b)\)，因此从所有 \((a,b)\) 中均匀随机选取时，不同输入的像成对独立分布，这正是 pairwise independent family。

实现时的关键点

题目限制只能用 random.getrandbits(k) 产生随机性，因此需要自行实现 randbelow(n)（rejection sampling 方式）：

  1. 令 \(k = \text{bit\_length}(n-1)\)
  2. 调用 random.getrandbits(k) 得到 \(k\) 位随机整数
  3. 若该数小于 \(n\)，接受；否则丢弃重试

参考实现

import random

def randbelow(n):
    if n <= 0:
        raise ValueError("n must be positive")
    k = (n - 1).bit_length()
    while True:
        r = random.getrandbits(k)
        if r < n:
            return r

def make_pairwise_hash(m, p=2147483647):
    a = randbelow(p - 1) + 1   # a ∈ {1,...,p-1}
    b = randbelow(p)           # b ∈ {0,...,p-1}

    def h(x):
        return ((a * x + b) % p) % m

    return h

容易错的地方

  1. 让 \(a=0\)：\(h\) 会退化成常数平移，失去 pairwise independence 性质，必须保证 \(a\ge 1\)。
  2. 直接对 getrandbits(k) 取模：getrandbits(k) % n 有偏差，不均匀，必须用 rejection sampling。
  3. \(p\) 不是素数：构造依赖模素数域，\(p\) 必须是素数。
  4. 使用题目禁止的随机 API：若题目明确只允许 getrandbits(k)，不要调用 random.randint 等。

可直接写进作业的简短版本

We use the standard pairwise independent family \(h_{a,b}(x)=((ax+b) \bmod p) \bmod m\), where \(p\) is prime, \(a \in \{1,\dots,p-1\}\), and \(b \in \{0,\dots,p-1\}\). Since the task only allows random.getrandbits(k), we implement a uniform randbelow(n) using rejection sampling, then sample \(a\) and \(b\) uniformly and return the resulting hash function.

Problem 2(b) — 生成 \(K_n\) 完全图和 \(C_n\) 环图

中文题目

实现两个函数：输入 \(n\)，返回 (1) \(n\) 个顶点的完全图 \(K_n\)；(2) \(n\) 个顶点的环图 \(C_n\)。

原题

Implement two functions returning, on input \(n\), (1) the complete graph \(K_n\) on \(n\) vertices; (2) the cycle graph \(C_n\) on \(n\) vertices.

知识点

  • 完全图（complete graph）
  • 环图（cycle graph）
  • 邻接表（adjacency list）
  • 图的 API 设计

核心思路

这道题是整个 Assignment 2 的基础设施题，后续所有 MaxCut 实验都依赖这两个函数。

完全图 \(K_n\)： 任意两个不同顶点之间都有一条边。顶点数 \(n\)，边数 \(\binom{n}{2}\)，每个顶点度数 \(n-1\)。两层循环实现：外层遍历所有顶点，内层从该顶点的下一个顶点开始，逐对插入边。

环图 \(C_n\)： \(n\) 个顶点排成一个环，每相邻两个顶点之间有一条边，首尾相连。顶点数 \(n\)，边数 \(n\)，每个顶点度数 \(2\)。连接 \((0,1),(1,2),\dots,(n-2,n-1),(n-1,0)\)。

参考实现

from graph import Graph

def complete_graph(n):
    G = Graph()
    for i in range(n):
        G.insert_vertex(i)
    for i in range(n):
        for j in range(i + 1, n):
            G.insert_edge(i, j)
    return G

def cycle_graph(n):
    G = Graph()
    for i in range(n):
        G.insert_vertex(i)
    for i in range(n):
        G.insert_edge(i, (i + 1) % n)
    return G

两种图在后续问题中的角色

图 \(K_n\) \(C_n\)
边数 \(\Theta(n^2)\) \(\Theta(n)\)
每顶点度 \(n-1\) \(2\)
MaxCut 最优值 \(\lfloor n^2/4 \rfloor\) \(n\) 或 \(n-1\)
算法效果 接近最优，方差小 约 \(n/2\)，方差较大

两个图分别代表稠密图和稀疏图两种极端情况，是后续实验的基准测试用例。

容易错的地方

  1. 完全图循环边界：内层从 i + 1 开始，否则会重复插入边。
  2. 环图首尾连接：用取模 (i + 1) % n 自动覆盖最后一条边 \((n-1, 0)\)。
  3. Graph API 的无向边语义：insert_edge(u, v) 同时加入 \(u\to v\) 和 \(v\to u\)，不需要手动处理双向。

Problem 2(c) — 随机化 MaxCut 算法

中文题目

实现随机近似算法求 MaxCut。对于 \(n=2\) 到 \(100\)，在 \(K_n\) 和 \(C_n\) 上各运行 \(k=20\) 次，记录结果并绘图（平均值、平均值±标准差、最小值、最大值），对图形结果进行简要评论。

原题

Implement the randomised approximation algorithm for MaxCut (function randmaxcut(G)). For \(n = 2\) to \(100\), run it on both \(K_n\) and \(C_n\), each for \(k = 20\) iterations, and report the results on two different graphs...

知识点

  • MaxCut 问题（最大割）
  • 随机算法
  • 期望值分析（线性期望）
  • 经验均值与标准差
  • 近似比（approximation ratio）

MaxCut 问题回顾

给定无向图 \(G=(V,E)\)，MaxCut 把顶点集划分成两部分 \(S\) 和 \(T=V\setminus S\)，最大化跨越划分的边数：

\[ \text{cut}(S,T) = |\{(u,v)\in E : u\in S, v\in T\}|. \]

MaxCut 是经典 NP-hard 问题。

随机化算法的核心思想

最朴素的随机化算法：

  1. 对每个顶点 \(v\)，独立地以概率 \(1/2\) 放入 \(S\) 或 \(T\)
  2. 返回这样得到的割

期望值分析： 对任意一条边 \((u,v)\)，\(u\) 和 \(v\) 独立随机分配，被割开的概率为 \(1/2\)。由线性期望：

\[ \mathbb{E}[\text{cut size}] = \frac{1}{2}|E|. \]

最优割至多 \(|E|\)，所以随机算法期望达到最优值一半，近似比为 \(1/2\)。

为什么在 \(K_n\) 和 \(C_n\) 上表现不同

完全图 \(K_n\)： \(|E|=\binom{n}{2}\)，期望割大小 \(\approx n(n-1)/4\)，最优割 \(\lfloor n^2/4\rfloor\)，两者几乎相等。大量独立边产生良好的集中效应，标准差相对均值很小。

环图 \(C_n\)： \(|E|=n\)，期望割大小 \(n/2\)，最优割 \(n\) 或 \(n-1\)，期望与最优差距绝对值为 \(n/2\)。集中效应弱，标准差相对均值较大。

实验结果的预期图形特征

指标 \(K_n\) \(C_n\)
平均值曲线 紧贴最优值（平方增长） 在 \(n/2\) 附近（线性增长）
±标准差范围 窄，相对割大小很小 宽一些
最小/最大值 紧贴均值 散布更广

参考实现思路

import random

def randmaxcut(G):
    assignment = {}
    for v in G.list_vertices():
        assignment[v] = random.getrandbits(1)  # 0 -> S, 1 -> T

    cut_size = 0
    for u, v in G.list_edges():
        if assignment[u] != assignment[v]:
            cut_size += 1
    return cut_size

注意题目要求只用 random.getrandbits(1) 生成单个随机比特。

Problem 2(d) — 基于哈希函数去随机化的 MaxCut

中文题目

实现基于哈希函数的去随机化近似算法求 MaxCut。对于 \(n=2\) 到 \(100\)，在 \(K_n\) 和 \(C_n\) 上运行，记录结果（平均值、最小值、最大值、标准差），对结果进行简要评论。

原题

Implement the derandomised approximation algorithm for MaxCut based on hash functions...

知识点

  • 去随机化（derandomization）
  • 两两独立哈希函数（pairwise independent hash functions）
  • 期望的线性性
  • 固定种子的去随机化

从随机化到去随机化

Problem 2(c) 的随机算法依赖对每个顶点的独立随机抛硬币。去随机化的目标是用确定性算法模拟随机算法的效果，核心思路是：用两两独立哈希函数替代完全独立的随机比特。

为什么两两独立哈希函数够用

设哈希函数 \(h: V \to \{0,1\}\) 决定分配。若 \(h\) pairwise independent，则对任意不同顶点 \(u,v\)，\((h(u),h(v))\) 成对独立，因此每条边被割开的概率：

\[ P[h(u) \neq h(v)] = P[h(u)=0]P[h(v)=1] + P[h(u)=1]P[h(v)=0] = \frac{1}{2}. \]

由线性期望，期望割大小仍然是 \(|E|/2\)。

算法步骤

  1. 固定哈希族参数：素数 \(p\)，桶数 \(m=2\)（映射到 \(\{0,1\}\)）
  2. 对每一对可能的 \((a,b)\)（\(a\in\{1,\dots,p-1\}\)，\(b\in\{0,\dots,p-1\}\)）：
    • 定义 \(h_{a,b}(v) = ((a \cdot v + b) \bmod p) \bmod 2\)
    • 计算该哈希函数产生的割大小
  3. 返回割大小最大的那个割值

实验结果的预期特征

指标 预期
平均值 等于最优值
最小值 = 最大值 与平均值相同
标准差 \(0\)（三条线完全重合）

原因：这是确定性算法，对固定输入每次运行结果完全一样。

与随机化版本的关键区别

随机化版本 哈希去随机化版本
结果是否确定 否 是
标准差 \(>0\) \(=0\)
最优保证 期望 \(\geq 1/2\) 实际达到 \(\geq 1/2\)
运行时间 \(O(n^2)\) 更慢（需遍历所有哈希函数）

容易错的地方

  1. 混淆"随机选一个哈希函数"和"遍历所有哈希函数找最优"：前者仍是随机算法，题目要求后者（确定性去随机化）。
  2. 让 \(a=0\)：必须保证 \(a \in \{1,\dots,p-1\}\)。
  3. \(p\) 的选择：\(p\) 需大于顶点数 \(n\)，通常取 \(2^{31}-1=2147483647\)。

Problem 2(e) — 基于条件期望去随机化的 MaxCut

中文题目

实现基于条件期望（method of conditional expectations）的去随机化近似算法求 MaxCut。对于 \(n=2\) 到 \(100\)，在 \(K_n\) 和 \(C_n\) 上运行，记录结果并评论。

原题

Implement the derandomised approximation algorithm for MaxCut based on the method of conditional expectations...

知识点

  • 条件期望（conditional expectation）
  • 去随机化（derandomization）
  • Method of conditional expectations
  • 贪心消减（deterministic rounding）

条件期望方法的核心思想

Method of Conditional Expectations 是通用的去随机化技术，框架如下：

  1. 定义随机变量：考虑随机算法产生的目标值 \(X\)（如割大小）
  2. 计算期望：\(\mathbb{E}[X]\) 是容易计算的值（如 \(|E|/2\)）
  3. 逐步固定随机比特：按顺序遍历每个顶点，每次选择让条件期望不降低的那一侧

MaxCut 上的条件期望法

设顶点顺序为 \(v_1,v_2,\dots,v_n\)。决定 \(v_i\) 的分配时，\(v_1,\dots,v_{i-1}\) 已分配好。计算两种选择的条件期望割大小，选择较大的那个。

关键不等式：

\[ \max(\mathbb{E}[X \mid E, v_i\to S],\ \mathbb{E}[X \mid E, v_i\to T]) \geq \mathbb{E}[X \mid E]. \]

每一步都不降低条件期望，最终割大小至少是原始期望值：

\[ \text{最终割大小} \geq \mathbb{E}[\text{割大小}] = \frac{1}{2}|E|. \]

所以这个确定性算法保证至少达到最优割的一半。

与哈希函数去随机化的比较

特征 哈希函数法 条件期望法
是否确定性 是 是
近似比保证 \(\geq 1/2\) \(\geq 1/2\)
实际效果 通常更好 通常达到最优
时间复杂度 \(O(n^2 \cdot \text{哈希空间})\) \(O(n^2)\)

实验结果的预期

指标 预期
平均值 最优割值
最小/最大值 与平均值相同
标准差 \(0\)

原因：这是确定性算法，对固定输入每次运行结果完全一样。

参考实现思路

def maxcut_conditionalexpect(G):
    vertices = G.list_vertices()
    assignment = {}  # 0 = S, 1 = T

    for v in vertices:
        neighbors_in_T = sum(1 for u in G.incident_edges(v)
                             if assignment.get(G.opposite(v, u), None) == 1)
        neighbors_in_S = sum(1 for u in G.incident_edges(v)
                             if assignment.get(G.opposite(v, u), None) == 0)
        # 选择贡献割边更多的一侧
        assignment[v] = 0 if neighbors_in_T >= neighbors_in_S else 1

    cut_size = sum(1 for u, w in G.list_edges()
                   if assignment[u] != assignment[w])
    return cut_size

Problem 2(f) — 三种 MaxCut 算法运行时间比较

中文题目

绘制三种方法在 \(n=2\) 到 \(100\)、在 \(K_n\) 上的运行时间（\(k=20\) 次迭代的平均值）。比较三个算法的速度快慢和可靠性。

原题

Plot the running time of the three approaches, for \(n = 2\) to \(100\), when run on \(K_n\)...

知识点

  • 运行时间测量
  • 算法复杂度
  • 随机算法 vs 去随机化算法
  • 时间复杂度阶的比较

三种算法回顾

  1. 随机化算法 (randmaxcut)：每个顶点独立随机分配
  2. 哈希函数去随机化 (maxcut_hashfunctions)：遍历所有哈希函数，选最优
  3. 条件期望去随机化 (maxcut_conditionalexpect)：逐顶点贪心选择

理论时间复杂度分析

在完全图 \(K_n\) 上（\(|E|=\Theta(n^2)\)）：

算法 单次运行复杂度 备注
随机化 \(O(n^2)\) 遍历所有边一次
哈希函数 \(O(n^2 \cdot p)\) 对每个 \((a,b)\) 遍历所有边；\((a,b)\) 空间约 \(p^2\)
条件期望 \(O(n^2)\) 逐顶点处理，每个顶点检查所有邻居

哈希函数法需要枚举所有 \((a,b)\) 组合，复杂度远高于其他两者。

实验观察

在 \(K_n\) 上测量 \(n=2\) 到 \(100\) 的运行时间，典型结果：

\[ \text{随机化} < \text{条件期望} < \text{哈希函数（最慢）} \]

随机化最快： 一次遍历所有边，最简单直接的操作。

条件期望比随机化慢： 每个顶点需两次遍历邻居（比较两种选择的贡献），工作量约多一倍。

哈希函数法最慢： 需对每一对 \((a,b)\)（约 \(p^2\) 种）计算一次割大小，每次 \(O(n^2)\) 边，总复杂度远高于其他两者。

可靠性比较

算法 结果是否确定 最优保证
随机化 否（每次运行不同） 期望 \(\geq 1/2\)
条件期望 是（可重复） 保证 \(\geq 1/2\)
哈希函数 是（可重复） 保证 \(\geq 1/2\)

去随机化的两种方法都是确定性的，对固定输入总产生相同的割——可重复、可预测，是相对随机算法的主要优势。

实际应用中的权衡

  • 只需一个近似解且要求快：随机化算法
  • 需要可重复结果，时间不敏感：去随机化算法
  • 图规模很大：即使去随机化算法复杂度也是 \(O(n^2)\) 级别，需考虑实际运行时间

从实验数据看趋势

\(n\) 较小时三种算法差异不大（常数因子主导）。随着 \(n\) 增大，\(O(n^2)\) 与 \(O(n^2 \cdot p)\) 的差距越来越明显：随机化和条件期望曲线形态接近，哈希函数法曲线斜率更大。