企业官网建设流程全解析

• 文档
• 教程
• 教育

本篇技术指南围绕《算法导论》（Introduction to Algorithms, Third Edition，即 CLRS）第 35 章"近似算法"中35.4 节"随机化与线性规划"（Randomization and linear programming）的四道课后习题展开，以仓库 docs/Chap35/35.4.md 中的完整解答为主体，重点精解MAX-CUT 问题的随机化 2 近似算法 APPROX-MAX-CUT。读者将掌握随机化近似算法的标准分析套路：抛硬币式随机划分 + 指示随机变量 + 线性期望，以及 8/7 近似（MAX-3-CNF）、2 近似（MAX-CNF 与 MAX-CUT）的近似比推导逻辑，并能对照仓库源码结构独立验证每一处推导。

一、35.4 节在 CLRS 中的定位：近似算法的随机化武器

在第 35 章中，前几节分别给出了顶点覆盖、旅行商问题、集合覆盖的确定性近似算法，而35.4 节引入两条新路线：随机化与线性规划舍入。从本站点导航配置 mkdocs.yml 中可以看到，第 35 章的目录结构为：

• 35.1 The vertex-cover problem（docs/Chap35/35.1.md）
• 35.2 The traveling-salesman problem（docs/Chap35/35.2.md）
• 35.3 The set-covering problem（docs/Chap35/35.3.md）
• 35.4 Randomization and linear programming（docs/Chap35/35.4.md）
• 35.5 The subset-sum problem（docs/Chap35/35.5.md）
• Chap 35 Problems（docs/Chap35/Problems/）

35.4 节的核心思想是：当 NP 完全问题难以精确求解时，随机赋值往往能以很高的概率给出接近最优的解——例如 MAX-3-CNF 可满足性问题的随机化 8/7 近似算法。仓库 docs/Chap35/35.4.md 收录了本节 4 道习题（35.4-1 至 35.4-4），其中35.4-3（MAX-CUT）给出了完整证明，其余三题在仓库中标注为(Omit!)，本文将分别呈现题目原文并依据教科书标准方法给出思路性补述，与仓库的完整解答形成互补。

二、35.4-1：允许子句含正反文字时，MAX-3-CNF 仍是 8/7 近似

题目原文（摘自 docs/Chap35/35.4.md）：

Show that even if we allow a clause to contain both a variable and its negation, randomly setting each variable to 1 with probability $1/2$ and to 0 with probability $1/2$ still yields a randomized $8/7$-approximation algorithm.

背景：MAX-3-CNF 可满足性问题是第 35.4 节引入的经典随机化近似案例。标准的 MAX-3-CNF 实例中，每个子句恰好由 3 个互不相同的文字（literal）组成。随机化算法对每个变量独立地以概率 $1/2$ 置为 1、以概率 $1/2$ 置为 0，则对任一 3 文字子句，8 种赋值中有 7 种使其为真，即

$$ \Pr{\text{子句被满足}} = \frac{7}{8}. $$

设最优解满足 $m^$ 个子句（显然 $m^\le |C|$，即总子句数），随机赋值的期望满足子句数为

$$ \mathbb{E}[m] \ge \frac{7}{8},|C| \ge \frac{7}{8},m^*, $$

从而 $\mathbb{E}[m^*/m] \le 8/7$，得到随机化 $8/7$ 近似保证。

本题的放宽点：允许子句同时包含某个变量 $x$ 及其否定 $\neg x$。此时该子句形如 $(x \vee \neg x \vee l)$，无论 $x$ 取何值都恒真，被满足概率为 $1 \ge 7/8$；其余不含冲突的子句仍保持原有 3 个不同文字的结构，被满足概率仍为 $7/8$。因此每条子句被满足的概率均不低于 $7/8$，随机赋值算法依然是期望意义下的 $8/7$ 近似算法。需要说明的是，仓库中该题解答标注为(Omit!)，上述为基于教科书标准方法的推导思路。

三、35.4-2：MAX-CNF 可满足性的随机 2 近似算法

题目原文：

The MAX-CNF satisfiability problem is like the MAX-3-CNF satisfiability problem, except that it does not restrict each clause to have exactly 3 literals. Give a randomized 2-approximation algorithm for the MAX-CNF satisfiability problem.

