6.5 Reductions：归约、复杂度边界与线性规划

6.5 · Reductions覆盖 6 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

  • 能解释“6.5 · Reductions”如何把上界、下界、线性规划、单纯形、指派和零和博弈放进问题变换与答案恢复合同
  • 能逐项核对 归约、上界、下界、线性规划、单纯形算法、指派问题与零和博弈，并区分作者站内容与本页独立补充
  • 能按“T_A(n)=T_transform(n)+T_B(f(n))+T_decode(n)”手算一个最小输入，逐步检查“A 的每个合法实例都映射到 B，B 的解可恢复为 A 的解，并保持可行性与目标值关系”
  • 能注入“只展示一个样例映射就宣称完成归约，或把 A≤B 的方向反过来推导 A 的困难性”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“6·5 · Reductions”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“6·5 · Reductions”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“6·5 · Reductions”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：6.5 · Reductions

  • 1. 归约：在本页通过“声明源问题和目标问题”连接解释、交互状态和练习验收。
  • 2. 上界：在本页通过“构造实例变换”连接解释、交互状态和练习验收。
  • 3. 下界：在本页通过“求解目标实例”连接解释、交互状态和练习验收。
  • 4. 线性规划：在本页通过“解码回原问题”连接解释、交互状态和练习验收。
  • 5. 单纯形算法：在本页通过“证明双向正确与成本”连接解释、交互状态和练习验收。
  • 6. 指派问题与零和博弈：在本页通过“声明源问题和目标问题”连接解释、交互状态和练习验收。

从“我已经有一个求解器，能否借来解决新问题”开始

归约（reductions）是算法设计中的复用接口。它不是说两个问题“看起来相似”，而是给出一条可执行、可证明、可计费的链：

x∈X→fy=f(x)∈Y→solve⁡Yb→ga∈Sol⁡X(x)x\in X \xrightarrow{f} y=f(x)\in Y \xrightarrow{\operatorname{solve}_Y} b \xrightarrow{g} a\in \operatorname{Sol}_X(x)

先预测：若从二分图构造flow network只需O(E+V)，maxflow用时T，但从integral flow恢复matching要扫描O(E)，能否把总复杂度直接写成T？不能。完整上界必须包括instance transformation与answer recovery。

problem X
bipartite matching
→
known problem Y
maximum flow
→
solution to X
keep unit-flow left-right edges
Tflow(V + 2, E + 2V) + O(E + V)
A reduction is a complete transform-solve-lift contract, not merely a resemblance between two problems.

归约让一个成熟solver覆盖一族应用，也让问题按computational resources形成equivalence classes。若X有效归约到Y，记作 X≤RYX\le_R Y：直觉是“Y至少足以表达X”。符号方向总是从待解决的source problem指向被调用的target problem。

6.5.1 Transform-solve-lift归约合同

一个algorithmic reduction至少承担四项义务：

  1. Instance map：对每个valid X instance构造valid Y instance。
  2. Answer map：Y的返回值必须足以恢复X的合法答案。
  3. Correctness：YES/NO、objective value或witness关系被保留。
  4. Resource accounting：构造规模、构造时间、solver时间和恢复时间都有界。

若 ff 用时 Tf(n)T_f(n)，构造后的instance size是 m(n)m(n)，Y solver用时 TY(m)T_Y(m)，恢复用时 Tg(n,m)T_g(n,m)，则：

TX(n)≤Tf(n)+TY(m(n))+Tg(n,m(n))T_X(n) \le T_f(n)+T_Y(m(n))+T_g(n,m(n))

这条式子也解释为何“polynomial-time reduction”不仅要求map可计算，还要求output size不发生指数爆炸。若f显式产生 2n2^n 个constraints，即使Y有linear-time solver，也不能推出X是polynomial time。

function solveX(instanceX: X): AnswerX {
  const instanceY = reduceInstance(instanceX);
  const answerY = solveY(instanceY);
  const answerX = liftAnswer(instanceX, instanceY, answerY);
  assert(verifiesX(instanceX, answerX));
  return answerX;
}

6.5.2 Upper bounds：把X交给已知算法Y

上界（upper bounds）回答“至多需要多少资源”。要给X建立upper bound，应构造 X≤RYX\le_R Y，再调用Y的已知算法。

Official 6.5列出许多经典upper-bound reductions：

  • Bipartite matching reduces to maxflow：source-left、left-right、right-sink全设unit capacity。
  • PERT scheduling reduces to topological sort and DAG longest paths。
  • Nonnegative undirected shortest paths reduce to directed shortest paths：每条edge换成two directed arcs。
  • Euclidean MST reduces to Delaunay triangulation后再运行sparse-graph MST。
  • Maximum flow、assignment problem and zero-sum games都可reduce to linear programming。

