守株阁

29篇区分了求解、验证和困难性。遇到难以精确求解的优化问题，一种选择是保留可行性，允许目标值偏离最优，但为偏离程度给出对所有合法输入成立的保证。 对于目标非负的最小化问题，记算法返回值为ALG、最优值为OPT。ρ近似要求ALG≤ρOPT，同时算法在输入编码长度的多项式时间内结束。直接写不等式可以覆盖OPT=0；写ALG/OPT时还得处理分母为零。下面两个保证是确定性的最坏情况保证，不是随机输入上的平均表现，也不是运行时间的摊还界。 点覆盖中的一组不相交边 输入是n个顶点、m条边的无向简单图。点覆盖是一组顶点C，使每条边至少有一个端点属于C；无权版本要求最小化|C|。这与27篇的匹配不同：匹配选择边，要求边不共享端点；覆盖选择顶点，要求所有边得到覆盖。 顺序扫描边。如果当前边的两个端点都没有被选过，把这条边加入M，并把两个端点加入C。扫描结束，输出C。 M是一组匹配，因为加入新边时两端都未使用。它还是极大匹配：若有一条边与M完全不相交，这条边在被扫描时两端也必定未使用，就应该被加入，矛盾。极大只表示不能继续加边，不表示边数最大；不需要运行27篇的最大匹配算法，也不要求图是二分图。 ...

一段程序跑得慢，只能说明这段程序在当前输入上的表现，不能证明问题本身必须如此。计算复杂性需要先固定问题、编码与计算模型，再说明算法能做到什么，或者一个已知困难问题怎样转换成它。 本篇用3SAT到CLIQUE的具体转换说明归约方向和双向证明，再用0/1背包解释为什么O(nW)的动态规划不一定是关于输入长度的多项式算法。27篇的二分图匹配依然可以高效求解；不能因为另一个图问题困难，就把困难性迁移到所有图算法。 P与NP先讨论判定问题 判定问题对每个合法输入只回答是或否。例如，CLIQUE问“给定无向简单图G和整数k，是否存在至少k个两两相邻的顶点”；优化版本则要求找出最大团。这两个问题有关，但定义类别时不能省略判定门槛。 把完整输入编码成有限二进制串，长度记为L。P包含能由确定性算法在L的多项式时间内判定的问题。NP用证书刻画判定问题。是实例存在长度不超过某个多项式p(L)的证书，确定性验证器能在多项式时间内接受它；否实例不存在任何能被接受的合法证书。 对CLIQUE，证书是k个不同顶点的编号。检查编号范围、不同性以及每对之间有边，就能验证。使用邻接矩阵时需O(k²)次查边，建矩阵或...

26篇用流提供一个可行值，用割限制所有流的最大值；27篇用匹配和点覆盖形成同样大小的两份证书。线性规划把这种“可行方案与界相遇”的结构推广到线性不等式：原问题给出方案，对偶问题给出界，两边可行且目标相等，就足以证明最优。 本篇只核对小型问题的精确证书，不实现通用线性规划求解器。求出候选解与验证候选解是两个任务；有一个通过检查的证书，并不意味着已经实现了搜索它的算法。 从约束到原问题 考虑非负变量x、y，最大化3x+2y，约束为 x+y≤4,2x+y≤5,x,y≥0.x+y\le 4,\qquad 2x+y\le 5,\qquad x,y\ge 0. x+y≤4,2x+y≤5,x,y≥0. 输入包括约束系数、右端常数、目标系数，以及待核对的原始和对偶候选。输出是候选是否可行、各自目标值和二者差距。变量在本节允许取实数，没有整数要求。 一般形式写为最大化cᵀx，满足Ax≤b、x≥0。设A有m行n列，m是约束条数，n是变量数。向量不等式逐项成立，转置只是交换行列，使Aᵀu按变量汇总各条约束的系数。 选择点(x,y)=(1,3)，两条约束左侧分别为4和5，目标值为9。它证明最优值至少为9...