思路要点（仓库中标注 Omit，以下为教科书方法补述）：MAX-CNF 中每个子句可以包含任意个文字。随机赋值同样以概率 $1/2$ 将每个变量置为 1。设某子句 $C_j$ 含 $k_j$ 个文字，则它不被满足当且仅当每个文字都为假；由于各变量独立且每个文字以概率 $1/2$ 为真，有

$$ \Pr{C_j \text{ 不被满足}} \le \frac{1}{2^{k_j}} \le \frac{1}{2}, $$

即每个子句被满足的概率至少为 $1/2$。于是

$$ \mathbb{E}[\text{满足的子句数}] \ge \frac{1}{2},|C| \ge \frac{1}{2},\text{opt}, $$

得到随机化 2 近似算法。这里 $k_j \ge 1$，故 $1/2^{k_j} \le 1/2$ 恰好给出 2 近似比；若子句含重复文字，不满足概率只会更低，结论不变。

四、35.4-3：MAX-CUT 的随机 2 近似算法——完整证明（仓库原解）

这是 docs/Chap35/35.4.md 中唯一给出完整解答的题目，也是本节的技术核心。

题目原文：

In the MAX-CUT problem, we are given an unweighted undirected graph $G = (V, E)$. We define a cut $(S, V - S)$ as in Chapter 23 and the weight of a cut as the number of edges crossing the cut. The goal is to find a cut of maximum weight. Suppose that for each vertex $v$, we randomly and independently place $v$ in $S$ with probability $1/2$ and in $V - S$ with probability $1/2$. Show that this algorithm is a randomized 2-approximation algorithm.

其中"割 (cut) $(S, V - S)$"的定义与第 23 章最小生成树中的割概念一致，可参见 docs/Chap23/23.1.md 中"respects a cut / light edge"等用法。MAX-CUT 的目标是找一条割，使跨越割的边数（割的权）最大。

4.1 算法重述与复杂度

仓库将随机化算法重写为如下清晰的伪代码（docs/Chap35/35.4.md）：

APPROX-MAX-CUT(G) for each v in V flip a fair coin if heads add v to S else add v to V - S

该算法显然运行在线性时间$O(V + E)$ 内：对每个顶点抛一次均匀硬币并归入一侧，无需比较、排序或迭代收敛。

4.2 定义事件与指示随机变量

对每条边 $(u, v) \in E$，定义事件 $A_{uv}$ 表示"边 $(u, v)$ 跨越割 $(S, V - S)$"，并令 $1_{A_{uv}}$ 为其指示随机变量。事件 $A_{uv}$ 发生当且仅当 $u$ 与 $v$ 被主循环放入不同的集合，因此：

$$ \begin{aligned} \Pr{A_{uv}} &= \Pr{u \in S \wedge v \in V - S} + \Pr{u \in V - S \wedge v \in S} \\ &= \frac{1}{2}\cdot\frac{1}{2} + \frac{1}{2}\cdot\frac{1}{2} \\ &= \frac{1}{2}. \end{aligned} $$

这正是"每一边以 $1/2$ 概率被跨越"的直观：$u$、$v$ 独立落入两侧，只有"同侧"与"异侧"两种等可能情形。该分析模式与第 5.2 节"指示随机变量"一脉相承，可对照 docs/Chap05/5.2.md 中利用指示随机变量计算期望的技术。

4.3 期望分析

记 $\text{opt}$ 为 $G$ 中最大割的权（即最大跨越边数），记 $c = |(S, V - S)|$ 为 APPROX-MAX-CUT 产生的割的大小。显然

$$ c = \sum_{(u, v) \in E} 1_{A_{uv}}, $$

并且 $\text{opt} \le |E|$（该上界在 $G$ 为二分图时取到等号，因为二分图的割可以覆盖全部边）。于是由期望的线性性：

$$ \begin{aligned} \mathbb{E}[c] &= \mathbb{E}\left[\sum_{(u, v) \in E} 1_{A_{uv}}\right] \\ &= \sum_{(u, v)\in E}\mathbb{E}[1_{A_{uv}}] \\ &= \sum_{(u, v)\in E}\Pr{A_{uv}} \\ &= \frac{1}{2}|E| \\ &\ge \frac{1}{2},\text{opt}. \end{aligned} $$