以matching为例，原图 G=(L∪R,E)G=(L\cup R,E) 转换后增加s、t与 ∣L∣+∣R∣|L|+|R| 条边。若使用Ford-Fulkerson且每次unit augmentation增加matching size 1，最多augment min⁡(∣L∣,∣R∣)\min(|L|,|R|) 次；更强的Hopcroft-Karp直接在bipartite graph上达到 O(EV)O(E\sqrt V)。归约给出可用上界，但不保证是该special problem的最优算法。

归约可以复合

若 X≤RYX\le_R Y 且 Y≤RZY\le_R Z，可将两个maps串联得到 X≤RZX\le_R Z。但size growth也要复合：

mZ(n)=mY→Z(mX→Y(n))m_Z(n)=m_{Y\to Z}\bigl(m_{X\to Y}(n)\bigr)

例如activity scheduling先转DAG longest paths，再通过negating weights转DAG shortest paths；每一步都需保持acyclicity和path semantics。复合使抽象可复用，也会放大中间representation。

6.5.3 Lower bounds：从已知困难问题把硬度传入X

下界（lower bounds）回答“至少需要多少资源”。方向与upper-bound intuition容易混淆。

要证明X至少和已知困难问题H一样难，需要：

H≤RXH\le_R X

因为若X存在更快algorithm，H就能通过reduction同样变快，和H的known lower bound矛盾。

反方向 X≤RHX\le_R H 只表示可借H solver给X建立upper bound。归约箭头本身不带“快”或“慢”；结论取决于source、target以及已知事实放在哪一侧。

6.5.4 Element distinctness的Θ(N log N)

Element distinctness问N个totally ordered values中是否有duplicate。Sorting后扫描相邻元素给出O(N log N) upper bound。Comparison-tree lower bound则说明不能在该model中做得更快。

若输入all distinct，algorithm必须区分N!种strict order。Binary comparison tree至少有N!个对应leaves，所以depth：

h≥⌈log⁡2(N!)⌉=Θ(Nlog⁡N)h\ge \lceil\log_2(N!)\rceil =\Theta(N\log N)

更结构化的argument是：若某correct distinctness algorithm从未比较sorted order中相邻的 ai,ai+1a_i,a_{i+1}，把后者改成前者时所有comparison outcomes可保持不变，但answer应从distinct变为duplicate，矛盾。Algorithm执行的comparisons还可形成order constraints；对distinct input做topological order就恢复sorting，因此sorting lower bound被传入。

这个结论依赖computation model。Comparison tree、linear decision tree、algebraic decision tree允许的primitive不同；不能把一个model的lower bound无条件搬到hashing、bounded integers或word RAM。

6.5.5 Linear programming：用线性不等式表达选择

线性规划（linear programming）把连续variables、constraints与objective统一成一个optimization language。Official 6.5采用standard-form primal：

maximizecTxsubject toAx≤bx≥0\begin{aligned} \text{maximize}\quad & c^\mathsf{T}x\\ \text{subject to}\quad & Ax\le b\\ & x\ge 0 \end{aligned}

以图中例子为例：

max⁡3x1+2x2x1+x2≤42x1+x2≤5x1,x2≥0\begin{aligned} \max\quad & 3x_1+2x_2\\ x_1+x_2 &\le 4\\ 2x_1+x_2 &\le 5\\ x_1,x_2 &\ge 0 \end{aligned}

Feasible region是convex polyhedron。Linear objective的equal-value sets是parallel hyperplanes；沿improving direction移动，最后接触一个face。若bounded optimum存在，则至少一个basic feasible solution，也就是某vertex，达到optimum。

Linear programming比linear equations多了inequality和objective；它能表达resource allocation、flows、fractional matching、scheduling和game strategies。它不能直接要求variable取integer；integer linear programming是表达能力更强、复杂度也显著不同的问题。

6.5.6 General LP如何归约到standard form

Official bare-bones LinearProgramming.java处理 Ax≤b,x≥0Ax\le b, x\ge0 且 b≥0b\ge0，因此origin是初始basic feasible solution。General LP要先归一化：

  • aTx≥ba^\mathsf{T}x\ge b 乘以-1变成 −aTx≤−b-a^\mathsf{T}x\le-b。
  • Equality拆成two opposite inequalities。
  • Unrestricted variable xjx_j 换成 xj+−xj−x_j^+-x_j^-，两者nonnegative。
  • Minimization objective乘以-1转maximization。
  • Constraint加slack variable把inequality变equation。
// a_i x <= b_i becomes a_i x + s_i = b_i, s_i >= 0
for (int i = 0; i < m; i++) {
    tableau[i][n + i] = 1.0;
    tableau[i][m + n] = b[i];
}

