算法设计技术

蛮力法

蛮力法直接枚举候选解并逐一验证约束。它通常不快，但思路清楚、实现容易检查，适合规模较小的问题，也常用来给复杂算法做正确性基准。

课件中的例子包括朴素串匹配、顺序查找、枚举最大公因子和“百元买百鸡”。枚举不等于完全不动脑：先利用价格、总数、奇偶性等简单约束收紧循环范围，已知两个变量后直接算出第三个，都能明显减少无效候选。

分治、减治与变治

分治法与主定理

分治包含三个步骤：

1. 把原问题划分成若干规模更小的同类子问题；
2. 递归求解，规模足够小时直接处理；
3. 合并各子问题的答案。

若递推式为

常用主定理给出

归并排序、快速排序、二叉树遍历都体现了分治思想。正确性通常按问题规模归纳：假设递归调用已正确解决更小实例，再证明划分和合并没有遗漏、重复或破坏答案。

Karatsuba 大整数乘法

把两个 \(n\) 位整数分成高、低两半：

普通展开需要四次半长乘法。改为计算

即可用三次乘法得到

所以

这是“用较便宜的加法换较少的乘法”。整数较短时，递归和临时空间的常数开销反而可能更大。

Strassen 矩阵乘法

普通分块矩阵乘法需要八次子矩阵乘法。Strassen 用七次：

组合为

于是

它减少乘法却增加了加减、临时矩阵和数值误差，通常只在矩阵足够大时使用，并在小块上切回普通乘法。

最近点对

平面最近点对的蛮力法要比较 \(O(n^2)\) 对。分治法先按横坐标分成两半，分别得到最近距离 \(\delta_L,\delta_R\)，再令 \(\delta=\min(\delta_L,\delta_R)\)。跨越中线的更优点对只可能落在宽度 \(2\delta\) 的条带中。

若同时维护按纵坐标排序的点，条带中每个点只需检查后面常数个邻点，合并为 \(O(n)\)，所以总时间 \(O(n\log n)\)。若每一层都重新排序条带，则会多出一个对数因子。

减治与变治

减治法每次只求一个更小的子问题：

• 选择排序每轮固定一个元素，规模减一；
• 折半查找每轮保留一半，规模减常数因子；
• 欧几里得算法把 \((m,n)\) 变为 \((n,m\bmod n)\)，减少量随数据而变；
• 天平找轻球时分成三组，一次称量后只保留约三分之一。

黄金分割搜索也可看作减治：每轮把可信区间缩短为原来的约 \(0.618\)。

变治法把问题转成已有工具更容易处理的形式，规模不一定变小。例如先排序再折半查找、高斯消去把一般方程组化成上三角系统、LU 把多个右端项化成三角求解。转换本身也有代价，只查一次时“先排序再折半”未必比顺序查找划算。FFT 把 DFT 按偶、奇下标拆成子问题，属于分治法而不是这里的变治。

贪心算法

贪心算法逐步扩展部分解，每一步选择当前最好的可行决策，并且不回退。它要得到全局最优，至少需要最优子结构和贪心选择性质；“每一步看起来最好”本身不是证明。

课程安排问题中，每次选择结束最早、且不与已选课程冲突的课程。交换论证可以说明：任取一个最优安排，把其第一门换成结束更早的贪心选择，不会减少后面可安排的数量，因此可递归得到最优解。

找零钱的“每次取最大面值”只对某些币制成立。0/1 背包按价值最大、重量最小或单位价值最大选择，都能构造反例。一个规则在某个样例中成功，不能代替一般证明。

Prim、Kruskal、Dijkstra 和 Huffman 都是本课中的贪心算法：前两者依靠割性质，Dijkstra 依靠非负边，Huffman 则反复合并最低频的两个符号。最速下降每次选局部最陡方向，却通常不保证全局最优；在适当的光滑性和线搜索条件下，一般也只是趋向驻点。

动态规划

动态规划适合具备以下结构的问题：

• 最优子结构：最优解包含子问题的最优解；
• 重叠子问题：不同求解路径会反复遇到同一状态；
• 无后效性：给定当前状态后，未来只依赖当前状态和后续决策。

一般步骤是：划分阶段，定义状态，写出转移方程，确定计算顺序并填表，最后根据决策记录反向恢复具体方案。分治通常独立地求子问题，动态规划则会保存并复用重叠状态；贪心只保留当前选择，动态规划会保留多个仍可能通向最优解的状态。

0/1 背包

第 \(i\) 件物品重量 \(w_i\)、价值 \(v_i\)，容量为 \(W\)。令 \(OPT(i,w)\) 表示只用前 \(i\) 件物品、容量为 \(w\) 时的最大价值：

