北邮研究生课程《算法设计与分析》知识总结 - Part 2

1. 分支限界法 整体定位#

• 核心目标：求解全局最优解，不遍历全部可行解，通过预判提前剪枝，效率优于单纯回溯。
• 一句话区别：回溯法=不撞南墙不回头（深搜、找所有解）；分支限界法=见南墙提前绕路（广搜/优先搜、找最优解）。

2. 与回溯法对比#

3. 解空间树结点定义#

1. 活结点：已生成，但子结点未全部生成，仍有可扩展分支。
2. 扩展结点：当前正在生成子结点的活结点（算法处理核心）。
3. 死结点：无子分支、违反约束、无法继续扩展的结点。

4. 两大核心动作#

1. 分支：对扩展结点，拆分所有合法决策，生成若干子结点（解空间树分叉）。
2. 限界：计算分支理论最优值（限界值），若该分支理论最优都差于当前已找到的最优解，直接剪枝。

1. 队列式分支限界法（FIFO 分支限界）#

• 底层逻辑：广度优先搜索 BFS，先进先出，逐层遍历。
• 执行流程（简答/默写）：
  1. 初始化：定义约束、限界函数、根结点、空队列、全局最优解；
  2. 队列非空则循环，为空则算法结束；
  3. 取出队首结点作为扩展结点；
  4. 分支生成所有合法子结点，计算限界值；
  5. 剪枝：叶子结点更新最优解；非叶子结点，限界值有希望则入队，否则剪枝；
  6. 回到步骤2循环。

2. 优先队列式分支限界法（LC/最小代价法）#

• 底层逻辑：优先级优先，谁最可能得到最优解，先处理谁。
• 优先级规则：
  • 求最大值（背包、装载问题）：限界值越大，优先级越高；
  • 求最小值（最短路径、旅行商）：限界值越小，优先级越高。
• 与队列式两大核心区别：
  1. 容器：普通队列 → 优先队列（堆）；
  2. 取结点：取队首 → 取优先级最高结点；
• 独有优化（考点）：取出结点后，若其限界值 ≤ 当前最优解，直接提前终止算法（队列所有结点都无潜力）。

1. 三步设计法（简答题）#

1. 明确优化目标
   • 求最大值（最大价值/重量）：设计上界（分支理论最大收益）；
   • 求最小值（最短路径/最小代价）：设计下界（分支理论最小代价）。
2. 安全性原则（绝对不能出错，考点核心）
   • 最大值问题：理论上界 ≥ 分支实际最大收益（不能误剪含最优解的分支）；
   • 最小值问题：理论下界 ≤ 分支实际最小代价；

   违规后果：剪掉最优分支，算法结果错误。

3. 平衡精度与计算量：限界值越接近真实值，剪枝越强；同时保证计算简单。

2. 通用剪枝规则#

• 最大值问题：上界 ≤ 当前最优解 → 剪枝；
• 最小值问题：下界 ≥ 当前最优解 → 剪枝。

题型1：0-1背包问题（最常考计算题）#

1. 问题特征：物品选/不选，不可分割，约束为背包容量，目标最大化总价值。
2. 解空间树：子集树，每个结点2个分支。
3. 限界函数（上界）（必背计算方式）
   • 预处理：物品按单位重量价值从高到低排序；
   • 计算：剩余背包容量 → 允许物品分割，依次装剩余物品，得到理论最大价值（上界）。
4. 解题核心步骤：初始化→取最高优先级结点→分支（装/不装）→计算上界→剪枝/入队→更新最优解→提前终止。

题型2：装载问题（0-1背包变种）#

1. 问题转化：双船装载 → 单船最大化装载重量（等价0-1背包，价值=重量）。
2. 约束：集装箱不可拆分，第一艘船载重限制。
3. 限界函数（上界）
   • 预处理剩余重量数组remainW[i]：第i个及之后所有集装箱总重量；
   • 上界 = 当前已装重量 + remainW[i]。
