COMP5270 Assignment 2 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()。