边界是 \(OPT(0,w)=0\)。二维表需 \(O(nW)\) 时间和空间；只求最优值时，容量从大到小更新可把空间压到 \(O(W)\)。若正序更新，同一件物品会在本轮被重复使用，问题就变成完全背包。

\(O(nW)\) 关于数值 \(W\) 是多项式，但 \(W\) 的二进制输入长度只有 \(O(\log W)\)，所以这是伪多项式时间。若要恢复选择方案，需要保存决策，或从二维表反向比较。

Floyd 与 Viterbi

Floyd 的状态是“只允许前 \(k\) 个顶点作中间点时的最短路”，前文已给出转移式。最短路要么不经过 \(k\)，要么在 \(k\) 处拆成两段，这一分类保证没有遗漏。

Viterbi 算法在隐状态模型中寻找最可能产生观测序列的状态路径。设 \(\delta_t(l)\) 是处理到时刻 \(t\)、终止于状态 \(l\) 的最大路径概率，则

\(e_l(o_t)\) 是发射概率，\(a_{kl}\) 是转移概率。每个状态还要记录取得最大值的前驱，最后从终点回溯整条路径。状态数为 \(S\)、序列长度为 \(T\) 时，时间为 \(O(TS^2)\)。通信解码、语音识别和 DNA 序列分析都用到这一结构。

最长公共子序列、diff 和旅行安排也可用相同的“状态 + 转移 + 回溯”框架描述。

解空间搜索

组合问题的候选解常能组织成树：每一层作一次决策，叶子代表完整方案。全排列树有 \(n!\) 个叶子；把递归改成显式栈只改变遍历方式，不会消除问题固有的指数或阶乘规模。

回溯法

回溯按深度优先顺序构造解；一旦部分解违反约束，或已经不可能扩展为目标解，就撤销选择：

Search(state):
    if state is complete:
        record state
        return
    for choice in candidates(state):
        if choice is feasible:
            make choice
            Search(next state)
            undo choice

八皇后按行放置可把状态记成每行的列号 \(c_r\)。加入第 \(s\) 行时，只需检查

列冲突或对角线冲突一出现就停止向下搜索。正数子集和还可在当前和超过目标，或“当前和 + 全部剩余元素”仍达不到目标时剪枝。剪枝能大幅改善很多实例，但最坏情况仍可能是 \(O(2^n)\)。

分配问题中，若当前成本已经不小于已知最好方案，也可以回退；先尝试便宜的分支，往往能更早得到较好的上界。

分支定界法

分支定界为每个部分解计算一个乐观边界，并优先扩展最有希望的结点。最小化问题中，若某结点的下界已经不小于当前最好完整解，它的整个子树都可舍弃。

分配问题的简单下界是

旅行商问题则可用每个顶点两条最短关联边的总和除以 \(2\) 作为初始下界，并随强制选边更新。

回溯常用 DFS，分支定界常用按下界排序的优先队列。后者不等同于普通 BFS，效率取决于结点扩展顺序和边界是否够紧；两者最坏都可能遍历指数级搜索树。

随机算法

计算机通常产生伪随机序列，例如线性同余发生器

参数和种子影响周期与分布。讨论随机算法时要说清楚保证属于“期望复杂度”“成功概率”还是“必然正确”。

Sherwood 算法用随机化打散输入与最坏过程的固定对应关系，但不改变答案的正确性。随机快速排序每次随机选枢轴，期望 \(O(n\log n)\)，某次运行仍可能达到 \(O(n^2)\)。

Las Vegas 算法可能本次失败或运行时间不定，但只要输出答案，答案一定正确。例如先随机放置若干皇后，再用回溯完成；冲突过多就重新开始。

Monte Carlo 算法总会返回结果，但结果可能是近似值或有小概率出错。随机点估计积分、圆周率都属于这一类。主元素若出现次数超过一半，随机抽中它的概率至少为 \(1/2\)；抽中后再完整扫描验证。独立重复 \(k\) 次仍未抽中的概率至多为 \(2^{-k}\)。

Fermat 素性测试先单独处理 \(n<2\)、\(n=2\) 和大于 \(2\) 的偶数。对剩下的奇数 \(n>2\)，选取满足 \(1<a<n\) 且 \(\gcd(a,n)=1\) 的底数，检查素数必须满足的条件

不满足时可以确定 \(n\) 为合数，满足却不能证明它是素数，因为伪素数和 Carmichael 数会通过测试。模拟退火、遗传算法和粒子群则是在优化过程中加入随机因素，以争取跳出局部最优。

随机算法可概括为：

评论