4. 判定规则：第一艘船装满即达到理论最优，可直接终止。

题型3：子集和问题#

1. 问题：从数组选子集，和等于目标值，元素不可重复选取。
2. 解空间树：子集树。
3. 限界函数（上下界结合）
   • 预处理剩余和数组remainSum[i]；
   • 下界=当前和，上界=当前和+remainSum[i]；
   • 剪枝：下界>目标值 或 上界<目标值，直接剪枝。
4. 技巧：数组排序可大幅提升剪枝效率，找到解立即终止。

题型4：旅行商问题（TSP，最小值问题代表）#

1. 问题特征：遍历所有城市一次，起点终点相同，求最短回路。
2. 解空间树：排列树，叶子数为 $(n-1)!$。
3. 限界函数（下界）（最小值专用）
   • 预处理：每个城市最小出边；
   • 下界 = 已走路程 + (剩余城市最小出边和 + 返回起点最小距离) / 2。
4. 特点：最坏复杂度 $O(n!)$，n较大时仅能依靠限界函数剪枝。

1. 随机化算法定义#

随机化算法可看作带两组输入的确定性算法：

• 常规问题输入 $x$
• 随机比特串 $r$（随机数生成，多项式长度） 同一输入$x$，输出随随机串$r$变化；概率特性仅由$r$决定。

2. 两大核心分类#

（1）拉斯维加斯（Las Vegas）算法

核心特点：零错误，运行时间随机

1. 正确性：输出100%正确，$\Pr[A(x)=f(x)]=1$
2. 运行时间：随机变量，期望运行时间有界
3. 优化方式：多次运行可降低最坏耗时
4. 典型例题：随机化快速排序、随机化快速选择

（2）蒙特卡洛（Monte Carlo）算法

核心特点：运行时间确定，结果存在有界错误

1. 错误率：错误概率严格小于给定阈值$\epsilon$，$\Pr[A(x) \neq f(x)]<\epsilon$
2. 运行时间：固定，不会超时
3. 优化方式：多次执行，错误概率指数级下降
4. 典型例题：蒙特卡洛求圆周率π

考试必考题：区分两种随机算法的特性、举例。

3. 随机数生成#

计算机使用两类随机数：

1. 伪随机数（PRNG）

   • 本质：确定性函数，依靠种子生成序列，可复现结果
   • 常用算法：线性同余LCG、梅森旋转MT19937、Xorshift
   • 优缺点：速度快、可复现；非真随机，不适用高安全密码场景
   • 工具：Python random 库，random.seed() 设置种子

2. 真随机数

   • 来源：物理随机现象（鼠标、键盘、CPU温度、放射性衰变、量子效应）
   • 优缺点：真正随机、安全性高；生成慢、成本高
   • 适用：密码学、金融等高安全场景

案例1：随机化快速排序（拉斯维加斯算法）#

1. 改进思路

确定性快排缺陷：固定选首/尾元素为主元，有序数组下复杂度退化至 $O(n^2)$。 核心优化：每次在当前子数组中随机选主元，打破最坏输入场景。

2. 执行流程

1. 随机选取区间内主元下标，将主元交换到区间最右侧；
2. 执行标准快排分区；
3. 递归排序左右子区间。

3. 复杂度分析

• 期望时间复杂度：$\boldsymbol{O(n\log n)}$（无论输入形态，稳定）
• 最坏时间复杂度：$O(n^2)$，发生概率极低，几乎可忽略
• 空间复杂度：期望 $O(\log n)$（递归栈），最坏 $O(n)$（概率极低）
• 实际性能：常数因子小，工程中最快排序之一。

4. 代码要点

核心函数：random_select（随机选主元）、partition（分区，与普通快排一致）、递归主体。

案例2：随机化快速选择（拉斯维加斯算法）#

1. 问题

在无序数组中找第k小元素，目标：比排序($O(n\log n)$)更快。

2. 算法思想

基于随机主元+分治，不完整排序，仅递归处理目标元素所在分支：

