COMP5270 Assignment 2 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 调整，关键是按顺序处理每个顶点，在已知前面分配结果的情况下，选择让当前条件期望更大的那侧。