把候选安排逐个加入日程时，先选中的一对可能妨碍后续分配。若每位人员最多接受一项任务，每项任务也最多分配一人，这个问题可以表示成二分图匹配。提高匹配大小有时需要撤销一对已有安排，换成两对新安排；26篇残量网络中的撤销操作正好表达这种调整。 本篇先证明匹配与整数流的对应，再从终止时的残量可达集合构造最小点覆盖。匹配是可行安排，点覆盖则限制任何安排最多能有多少对，两者大小相等时形成可核对的最优性证书。 两侧顶点不能混成一个编号域 输入左侧a个顶点、右侧b个顶点，以及m条候选边(l,r)。左侧编号0到a−1，右侧编号0到b−1，即使数字相同也表示不同对象。边保留输入ID，允许重复候选，但匹配不能重复使用任一端点。 输出一组匹配边ID，以及分别位于左右两侧的点覆盖集合。点覆盖要求每条输入边至少一个端点被选中；匹配则要求所选边两两不共享端点。这两个“覆盖”和“配对”条件不同，不能只比较返回集合的大小。 允许一侧为空、没有边、存在孤立点。不要求把所有人员或任务配满；目标是最大化匹配条数。加入边权、人员容量或任务优先级以后，需要重新说明目标和归约，不能直接沿用本篇最大基数匹配的结论。 单位容量强...

沿一条通路增加流量，很容易得到比原来更好的方案。困难在于证明何时不能继续改善，以及早先选错的通路能否撤销。最大流的残量网络同时处理这两件事：正向残量表示还能增加多少，反向残量表示已有流量能撤回多少。 本篇固定使用Edmonds–Karp算法，每次用BFS找边数最少的增广路。它属于Ford-Fulkerson增广方法，但不能把任意选路规则的执行次数直接当作它的复杂度。最终输出除了流量，还包括一个容量相等的割，让最优性可以独立核对。 流的接口与可行性 输入n≥2个顶点、m条有向边、不同的源点s与汇点t。每条边有非负整数容量c，保留独立输入ID，允许平行边、相反方向的原始边和自环。输出每条原边的流f、总流值以及一个源侧顶点集合S。 可行流必须满足0≤f(e)≤c(e)。除s、t外，每个顶点的流入和流出相等。总流值取s的净流出，即流出减流入，而不是仅把源点所有出边相加；它同时等于t的净流入。 自环对净流量的贡献为零，教学实现不会利用它增广。零流总是可行，所以无需先解决一个寻找初始可行解的子问题。本篇没有下界流、多源供需或最小费用约束。 一条原边需要两个残量方向 原边u→v的当前流量为f时...

从起点到一个顶点的当前最好路径，未必已经是最短路径。Dijkstra能永久确定当前距离最小的顶点，是因为后面的非负边不能把尚未发现的路径变得更短。允许负边以后，这项推理失效，优先队列本身无法补回缺失的前提。 本篇在同一个有向图接口上比较Dijkstra与Bellman–Ford，再用势函数说明怎样在保留路径比较的条件下消除负边。09篇的索引堆继续用于减键，22篇的状态依赖思想用于理解有边数限制的路径。 距离与路径证据 输入n≥1个顶点、m条有向整数权边以及起点s。顶点编号0到n−1，平行边和自环保留独立输入ID。输出每个顶点的距离和前驱边ID；不可达顶点距离为None，不能用一个可能被真实路径超过的有限大整数冒充无穷。 Dijkstra要求全图边权非负，发现负权就拒绝，即使负边位于当前起点不可达的分量。Bellman–Ford允许负边，但只在存在从s可达的负环时报告异常，并给出一个可核对的环。异常时不把尚在变化的距离数组作为最终最短距离交付。 没有可达负环时，任意最短路都可去掉非负环，得到至多n−1条边的简单路径。若某个负环可达，能通过它到达的顶点可以反复绕环降低路径权重，因此不...

22篇的带权区间调度不能总选最早结束的区间。Kruskal却可以反复选当前最轻、且不形成环的边，最终得到最小生成森林。区别不在于两个规则哪一个“更自然”，而在于是否能证明局部选择仍属于某个全局最优解。 本篇先给出割与交换证明，再把无环边集合抽象成图拟阵。教学实现复用10篇并查集，检查的是无环约束；优化目标的正确性需要另外证明。 无向多重图的目标 输入n个顶点，编号0到n−1，以及m条无向边(u,v,weight)。权重为整数，允许负权、相等权、平行边和自环；每个输入位置是独立边ID。输出总权重与选中的边ID。 若原图连通，目标是最小权生成树。若有c个连通分量，目标是在每个原分量内选生成树，合计n−c条边；孤立点也算分量。空图返回总权重0和空边集。 这不是在任意子图中最小化权重。允许任意森林时可以不连接某些顶点；允许任意连接子图且存在负权环时，加入额外边反而可能降低总权重。生成森林同时要求连接原分量与无环，两个条件都不能省略。 Kruskal只负责维持森林 将边按(weight,id)递增排序，开始时选边集A为空。扫描到边(u,v)时，用并查集判断两端是否已经连通：不连通就选入并合...