1. 随机选主元、分区；
2. 设左区间（≤主元）元素个数为$m$：
   • $k = m$：主元就是第k小元素，直接返回；
   • $k < m$：目标在左区间，递归左半；
   • $k > m$：目标在右区间，递归右半，查找第 $k-m-1$ 小。

3. 复杂度

• 期望时间复杂度：$\boldsymbol{O(n)}$（线性时间，核心优势）
• 最坏时间复杂度：$O(n^2)$（低概率）
• 空间复杂度：$O(\log n)$（递归栈）

案例3：蒙特卡洛法求π#

1. 数学原理（简答/计算题）

几何概率模型：

• 边长为2的正方形，面积 $S_{正}=4$；内部单位圆半径$r=1$，面积 $S_{圆}=\pi$
• 概率关系：$\dfrac{\text{圆内点数}M}{\text{总投点数}N} \approx \dfrac{\pi}{4}$
• 推导公式：$\boldsymbol{\pi \approx 4 \times \dfrac{M}{N}}$

2. 执行步骤

1. 生成 $N$ 组随机坐标 $(x,y)$，$x,y\in[-1,1]$；
2. 判断点是否在单位圆内：$x^2+y^2 \le 1$，统计圆内点数$M$；
3. 代入公式估算$\pi$。

3. 复杂度与精度

• 时间复杂度：$\boldsymbol{O(N)}$（与投点数量线性相关）
• 空间复杂度：$\boldsymbol{O(1)}$（常数空间）
• 精度规律：误差与 $\dfrac{1}{\sqrt{N}}$ 成正比；误差减半，投点数需扩大4倍。

1. 遗传算法定义#

遗传算法是模拟生物自然选择、遗传变异的随机优化算法，将解编码为染色体，通过选择、交叉、变异三大核心操作迭代寻优。

2. 生物学 ↔ 算法概念映射#

1. 选择操作（优胜劣汰）#

作用：优先选择适应度高的个体进入交配池，传递优良基因。

三种经典实现：

1. 轮盘赌选择（公式必考）

   个体$i$被选中概率：$\displaystyle p_i=\frac{f_i}{\sum_{j=1}^N f_j}$

   特点：概率与适应度成正比。

2. 锦标赛选择（工程常用）

   随机选$k$个个体，取适应度最高者；鲁棒性强。

3. 精英保留策略（必背）

   将当代最优的若干个体直接复制到下一代，防止最优解丢失。

2. 交叉操作（基因重组）#

作用：组合父代优良基因，产生新个体。

• 二进制编码：单点交叉、多点交叉、均匀交叉
• 排列编码（TSP问题）：顺序交叉（保证城市不重复，合法路径）

3. 变异操作（基因突变）#

作用：增加种群多样性，避免算法陷入局部最优。

• 二进制编码：位翻转变异（0↔1）
• 实数编码：均匀变异、高斯变异
• 排列编码（TSP）：交换变异（随机交换两个基因位置）

案例1：0-1背包问题（二进制编码）#

1. 算法设计

1. 编码：二进制串，长度=物品数；位=1表示选该物品，0表示不选。
2. 适应度函数
   • 总重量 ≤ 背包承重：适应度 = 物品总价值
   • 总重量 > 背包承重：适应度 = 0（惩罚非法解）
3. 操作配置：锦标赛选择、单点交叉、位翻转变异、精英保留。

2. 复杂度分析（计算题考点）

• 单代时间复杂度：$O(N \cdot n)$ （$N$种群规模，$n$物品数）
• 总时间复杂度：$\boldsymbol{O(T \cdot N \cdot n)}$（$T$迭代次数）
• 空间复杂度：$\boldsymbol{O(N \cdot n)}$
• 对比优势：遗传算法复杂度和背包载重$W$无关，适合超大载重场景（动态规划$O(nW)$在$W$极大时失效）。

案例2：旅行商问题 TSP（排列编码）#

1. 算法设计