若某 bib_i negative，origin不feasible，不能直接使用该实现的初始basis。完整simplex通常用Phase I寻找feasible basis，或给出infeasibility certificate；Phase II再优化original objective。

6.5.7 Simplex algorithm：沿basic feasible vertices换basis

单纯形算法（simplex algorithm）由George Dantzig提出，可看作Gaussian elimination扩展到inequalities。

一个tableau pivot包含：

  1. 选择positive reduced cost的entering column q。
  2. 对 aiq>0a_{iq}>0 的rows计算ratio bi/aiqb_i/a_{iq}，最小者是leaving row p。
  3. 以 apqa_{pq} 为pivot做Gauss-Jordan elimination。
  4. 更新basis，保持new right-hand side nonnegative。
int q = bland();          // entering variable
int p = minRatioRule(q);  // leaving variable
if (p == -1) throw new ArithmeticException("unbounded");
pivot(p, q);
basis[p] = q;

Ratio test为空表示存在improving ray，LP unbounded。若Phase I找不到feasible basis，则infeasible。Fundamental theorem总结为：LP若feasible则有basic feasible solution；若有finite optimum则有basic optimal solution；没有optimal solution时要么infeasible，要么unbounded。

Degeneracy、cycling与实际性能

Degenerate pivot可能objective不增加，因为多个constraints在same vertex tight。某些pivot rules可能循环；Bland's rule以最小index选entering/leaving variable可避免cycling。Floating arithmetic还会让“接近0”的coefficient改变ratio eligibility，所以production solver使用tolerance、scaling与稳定factorization。

Simplex worst case可走exponentially many pivots，不能把常见实践性能当polynomial guarantee。Official page同时强调其巨大工程影响以及实践中often少量pivots的现象；理论worst case与实际behavior必须分开陈述。

6.5.8 Primal、dual与strong duality

上面的primal有dual：

minimizebTysubject toATy≥cy≥0\begin{aligned} \text{minimize}\quad & b^\mathsf{T}y\\ \text{subject to}\quad & A^\mathsf{T}y\ge c\\ & y\ge 0 \end{aligned}

对任意primal feasible x和dual feasible y：

cTx≤yTAx≤yTb=bTyc^\mathsf{T}x \le y^\mathsf{T}Ax \le y^\mathsf{T}b =b^\mathsf{T}y

这是weak duality：任意dual value都是primal upper bound。若找到两边feasible且objective equal的pair，立即证明二者optimal。

Strong duality说明primal bounded and feasible时，dual也bounded and feasible，且optimal values equal。Simplex实际上同时维护primal basis与dual price information；reduced costs可解释为constraint shadow prices。

Complementary slackness进一步给出局部证书：

yi(bi−(Ax)i)=0,xj((ATy)j−cj)=0y_i\bigl(b_i-(Ax)_i\bigr)=0, \qquad x_j\bigl((A^\mathsf{T}y)_j-c_j\bigr)=0

Positive dual price意味着对应primal resource constraint tight；positive primal variable意味着对应dual inequality tight。Verifier只需matrix-vector products和nonnegativity checks，不必复跑simplex。

6.5.9 Maximum flow reduce to linear programming

对每条directed edge e建variable fef_e。Capacity是：

0≤fe≤ce0\le f_e\le c_e

每个internal vertex加入flow-conservation equality；objective最大化source net outflow。Equality可按standard-form rule拆成two inequalities，upper bound可通过slack表达。因此maximum flow是LP special case。

但专用maxflow算法利用network matrix结构，通常比general LP solver更简单、更快。Reduction证明expressiveness和upper bound，不意味着implementation必须采用generic simplex。

Maxflow-mincut theorem也可视作该LP的strong duality。Primal是flow，dual的0/1 vertex labels诱导s-t cut；equal objective的flow/cut pair是combinatorial primal-dual certificate。

6.5.10 Assignment problem and zero-sum games

Assignment problem

指派问题（assignment problem）可写为：

min⁡∑i,jcijxij∑jxij=1for every row i∑ixij=1for every column jxij≥0\begin{aligned} \min\quad & \sum_{i,j} c_{ij}x_{ij}\\ \sum_j x_{ij} &= 1 && \text{for every row }i\\ \sum_i x_{ij} &= 1 && \text{for every column }j\\ x_{ij} &\ge 0 \end{aligned}

LP没有显式写 xij∈{0,1}x_{ij}\in\{0,1\}，但Birkhoff-von Neumann theorem说明doubly stochastic polytope的extreme points正是permutation matrices，所以optimal basic solution可取integral。这个integrality来自constraint matrix结构，不是所有LP都有的性质。

Official section列出三条implementation路线：reduce to LP；Hungarian algorithm；以及successive shortest paths。当前AssignmentProblem.java的successive shortest paths worst-case为 O(n3log⁡n)O(n^3\log n)，dense variant为 O(n3)O(n^3)。专用结构再次带来比generic solver更清晰的边界。