22篇先证明状态与转移正确，再计算每个状态。优化动态规划时，这个顺序仍然重要：减少内存不能丢掉未来依赖，缩小候选集合不能排除真正最优决策。观察几行最优下标递增，只能形成猜测，不能授权程序跳过剩余候选。 本篇把一个非负数组切成固定数量的非空连续段，最小化各段元素和的平方之和。先建立朴素递推，再证明特定代价满足的四边形不等式，最后用决策单调性减少搜索。 状态包含用了多少段 输入n个非负整数a，以及段数g。输出最小代价和g个半开区间，它们按顺序无缝覆盖[0,n)，每段非空。n=0、g=0单独返回代价0与空方案；其余要求1≤g≤n。 令S_i为前i项之和，S_0=0，区间[k,i)代价W(k,i)=(S_i−S_k)²。沿用11篇前缀和的半开语义，一次区间和只需相减；不需要再建一个区间求和数据结构。 D_t[i]表示前i项恰分成t段的最小代价。D_0[0]=0，其余零段状态不可行；对i≥t： Dt[i]=min⁡t−1≤k<i{Dt−1[k]+W(k,i)}.D_t[i]=\min_{t-1\le k<i}\{D_{t-1}[k]+W(k,i)\}. Dt​[i]=t−1≤k...

一组预约各占一个时间区间并带有收益。选出互不冲突的预约，使总收益最大。最早结束的预约为后续留下较多时间，但它可能收益很小；直接套用无权区间调度的贪心规则会丢掉更好的带权方案。 例如[0,1)和[1,2)的收益各为2，[0,2)的收益为5。最早结束的贪心可以选前两个，收益4；只选长区间却有5。动态规划需要保存的是尚未选择最后一个区间时，各个前缀能达到的最好收益。 输入、兼容与恢复结果 输入n个三元组(start,end,weight)，端点和收益为整数，要求start<end。区间采用半开语义，相接端点兼容：一个区间的end等于下一个的start时可以同时选择。收益可以为负或0，空方案始终合法。 每个输入位置是独立ID，相同区间也保留不同ID；它们有正长度且彼此重叠，不能同时选择。输出包括最优收益和一组实际选择的ID，ID按算法的结束时间顺序返回。目标并未要求所有最优解，也不要求ID字典序最小。 教学接口对start≥end抛出ValueError。特别是零长度区间没有直接混入常规区间证明：空区间怎样参与收益和兼容，需要另外约定，不能靠排序偶然得到结果。 为什么按结束时间建立...

两个长度接近n的系数数组做朴素卷积，需要约n²次乘法。把其中一个数组机械地切成两半，仍然需要与另一个数组的每个元素相乘，总工作不会减少。有效分治需要找到可以共享的中间结果，而不只是增加递归调用。 FFT利用单位根的成对结构共享多项式求值。本篇从卷积开始推导这项结构，再用选择问题对照另一种分治：不是加速合并，而是只递归进入包含目标的一边。两者的递推不能混写。 卷积等价于多项式乘法 输入实数系数数组a、b，长度分别为p、q；输出c长度p+q−1，其中 ck=∑i+j=kaibj.c_k=\sum_{i+j=k}a_i b_j. ck​=i+j=k∑​ai​bj​. 把A(x)=Σa_i x^i、B(x)=Σb_j x^j相乘，c正是乘积系数。空数组在教学接口中代表没有系数，任意一方为空时返回空结果；这个约定单独处理，避免长度公式产生负数。 朴素算法对每对(i,j)把a_i b_j加到c[i+j]。在单位成本实数运算模型下，乘法p q次，累加同阶。这是可复跑的独立参照，也直接体现正确性：每个应进入第k项的乘积恰好被访问一次。 另一种表示是多项式在足够多不同点上的值。逐点相乘很便宜；困难...