1. 编码：整数排列，每个数字代表城市，每个城市仅出现一次。
2. 适应度函数：总路程倒数（最小化问题转化为最大化适应度，路程越短，适应度越高）。
3. 专属操作：顺序交叉、交换变异（保证排列合法，无重复城市）。

2. 复杂度

时间、空间复杂度和0-1背包一致：$O(T \cdot N \cdot n)$、$O(N \cdot n)$。

1. 算法来源与本质#

1. 灵感来源：冶金学金属退火——高温加热、缓慢冷却，原子趋于能量最低的稳定晶体状态。
2. 算法定义：基于蒙特卡洛迭代的随机化全局优化算法；单点迭代搜索，允许以一定概率接受较差解，从而跳出局部最优，最终逼近全局最优。
3. 应用场景：旅行商TSP、0-1背包、车间调度、芯片设计、神经网络训练等组合优化问题。

2. 模拟退火 VS 遗传算法#

通俗记忆：遗传算法=一群人找路；模拟退火=一个人摸索，偶尔走弯路找全局最优。

1. 通用算法步骤#

设解空间$S$，目标函数$f$（默认求最小值；求最大值可对目标函数取负）

1. 初始化：初始温度$T=T_0$、初始解$x_0$、最优解$x_{best}=x_0$；
2. 等温迭代（马尔可夫链，长度$L$）：循环$L$次
   • 对当前解随机扰动，生成新解$x'$；
   • 计算目标函数差值 $\Delta f = f(x')-f(x)$；
   • Metropolis准则判断是否接受新解；
   • 若新解更优，更新全局最优解$x_{best}$；
3. 降温：按降温策略更新温度$T$；
4. 终止判断：温度低于终止温度$T_f$或达到最大迭代，停止；
5. 输出全局最优解$x_{best}$。

2. 三大核心操作#

（1）状态产生函数（生成新解）

对当前解做随机扰动，不同编码对应不同方式：

• 二进制编码（如0-1背包）：位翻转
• 排列编码（如TSP旅行商）：交换、插入
• 实数编码：高斯/均匀随机扰动

（2）状态接受函数：Metropolis准则

（3）温度更新函数（降温策略）

三种策略，区分特点与适用场景：

1. 指数降温（最常用）：$T_{k+1}=\alpha \cdot T_k$，降温系数 $\alpha \in [0.85,0.95]$

   特点：兼顾效率与收敛，工程首选。

2. 线性降温：$T_{k+1}=T_k-\beta$

   特点：降温快，易陷入局部最优。

3. 对数降温：$T_{k+1}=T_0/\log(1+k)$

   特点：理论保证全局收敛，但降温极慢，几乎不实际使用。

3. 核心参数#

• $T_0$：初始高温；$T_f$：终止温度；
• $L$：马尔可夫链长度（单温度下迭代次数）；
• $\alpha$：降温系数。

案例1：0-1 背包问题#

1. 问题转化

原目标：最大化总价值 → 模拟退火求最小值，因此目标函数取负。

2. 约束处理：惩罚函数

对超重的不可行解施加惩罚：

惩罚系数取大数，保证不可行解函数值远大于可行解。

3. 编码与新解生成

• 编码：二进制串，1选物品，0不选；
• 扰动方式：随机翻转一位二进制位。

4. 复杂度

• 时间复杂度：$\boldsymbol{O(T \times L \times n)}$

  $T$：温度迭代次数，$L$：马尔可夫链长度，$n$：物品数量

• 空间复杂度：$\boldsymbol{O(n)}$（仅存储解向量）

案例2：旅行商问题 TSP#

1. 编码与新解生成

• 编码：城市排列（每个城市出现且仅出现一次）；
• 扰动方式：随机交换两个位置的城市，保证解合法。

2. 目标函数

路线总路程，直接求最小值，无需取负。

3. 解题流程核心逻辑

随机初始路线 → 交换生成新路线 → Metropolis准则判接受 → 降温迭代 → 输出最短路径。