Two-person zero-sum games

零和博弈（zero-sum games）用payoff matrix M表示。Row player选distribution p，column player选distribution q；expected payoff是：

pTMqp^\mathsf{T}Mq

若为每个matrix entry加constant K，optimal mixed strategies不变，game value增加K，因此可先让all entries positive。Official reduction把normalized probabilities改写成nonnegative variables，再由LP primal/dual求两个players策略；最后按variable sum归一化。

Minimax theorem：

max⁡pmin⁡qpTMq=min⁡qmax⁡ppTMq\max_p\min_q p^\mathsf{T}Mq = \min_q\max_p p^\mathsf{T}Mq

左边是row player能保证的value，右边是column player能限制的value。二者相等正是对应LP的strong duality。Pure strategy可能没有saddle point，但mixed strategy总能在finite zero-sum game中达到equilibrium。

6.5.11 Reductions的边界与常见失败

归约结论必须附带model和promise：

  • Undirected negative-weight shortest path不能简单换two directed arcs，否则每条negative edge立刻形成negative 2-cycle。
  • Fractional LP assignment依赖integrality theorem恢复discrete matching；一般integer requirement不能忽略。
  • Numeric LP solution需检查tolerance，不能用bit-exact equality判dual gap。
  • Reduction只保留指定objective或decision answer；它不自动保留all solutions、uniqueness或approximation ratio。
  • Oracle call count也属于成本；binary search reduction需乘以search iterations。
  • Randomized solver的error probability会随多次calls组合，需放大success probability。

一个可信reduction certificate应记录source/target sizes、construction invariants、target witness、lifted witness以及objective relation。Mutation test要覆盖missing edge、extra constraint、wrong sign、answer lift mismatch和overflow。

assert(target.vertices === source.vertices + 2);
assert(everyAllowedEdgeWasCopied(source, target));
assert(isIntegralUnitFlow(flow));
const matching = flowEdges
  .filter((edge) => edge.kind === "left-right" && edge.flow === 1)
  .map((edge) => [edge.from, edge.to]);
assert(isMatching(source, matching));
assert(matching.length === flow.value);

6.5.12 逐步运行路线

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“6.5 · Reductions”的两个最小情境间切换，再逐项选择正式概念。预测“T_A(n)=T_transform(n)+T_B(f(n))+T_decode(n)”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

6.5 · Reductions：对象、操作与不变量

把上界、下界、线性规划、单纯形、指派和零和博弈放进问题变换与答案恢复合同

选择最小情境

切换正式概念

输入合同操作证书algs4-6.5 · 先给前提，再执行，再验收当前概念：1/6
排序归约
把元素唯一性问题归约为排序后扫描相邻项
当前观察
reductions：排序加线性扫描给出上界，并明确比较模型成本
T_A(n)=T_transform(n)+T_B(f(n))+T_decode(n)

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

  • 归约：在实验 1 中指出对应状态，并写出一个通过条件。
  • 上界：在实验 2 中指出对应状态，并写出一个通过条件。
  • 下界：在实验 3 中指出对应状态，并写出一个通过条件。
  • 线性规划：在实验 1 中指出对应状态，并写出一个通过条件。
  • 单纯形算法：在实验 2 中指出对应状态，并写出一个通过条件。
  • 指派问题与零和博弈：在实验 3 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“T_A(n)=T_transform(n)+T_B(f(n))+T_decode(n)”不是孤立结论？

问题 3：故障恢复。 怎样证明“只展示一个样例映射就宣称完成归约，或把 A≤B 的方向反过来推导 A 的困难性”已经修复？

小结

  • Reductions由instance map、target solve、answer lift、correctness proof和resource accounting组成。
  • Upper bounds通过 X≤RYX\le_R Y 借用Y的algorithm；lower bounds通过 H≤RXH\le_R X 传递H的known hardness。
  • Element distinctness在comparison-tree model中有Θ(N log N) matching bounds。
  • Linear programming在linear constraints下优化linear objective，bounded optimum可在basic feasible solution取得。
  • Simplex algorithm通过pivot在adjacent bases之间移动，但要处理infeasible、unbounded、degeneracy与cycling。
  • Weak duality给upper bound，strong duality与zero gap提供optimality certificate。
  • Maximum flow是LP special case；专用network algorithm仍可利用更多结构。
  • Assignment LP因Birkhoff-von Neumann integrality得到permutation solution。
  • Two-person zero-sum games reduce to LP，minimax equality对应strong duality。
  • Reduction方向、computation model、numeric tolerance与representation growth都属于结论的一部分。

资料与写作方式声明

本章以Algorithms, Fourth Edition的合法公开试读核定可见范围，并以目录限定未公开部分，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…