注意：期望线性性在此处是关键工具——即使各 $1_{A_{uv}}$ 之间并不独立，期望的和仍等于和的期望，无需任何独立性假设。

4.4 近似比结论

仓库原文以比值形式收尾：

$$ \mathbb{E}\left[\frac{\text{opt}}{c}\right] \le \frac{|E|}{1/2,|E|} = 2, $$

因此APPROX-MAX-CUT 是随机化 2 近似算法。需要指出的是，上式在形式上借用了 $\text{opt} \le |E|$ 与 $\mathbb{E}[c] = |E|/2$ 的比值关系；严格地说，$c$ 作为随机变量出现在分母中，直接取 $1/\mathbb{E}[c]$ 并不等价于 $\mathbb{E}[\text{opt}/c]$，教科书采用 Jensen 不等式思路给出期望意义下的近似比保证。从工程视角看，这条证明链给出了清晰的可验证结论：随机抛硬币即可在期望意义上逼近最优割的 $1/2$，近似比 2，且算法线性时间、无需任何图论预处理。该结论同时呼应了 35.4 节的中心论点——随机化是构造近似算法的极简而有效的途径。

五、35.4-4：线性规划松弛中约束 (35.19) 的冗余性

题目原文：

Show that the constraints in line (35.19) are redundant in the sense that if we remove them from the linear program in lines (35.17)–(35.20), any optimal solution to the resulting linear program must satisfy $x(v) \le 1$ for each $v \in V$.

背景：第 35.4 节在分析 MAX-3-CNF 时还引入了线性规划舍入技术：将整数规划松弛为线性规划（LP），其中对每个变量 $v$ 设有 $0 \le x(v) \le 1$ 的取值约束，并对每个子句设有关于文字取值之和的不等式约束。约束组 (35.17)–(35.20) 中，式 (35.19) 即上界约束 $x(v) \le 1$。

思路要点（仓库标注 Omit，以下为教科书方法补述）：本题要证明 $x(v) \le 1$ 约束可以从 LP 中安全删除——若删除后求出的任一最优解出现某个 $x(v) > 1$，可以通过把该变量截断到 1，同时保持所有子句约束不违反、且不降低目标值，从而说明存在一个满足 $x(v) \le 1$ 的等价最优解。核心观察是：目标函数中变量的系数非负，且子句约束均为"和不超过 1"的上界形式，因此将变量从超过 1 的值下调至 1 只会使目标值向不坏的方向变化。这体现出 LP 舍入分析中"冗余约束 + 可行解规范化"的典型论证手法。

六、在本仓库中查阅与核验本节内容

该仓库是《算法导论》第三版习题解答的 Markdown 镜像站点，所有章节与习题均以独立.md文件组织，第 35.4 节解答位于 docs/Chap35/35.4.md，同章其余小节与课后问题分别位于 docs/Chap35/ 与 docs/Chap35/Problems/。核验要点：

• 导航与渲染：站点由 MkDocs + Material for MkDocs 构建，配置见 mkdocs.yml，其中明确将 35.4 节挂载为 "Randomization and linear programming"；数学公式由 KaTeX 渲染，相关脚本见 js/katex.js 与 css/katex.css（依据 README.md 的站点构建说明）。
• 公式宏：35.4 节原文在解答前用\gdef定义了 $\Ex$、$\Prob$、$\opt$ 等简写宏（docs/Chap35/35.4.md 第 17-19 行），本文为通用性改用 $\mathbb{E}$、$\Pr$、$\text{opt}$ 书写，含义一致。
• 交叉引用：MAX-CUT 中"割"的定义沿用第 23 章（docs/Chap23/23.1.md），指示随机变量的期望分析技法可回溯至第 5.2 节（docs/Chap05/5.2.md），便于读者沿着仓库路径构建完整的知识链。

综上所述，35.4 节通过 MAX-3-CNF、MAX-CNF 与 MAX-CUT 三个实例展示了随机化近似算法的统一套路——独立随机赋值 + 每条约束被满足概率的下界 + 期望线性性——而 docs/Chap35/35.4.md 中 APPROX-MAX-CUT 的完整证明，正是这套方法最简洁、最易复现的范本。

• 文档
• 教程
• 教育