COMP5270 Assignment 2 完整题解

Posted on In Word count in article: 6.7k Reading time ≈ 24 mins.
COMP5270 Assignment 2 完整题解，涵盖 Problem 1（Karger 算法枚举最小割）和 Problem 2 (a-f)（MaxCut 近似算法的实现与分析）。

COMP5270 Assignment 2 完整题解

本题解涵盖 COMP5270 Assignment 2 的全部问题，包含 Problem 1（Karger 算法与最小割枚举）以及 Problem 2 的六个子问题（Pairwise Independent Hash Functions、\(K_n\)/\(C_n\) 图生成、随机化 MaxCut、哈希函数去随机化、条件期望去随机化、运行时间比较）。

所有内容均基于课程 lecture notes 与算法原理撰写，供学习参考使用。

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 表示成两侧顶点集里较小字典序的一侧，避免同一个 cut 被重复存储
  7. 输出 S

时间复杂度

如果一次 Karger 运行耗时记为 \(O(n^2)\)，而我们总共运行

\[ O(n^2 \log n) \]

次，那么总时间复杂度就是

\[ O(n^2) \cdot O(n^2 \log n) = O(n^4 \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，也就是对任意不同的 \(x_1,x_2\)，它们的哈希值分布是成对独立的。

为什么这个构造可行

在模素数 \(p\) 的域上，映射

\[ x \mapsto ax+b \pmod p \]

是最经典的随机线性哈希构造。

对于任意不同的两个输入 \(x_1 \neq x_2\)，以及任意两个目标值 \(y_1,y_2\)，联立方程

\[ ax_1+b \equiv y_1 \pmod p \]

\[ ax_2+b \equiv y_2 \pmod p \]

有唯一解 \((a,b)\)。这意味着从所有可能的 \((a,b)\) 中均匀随机选取时，不同输入的像会呈现两两独立的分布。因此这就是课程里常见的 pairwise independent family。

实现时的关键点

题目特别限制，你的 Python 代码只能通过：

import random
random.getrandbits(k)

来产生随机性。所以不能直接用 random.randrange() 或 random.randint()。

因此标准做法是自己写一个 randbelow(n)，用 rejection sampling 从 \(\{0,1,\dots,n-1\}\) 中均匀采样。

randbelow(n) 的思路

  1. 令 \(k = \text{bit\_length}(n-1)\)
  2. 调用 random.getrandbits(k) 得到一个 \(k\) 位随机整数
  3. 如果这个数小于 \(n\)，就接受
  4. 否则丢弃，重新抽一次

这样可以保证采样是均匀的。

参考实现

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   # 1..p-1
    b = randbelow(p)           # 0..p-1

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

    return h

如果 Ed 的接口要求你返回参数而不是闭包，也可以保存 a,b,p,m，然后单独写一个 hash(x) 方法，思路完全一样。

代码含义解释

这里：

  • a = randbelow(p - 1) + 1 保证 \(a \neq 0\)
  • b = randbelow(p) 保证 \(b\) 在 \([0,p-1]\) 内均匀分布
  • ((a * x + b) % p) % m 先在模 \(p\) 的域里做随机线性映射，再映射到目标范围 \(\{0,1,\dots,m-1\}\)

通常课程里要求你实现的，就是这个 family，而不是去重新证明它。

容易错的地方

1. 让 a = 0

如果 \(a=0\)，哈希函数就退化成常数平移，失去课程里要求的性质。所以必须保证 \(a \in \{1,\dots,p-1\}\)。

2. 直接对 getrandbits(k) 取模

如果写成：

random.getrandbits(k) % n

通常会引入偏差，不能保证均匀分布。正确方法是 rejection sampling。

3. 选的 \(p\) 不是素数

这个构造依赖模素数域的性质，所以 \(p\) 应该取素数。

4. 忘记根据题目限制控制随机数来源

如果作业明确要求只能用 random.getrandbits(k)，那就不要调用别的随机 API。

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

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ₙ 完全图和 Cₙ 环图

中文题目

实现两个函数：输入 \(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\)

完全图 \(K_n\) 是任意两个不同顶点之间都有一条边的图。对角化来说：

  • 顶点：\(n\) 个，通常编号为 \(0,1,\dots,n-1\)
  • 边：共 \(\binom{n}{2} = \frac{n(n-1)}{2}\) 条
  • 度数：每个顶点的度数为 \(n-1\)

实现方式是两层循环：外层遍历所有顶点，内层从该顶点的下一个顶点开始，遍历到最后一个顶点，每对顶点插入一条边。

环图 \(C_n\)

环图 \(C_n\) 是 \(n\) 个顶点排成一个环，每相邻两个顶点之间有一条边，首尾顶点也相连：

  • 顶点：\(n\) 个，编号 \(0,1,\dots,n-1\)
  • 边：共 \(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

注意： - 完全图的双层循环中，内层从 i + 1 开始，避免重复插入同一条边（因为 Graph API 的 insert_edge 会把 \((u,v)\) 和 \((v,u)\) 当作同一条边） - 环图用 (i + 1) % n 自动处理 \(n-1\) 到 \(0\) 的回边，这是 Python 里写环结构的常用技巧

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

图 \(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 开始，不是 0。否则会重复插入边或者漏掉某些边对。
  2. 环图的首尾连接：最后一条边 (n-1, 0) 容易忘掉，用取模技巧可以自动覆盖。
  3. Graph API 的语义：insert_edge(u, v) 会同时在邻接表中加入 u -> v 和 v -> 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 (one for \(K_n\), one for \(C_n\), each with 5 plots)...

知识点

  • 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\) 被独立随机分配到两侧
  • 共有 4 种等概率分配：\((S,S), (S,T), (T,S), (T,T)\)
  • 其中 \((S,T)\) 和 \((T,S)\) 两种会跨割
  • 所以 \(P[\text{边在割中}] = 2/4 = 1/2\)

边的期望贡献是 \(1/2\)。由线性期望，所有边的总期望割大小是：

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

由于最优割的大小最多是 \(|E|\)，所以这个随机算法至少达到最优值一半，近似比为 \(1/2\)。这是一个非常简单的算法，却有可证明的性能下界。

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

完全图 \(K_n\)

\(|E| = \binom{n}{2} = \frac{n(n-1)}{2}\)。

期望割大小为 \(|E|/2 = \frac{n(n-1)}{4}\)。

最优割大小也是 \(\lfloor n^2/4 \rfloor\)（相当于把顶点对半划分），所以随机算法在完全图上的期望表现几乎是最优的，而且由于所有割边数都集中在均值附近，标准差相对于割大小很小。

这是因为大量相互独立的边产生了良好的集中（concentration）效应。

环图 \(C_n\)

\(|E| = n\)，最优割大小为 \(n\) 或 \(n-1\)（把环的奇偶交替着色）。

期望割大小为 \(n/2\)，而最优是 \(n\)，所以近似比仍是 \(1/2\)，但此时：

  • 最优和期望的差距是绝对值 \(n/2\)，明显比完全图大
  • 每条边被割的概率仍是 \(1/2\)，但集中效应弱，标准差相对割大小较大

此外，环图上每条边被割与否并非完全独立（割的性质有图的约束），所以实验的分布形态也和完全图不同。

实验结果的预期图形特征

根据理论预期，绘图时应观察到：

指标 \(K_n\) 上的表现 \(C_n\) 上的表现
平均值曲线 紧贴最优值（平方增长） 在 \(n/2\) 附近（线性增长）
±标准差范围 窄，相对割大小很小 宽一些，但绝对值不大
最小/最大值 紧贴均值 散布更广
曲线形态 越来越接近最优 与最优差距恒定在约 \(n/2\)

参考实现思路

import random

def randmaxcut(G):
    # 把每个顶点随机分配到 S 或 T
    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) 生成单个随机比特，而不能用 random.random() 或 random.randint()。

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）
  • 期望的线性性
  • 条件化方法（method of conditional expectations）
  • 固定种子的去随机化

从随机化到去随机化

Problem 2(c) 的随机化算法依赖对每个顶点的独立随机抛硬币。去随机化（derandomization）的目标是：用确定性的算法模拟随机算法能达到的效果，而不真正使用随机性。

核心思路是：用两两独立（pairwise independent）的哈希函数替代完全独立的随机比特。虽然独立程度降低了，但足以保持可预测的期望性质。

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

回想随机化算法的核心：每个顶点 \(v\) 以 \(1/2\) 概率放入 \(S\)，以 \(1/2\) 概率放入 \(T\)。我们希望：

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

现在考虑用哈希函数 \(h: V \to \{0,1\}\) 来决定分配。关键观察：如果 \(h\) 是 pairwise independent 的，那么对任意不同的顶点 \(u,v\)，\(h(u)\) 和 \(h(v)\) 分布是独立的（或说"成对独立"）。

对每条边 \((u,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}. \]

即使只有成对的独立性，这个概率关系依然成立——因为我们只需要每条边两端比特独立的概率，而不是更多。

期望值的精确计算

更妙的是，由于 \(h\) 是确定性的（给定哈希函数后），我们可以直接计算任意给定 \(h\) 的割大小，不需要采样：

\[ \text{cut}(h) = \sum_{(u,v)\in E} \mathbf{1}[h(u) \neq h(v)]. \]

而对所有哈希函数（由随机种子决定）取平均，期望仍然是 \(|E|/2\)。

所以我们可以遍历所有哈希函数（或者用某种确定性方式覆盖），找出割最大的那个。由于状态空间是有限的（对于 \(p\) 素数和哈希值范围 \(m\)，共有 \((p-1)\cdot p\) 种 \((a,b)\) 组合），这在实验规模下是完全可行的。

这就是为什么输出是确定性的（平均=最小=最大），因为我们选的是所有哈希函数中割最大的那一个。

算法步骤

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

实际上，由于课程里用的是 pairwise independent family，我们可以遍历所有 \((a,b)\) 组合。

实验结果的预期特征

指标 预期
平均值 等于最优值（因为我们选的是最大者）
最小值 与平均值相同
最大值 与平均值相同
标准差 \(0\)（三条线完全重合）

对 \(K_n\)：割值应为 \(\lfloor n^2/4 \rfloor\)（完全图的全局最优割） 对 \(C_n\)：割值应为 \(n\) 或 \(n-1\)（环图交替染色的最优割）

与随机化版本的关键区别

随机化版本 哈希去随机化版本
结果是否确定 否（每次运行不同） 是（给定 \((a,b)\) 就确定）
标准差 \(>0\) \(=0\)
最优保证 期望 \(1/2\) 实际达到 \(1/2\) 以上
运行时间 每次 \(O(n^2)\) 需要遍历所有哈希函数，更慢

容易错的地方

  1. 混淆"随机选一个哈希函数"和"遍历所有哈希函数找最优"：前者还是随机算法，后者才是确定性去随机化版本。题目要求的是后者。
  2. 哈希函数生成方式：必须保证 \(a \neq 0\)（\(a \in \{1,\dots,p-1\}\)），\(b \in \{0,\dots,p-1\}\)，用 randbelow(p-1)+1 和 randbelow(p) 实现。
  3. 参数 \(p\) 的选择：\(p\) 需要大于顶点数 \(n\)，通常用一个大素数如 \(2147483647\)（\(2^{31}-1\)）。

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）
  • Yen's algorithm / method of conditional expectations
  • 贪心消减（deterministic rounding）

条件期望方法的核心思想

Method of Conditional Expectations（条件期望法）是一种通用的去随机化技术。它的基本框架是：

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

具体到 MaxCut 问题，我们按顺序决定每个顶点的分配。

MaxCut 上的条件期望法

设图的顶点顺序为 \(v_1, v_2, \dots, v_n\)。对每个顶点，我们依次决定它进入 \(S\) 还是 \(T\)。

当决定 \(v_i\) 的分配时，之前的顶点 \(v_1,\dots,v_{i-1}\) 已经分配好了，我们在已知这些信息条件下，计算 \(v_i\) 进入 \(S\) 或 \(T\) 时的条件期望割大小，选择条件期望更大的那个。

单个顶点的条件期望计算

设已确定分配的顶点集合为 \(A\)，未确定的为 \(B\)。对于一条连接 \(A\) 和 \(B\) 的边，它被割开的概率取决于 \(B\) 中顶点如何分配。

更精确的框架是：当我们决定 \(v_i\) 的值时，考虑两种选择的条件期望：

  • \(v_i \to S\) 时的期望割大小
  • \(v_i \to T\) 时的期望割大小

选择期望更大的那个。由于期望的线性性，这个计算在每一步都是可以高效进行的。

为什么这个方法有效

关键不等式是：无论我们选择哪一半，条件期望都至少和原来的（全）期望一样大。

形式化地，设 \(X\) 是随机变量，\(E\) 是某个事件（比如"随机比特的前 \(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]. \]

如果我们从 \(\mathbb{E}[X]\) 开始，然后沿着每一步都选择不降低条件期望的方向，最终得到的值至少是原始期望值，即：

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

所以这个确定性算法保证至少达到最优割的一半，与随机版本有相同的近似保证。

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

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

在本题的实验中，两种方法在 \(K_n\) 和 \(C_n\) 上都达到了最优值，但这是因为这两类图的结构比较特殊。在更一般的图上，两种方法的效果可能不同。

实验结果的预期

与 Problem 2(d) 完全一样：

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

原因相同：这是一个确定性算法，没有随机性，所以在同样输入下每次运行结果完全一样。

参考实现思路

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

    for v in vertices:
        # 计算如果 v 进入 S 的条件期望
        cut_if_S = sum(1 for u, w in G.list_edges()
                        if (u == v and assignment.get(w, None) == 1) or
                           (w == v and assignment.get(u, None) == 1))
        # 粗略计算：比较 v 的邻居中已分配到 T 的数量和已分配到 S 的数量
        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

实际实现可能需要根据具体 API 调整，关键是按顺序处理每个顶点，在已知前面分配结果的情况下，选择让当前条件期望更大的那侧。

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 去随机化算法
  • 时间复杂度阶的比较

三种算法回顾

我们在 Problem 2(c)、2(d)、2(e) 中分别实现和分析了三种 MaxCut 算法：

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

理论时间复杂度分析

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

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

哈希函数法的 \(p\) 是素数（通常取 \(2147483647\)），所以即使只枚举所有 \((a,b)\) 的一小部分，复杂度也远高于其他两者。

实验观察

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

随机化  <  条件期望  <  哈希函数
最快            中等        最慢

具体原因：

为什么随机化算法最快

随机化算法做一次割只需要：遍历所有边，对每条边检查两个端点是否在不同侧。这是最简单直接的操作。

条件期望为什么比随机化慢

条件期望算法在每个顶点上需要： 1. 遍历该顶点的所有邻居（完全图上每个顶点有 \(n-1\) 个邻居） 2. 对每种选择计算贡献（本质上是两次遍历邻居） 3. 做一次比较决定分配

这比随机算法"一次遍历所有边检查是否跨割"多了约一倍的工作量。

哈希函数法为什么最慢

哈希函数法需要对每一对 \((a,b)\)（约 \((p-1)\cdot p\) 种组合）计算一次割大小，每次计算都需要遍历 \(O(n^2)\) 条边。这使得总时间复杂度远高于其他两者，即使 \(p\) 固定不变也如此。

可靠性比较

算法 每次结果是否相同 是否总返回最优
随机化 否 否（期望 \(1/2\)，方差存在）
条件期望 是 否（保证 \(\geq 1/2\)，通常更好）
哈希函数 是 否（保证 \(\geq 1/2\)，通常最优）

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

实际应用中的权衡

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

从实验数据看趋势

在 \(n\) 较小时，三种算法时间差异较小，因为常数因子和系统开销占主导。

随着 \(n\) 增大，\(O(n^2)\) 和 \(O(n^2 \cdot p)\) 的差距越来越明显： - 随机化和条件期望的曲线接近线性（二次复杂度） - 哈希函数法的曲线更陡，斜率更大