第五部分：应对不确定性与大规模问题

本部分聚焦于处理动态输入、超大规模搜索空间及实际工程中的复杂优化问题。

5.1 在线算法 (Online Algorithms)

5.1.1 在线算法

离线和在线

离线算法 (Offline Algorithm)：在计算开始前，问题的所有输入数据（整个序列）均已知。算法可以统筹全局做出最优决策。 在线算法 (Online Algorithm)：输入是以序列形式逐步到来的 (\(x_1, x_2, \dots\))。算法必须在接收到每一个输入 \(x_i\) 时立即做出决策，且该决策通常是不可逆的。算法无法预知未来的输入。

在线算法分析和竞争比

在线算法的分析通常被建模为在线选手 (Online Player) 与 恶意对手 (Malicious Adversary) 之间的博弈： - 在线选手运行在线算法。 - 恶意对手了解选手的算法逻辑，并精心构造一组最坏情况的输入序列，试图最大化在线选手的代价。

目标：设计一种算法，使得即使在对手最恶毒的攻击下，其表现也不会比拥有上帝视角的离线最优算法差太多。

设 \(A\) 是一个在线算法，\(C_A(I)\) 是其在输入序列 \(I\) 上的代价；\(OPT\) 是离线最优算法，\(C_{OPT}(I)\) 是其代价。 如果存在常数 \(\alpha\) 和 \(b\)，使得对于任意输入序列 \(I\)，均满足：

\[C_A(I) \le \alpha \cdot C_{OPT}(I) + b\]

则称算法 \(A\) 是 \(\alpha\)-竞争 的，\(\alpha\) 称为竞争比。 - \(\alpha\) 越小，算法在最坏情况下的鲁棒性越好。 - 对于最小化问题，\(\alpha \ge 1\)。

5.1.2 经典在线问题

滑雪租赁问题

情境：计划去滑雪，但不知道天气何时变坏导致滑雪场关闭（即不知道总天数 \(n\)）。 - 租 (Rent)：每天 1 元。 - 买 (Buy)：一次性支付 \(b\) 元。 目标：最小化总花费。

盈亏平衡算法

策略：先租 \(b-1\) 天；如果第 \(b\) 天还能滑，则购买滑雪板。

情况 1 (\(n < b\))：一直租。代价 \(C_A(n) = n\)，最优代价 \(C_{OPT}(n) = n\)，比值：\(1\)。 情况 2 (\(n \ge b\))：最坏情况发生在刚买完滑雪板后，滑雪场立即关闭（即 \(n=b\)），代价 \(C_A(n) = (b-1) + b = 2b - 1\)，最优代价 \(C_{OPT}(n) = b\)，比值：\(\frac{2b-1}{b} < 2\)。

盈亏平衡算法是 2-竞争 (2-Competitive) 的。

最优缓存问题

缓存容量为 \(k\)，主存容量为 \(N\) (\(N \gg k\))，输入是页面请求序列 \(\sigma = <r_1, r_2, \dots, r_n>\)。 - 命中 (Page Hit)：请求页在缓存中 \(\to\) 代价 0。 - 缺页 (Page Fault)：请求页不在缓存中 \(\to\) 代价 1。 - 此时，若缓存已满，必须选择一页剔除 (Evict)，并将新页载入。 目标：设计页面剔除策略，最小化缺页中断次数。

这个算法的离线最优是贪心算法，即选择缓存中在未来最长时间内不会被访问的那个页面。若某页未来不再被访问，则优先剔除。这个算法被称作最远将来(Farthest-in-Future, FIF)。

常见在线策略

• LIFO (Last-In First-Out，后进先出)：剔除最新进入缓存的页面。

• LFU (Least Frequently Used，最少频繁使用)：剔除过去被访问次数最少的页面。

• FIFO (First-In First-Out，先进先出)：剔除最早进入缓存的页面

• LRU (Least Recently Used，最少最近使用)：剔除距离当前时刻最久未被访问的页面

尽管 LIFO 和 LFU 在特定场景下有其逻辑，但在对抗性分析（面对恶意对手）中，它们的表现是灾难性的，竞争比无法被常数界定。 以LIFO为例： - 缓存容量 \(k\)，当前内容 \(\{1, \dots, k\}\)，最后载入的是 \(k\)。 - 攻击序列：\(k+1, k, k+1, k, \dots\) - LIFO 会在 \(k\) 和 \(k+1\) 之间反复“抖动”，每一次请求都导致缺页。 - \(C_{LIFO} \to \infty\)（相对于 \(C_{OPT}=1\)）。

定理：对于缓存容量为 \(k\) 的系统，任何确定性在线算法 \(A\) 的竞争比至少为 \(k\)。 - 假设系统共有 \(k+1\) 个页面。 - 在每一步，对手总是请求当前不在算法 \(A\) 缓存中的那个页面。 - 由于只有 \(k+1\) 个页且缓存大小为 \(k\)，总有 1 个页在缓存外。 - 这导致算法 \(A\) 每一次请求都发生缺页。对于长度为 \(L\) 的序列，\(C_A = L\) - 对于离线算法，OPT 会查看这 \(k+1\) 个页中哪一个在未来最晚被请求，并剔除它。 - 在 \(k+1\) 个页面的循环请求中，OPT 平均每 \(k\) 次请求才需要缺页一次 因此竞争比约等于k

LRU 策略是 \(k\)-竞争的

• 将请求序列 \(\sigma\) 划分为若干阶段 \(P_1, P_2, \dots\)，每个阶段恰好包含 \(k\) 个不同的页面。一旦请求序列中出现了第 \(k+1\) 个不同的页面，当前阶段结束，新阶段开始。第 \(i\) 阶段结束时的请求页与第 \(i+1\) 阶段开始时的请求页必然不同。

• 在每个阶段 \(P_i\) 内，LRU 策略最多发生 \(k\) 次缺页，设总阶段数为 \(N\)，则 \(C_{LRU} \le k \cdot N\)

此时的FIF算法： - 每当从阶段 \(P_i\) 进入 \(P_{i+1}\) 时，必须处理一个新的页面 \(p_{new}\) - 在 \(P_i\) 结束时，OPT 的缓存中存有 \(k\) 个页。\(P_{i+1}\) 的第一个请求必然是 \(P_i\) 中从未出现过的第 \(k+1\) 个不同页，因此 OPT 在新阶段开始时必然缺页。 - FIF 在每个阶段（除第一个外）至少发生 1 次缺页。\(C_{OPT} \ge N - 1\)。

随机在线算法和标记算法

如前所述，任何确定性在线缓存算法的竞争比至少为 \(k\)。为了获得更好的性能，我们引入随机性。

我们采用不经意对手 (Oblivious Adversary) 模型，对手必须在算法执行前构造好整个请求序列 \(I\)，对手知道算法的代码，但不知道算法执行过程中的随机选择结果。

标记算法 (Marker Algorithm)通过维护页面的“标记”状态来辅助随机剔除

缓存中的每个位置（共 \(k\) 个）有一个标记位，初始全为 0 - 对于每个请求 \(r_i\) - 命中：若 \(r_i\) 在缓存中，将其对应位置标记设为 1 - 缺页：若 \(r_i\) 不在缓存中，检查是否存在标记为 0 的页 - 有 0 标记：在所有标记为 0 的页中，均匀随机选择一个进行剔除。将新页 \(r_i\) 载入并标记为 1。 - 全 1 标记：说明当前阶段结束。将所有标记重置为 0，开始新阶段。然后按“有 0 标记”的情况处理（即随机剔除一个，载入新页并标记）。

Marker 算法对不经意对手是 \(2H_k\)-竞争 的，其中 \(H_k = 1 + 1/2 + \dots + 1/k \approx \ln k\)

定义：除了最后一个阶段外，每个阶段恰好包含 \(k\) 个不同的被标记页面。即每当有 \(k\) 个不同页被请求后，阶段结束。 - \(P_i\)：第 \(i\) 阶段出现的所有 \(k\) 个页面的集合。 - 新页 (New Pages)：\(N_i = P_i \setminus P_{i-1}\)，既在当前阶段出现但上一阶段未出现的页。令 \(|N_i| = n_i\)。 - 旧页 (Old Pages)：\(O_i = P_i \cap P_{i-1}\)，即在上一阶段也出现过的页。\(|O_i| = k - n_i\)。 理论上，每一阶段都会将所有缓存的标记全部标为1，并在进入下一阶段时全部置零。这一阶段结束时，缓存中包含的页面就是这一阶段中出现的所有页面。

分析第 \(i\) 阶段的期望缺页数 - 新页 (\(N_i\))：必然不在缓存中（因为上一阶段没用到，早已被剔除或从未载入）。这就贡献了 \(n_i\) 次缺页。 - 旧页 (\(O_i\))：旧页在上一阶段结束时全部包含在缓存中，但在这一阶段的进行中可能被剔除。 - 假设 \(O_i\) 中的旧页在当前阶段第一次被请求的顺序为 \(y_1, y_2, \dots, y_{k-n_i}\) - 当请求 \(y_j\) 时，已有 \(n_i\) 个新页和 \(j-1\) 个旧页被标记为 1。此时缓存中“未标记”的空位（即可能保留旧页的位置）还有 \(k - (n_i + j - 1)\) 个、 - \(y_j\) 被剔除的概率上限为 \(n_i / (k - j + 1)\) - 对所有旧页求和，期望缺页数 \(\le \sum_{j=1}^{k-n_i} \frac{n_i}{k-j+1} = n_i (H_k - H_{n_i})\)。 总期望：\(E[\text{Faults}_i] \le n_i + n_i(H_k - H_{n_i}) \le n_i H_k\)。

FIF的下界：\(C_{OPT} \ge \frac{1}{2} \sum n_i\)

竞争比：

\[\frac{\sum n_i H_k}{\frac{1}{2} \sum n_i} = 2H_k\]

---

5.2 现代启发式算法

当问题规模巨大且对解的精度要求不苛刻时，启发式算法是工程首选。

启发式算法利用基于经验（Experience-based）的技术寻找问题的满意解，而非绝对最优解。

具备以下特点： - 经验导向：模仿自然现象（如物理退火、生物进化）或人类直觉。

• 近似性：通常不能保证收敛到全局最优，但实用性强。

• 高效性：相比精确算法（如穷举），计算时间大幅减少。

• 问题依赖性：通用性较弱，需针对特定问题设计。

以兔子爬山为例，一些启发式算法的思想如下所示： - 局部搜索 (Local Search)：“视力不好的兔子”。采用贪心策略，每步只向周围比现在高的地方跳。 - 禁忌搜索 (Tabu Search)：“有记忆力的兔子”。记住走过的路并留下记号，优先探索未涉足区域，避免重复。 - 模拟退火 (Simulated Annealing)：“会瞬移的兔子”。在体力好（高温）时可能跳向低处（概率接受劣解），从而跳出局部陷阱。 - 遗传算法 (Genetic Algorithm)：“多产的兔子群”。通过优胜劣汰，海拔高的兔子繁衍后代，种群自动向高峰迁移。

5.2.1 个体算法

邻域搜索算法 NS

从一个初始解 \(x\) 出发，通过定义邻域动作（如交换、插入、反转），在当前解的邻域 \(N(x)\) 中寻找更好的解。 - 生成初始解。

• 在邻域中产生候选解。

• 贪心接受：若候选解优于当前解，则移动；否则尝试其他邻居或停止。

• 重复直至满足终止条件（如找不到更好的解）。

Algorithm Lin-Kernighan (LK)
输入：距离矩阵 D，初始路径 T (通常由贪心算法生成)
输出：优化后的路径 T_best

1. T_best ← T
2. improved ← true
3. while improved do
4.    improved ← false
5.    // 遍历所有节点作为搜索的起点 t1
6.    for each node t1 in T do
7.       // 选择 t1 的邻居 t2，构成第一条要断开的边 x1 = (t1, t2)
8.       for each neighbor t2 of t1 in T do
9.          // 尝试寻找能够改进路径的移动序列 (k-opt)
10.         (is_improved, new_tour) ← Execute-LK-Move(T, t1, t2)
11.         if is_improved then
12.            T ← new_tour
13.            T_best ← new_tour
14.            improved ← true
15.            goto Step 3 (一旦找到改进，立即重新开始主循环 - 贪心策略)
16.         end if
17.      end for
18.   end for
19. end while
20. return T_best

其中的Execute-LK-Move是一种变深度搜索策略，简单起见，以下使用2-opt的示例：

Algorithm EXECUTE-2OPT-MOVE
Input: 当前路径 T，第一条要断开边的端点 t1, t2。
Output: 元组 (improved, T)，其中 improved 为布尔值。
1. x1_cost ← dist(t1, t2)
2. for 每一个节点 t3 ∈ T do
3.    // 过滤无效节点：t3 不能是 t1, t2，且构成的边不能相邻
4.    if t3 ∉ {t1, t2} and t3 is not adjacent to t1 or t2 then
5.       t4 ← next_node(t3)
6.       x2_cost ← dist(t3, t4)
7.       // 计算 2-opt 交换后的新连接成本
8.       y1_cost ← dist(t1, t3)
9.       y2_cost ← dist(t2, t4)
10.      // 计算增益：(断开的边总长) - (新连接的边总长)
11.      gain ← (x1_cost + x2_cost) - (y1_cost + y2_cost)
12.      if gain > 0 then
13.         // 执行 2-opt 反转操作：将 t2 到 t3 之间的路径段反转
14.         Reverse_Segment(T, t2, t3)
15.         return (true, T)
16.      end if
17.   end if
18. end for
19. return (false, T)

领域搜索算法与梯度下降算法相近，两者都是通过迭代改进当前解，逐步逼近局部最优解。这种算法适用于离散空间优化，而后者适用于有一阶导的连续可微函数的优化。另外，这两种算法都比较依赖初始点的选择。

变邻域搜索算法(Variable Neighborhood Search, VNS)使用多种领域结构，并在其中交替搜索。

禁忌搜索算法 TS

禁忌搜索是对局部邻域搜索的一种扩展，旨在实现全局寻优。

在搜索过程中，标记已经搜索过的局部最优解（或移动操作）为“禁忌”，在接下来的迭代中尽量避开这些禁忌对象。它允许算法接受劣解（即目标函数值变差的解），以此来跳出局部最优陷阱。

禁忌搜索算法的构成要素包括： 禁忌表 (Tabu List)：记录近期的历史移动或状态，防止搜索循环 - 禁忌对象：放入表中的元素，可以为状态本身、状态分量或者目标值 - 禁忌任期 (Tabu Tenure)：对象在表中滞留的步数 在当前解 \(x\) 的邻域 \(N(x)\) 中，选择不在禁忌表中的最优候选解 \(s_k(x)\)，即使该解的目标值比当前解差（\(c(s_k(x)) > c(x)\)）。

但如果某个候选解虽然在禁忌表中，但其目标值优于历史最好解（或满足特定渴望水平），则无视禁忌状态，直接接受该解。

Algorithm TABU-SEARCH
Input: 初始解 x_0，禁忌长度 L，最大迭代次数 k_max。
Output: 全局最优解 x^*。
1. x ← x_0
2. x^* ← x_0                     // 初始化全局最优解
3. T ← ∅                         // T 为禁忌表 (队列结构)
4. k ← 0
5. while k < k_max
6.    k ← k + 1
7.    BestCandidate ← null
8.    BestVal ← -∞
9.    ChosenMove ← null
10.   for 每一个候选解 y ∈ N(x) do
11.      move ← 从 x 变换到 y 的操作 (例如: Swap(i, j))
12.      is_tabu ← (move ∈ T)
13.      is_aspiration ← (f(y) > f(x^*))
14.      if (not is_tabu) or is_aspiration then
15.         // 在所有合法候选中寻找最优 (允许劣解)
16.         if f(y) > BestVal then
17.            BestCandidate ← y
18.            BestVal ← f(y)
19.            ChosenMove ← move
20.         end if
21.      end if
22.   end for
23.   if BestCandidate = null then break   //陷入死胡同，提前终止
24.   x ← BestCandidate
25.   if f(x) > f(x^*) then x^* ← x
26.   T ← T ∪ {ChosenMove}
27.   if |T| > L then
28.      从 T 中移除最早进入的移动 (FIFO)
29.   end if
30. end while
31. output x^*

---

主动禁忌搜索 基本 TS 的难点在于禁忌长度（Tabu Size）的设定：太短导致循环，太长限制搜索。主动 TS 通过反馈机制自动调整参数。

• 算法记录所有访问过的解：用于检测是否陷入长周期的循环。
• 如果发现当前解以前访问过（重复），说明陷入循环，将 \(t\) 乘以 \(N_{IN} > 1\)（加强禁忌）。
• 如果连续多步没有重复解，说明搜索路径健康，将 \(t\) 乘以 \(N_{DE} < 1\)（放松禁忌）。
• 如果解的重复次数超过阈值（\(num\_esc\)），说明单纯调整禁忌长度无效。执行随机扰动（随机移动若干步），强行跳出当前区域。

模拟退火算法 SA

Metropolis准则 设当前状态为 \(i\)，能量为 \(E_i\)；新状态为 \(j\)，能量为 \(E_j\)。 能量差 \(\Delta E = E_j - E_i\)。 接受新状态 \(j\) 的概率 \(P\) 为： \[P = \begin{cases} 1, & \text{若 } \Delta E < 0 \text{ (能量降低，解变优)} \\ \exp(-\frac{\Delta E}{kT}), & \text{若 } \Delta E > 0 \text{ (能量升高，解变差)} \end{cases}\]

粒子允许以一定概率接受劣解，从而具备跳出局部最优的能力。温度 \(T\) 越高，接受劣解的概率越大。

马尔科夫链

SA 算法的随机搜索过程可以被建模为一个马尔可夫链 (Markov Chain)。

从状态 \(i\) 转移到状态 \(j\) 的概率 \(p_{ij}\) 由两部分组成： - 生成概率 (Generation Probability, \(g_{ij}\))：在 \(i\) 的邻域中选择 \(j\) 的概率。通常假设是对称的，即 \(g_{ij} = g_{ji}\)。 - 接受概率 (Acceptance Probability, \(a_{ij}\))：基于 Metropolis 准则。 \[a_{ij}(T) = \min \left( 1, \exp \left( -\frac{f(j) - f(i)}{T} \right) \right)\] 转移概率为 \(p_{ij} = g_{ij} \cdot a_{ij}\)。

根据热力学统计物理，在温度 \(T\) 下达到热平衡时，系统处于状态 \(i\) 的概率遵循 Boltzmann 分布： \[P_i(T) = \frac{\exp(-E_i/T)}{\sum_{j=1}^n \exp(-E_j/T)}\] 由于转移概率满足细致平衡条件：\(P_i(T) p_{ij} = P_j(T) p_{ji}\)，因此 Boltzmann 分布确实是该马尔可夫链的平稳分布。 - 在高温下，系统处于各个状态的概率几乎相等。算法行为近似于随机游走 (Random Walk)，进行广域搜索。 - 当温度趋近于 0 时，系统以概率 1 收敛于最低能量状态（全局最优解）。

但是，理论上要求无限满的降温才能保证系统的每一步近似为稳态（热平衡），才能最终收敛到全局最优解。通常需要设计合理的冷却进度表提供较好的近似解。

对于算法： - 初始温度 (\(T_0\))要求足够高，使得 \(\exp(-\Delta E/T_0) \approx 1\)，保证算法初期能自由探索解空间，不依赖初始解，避免过早陷入局部最优 - 等温过程长度要求在每个温度下的迭代次数足够多，通常设为问题规模的函数（如 \(n\) 或 \(n^2\)） - 降温策略可以选择几何降温\(T_{k+1} = \alpha \cdot T_k\)或者算数降温\(T_{k+1} = T_k - \Delta T\)。 - 终止温度要求足够低，以锁定最终解

Algorithm SIMULATED-ANNEALING
输入：初始解 s_0，初始温度 T_0，等温过程迭代次数 L，冷却系数 α (0.95 ~ 0.99)，终止温度 T_f。
输出：全局最优解 s_best。
1. s ← s_0
2. s_best ← s_0
3. T ← T_0
4. while T > T_f
5.    // 内循环：在当前温度下进行 L 次迭代以达到热平衡
6.    for k ← 1 to L
7.       s' ← GenerateNeighbor(s)      // 在邻域内生成一个新的候选解
8.       ΔE ← Cost(s') - Cost(s)       // 计算能量差（目标函数值变化）
9.       if ΔE < 0 then
10.         // 情况 A：新解更优 (能量更低)，贪心接受
11.         s ← s'
12.         if Cost(s) < Cost(s_best) then s_best ← s
13.      else
14.         // 情况 B：新解较差 (能量更高)，按概率接受
15.         p ← exp(-ΔE / T)           // Metropolis 准则
16.         r ← Random(0, 1)           // 生成 [0, 1) 之间的随机数
17.         if r < p then s ← s'       // 即使是劣解也接受，以跳出局部最优
18.      end if
19.   end for
20.   T ← α * T                        // 几何降温过程
21. end while
22. output s_best

5.2.2 群体算法

遗传算法 GA

算法模仿达尔文的生物进化论——“物竞天择，适者生存”。通过模拟生物种群的繁衍、变异和自然选择，让解群体在迭代中不断进化，最终逼近全局最优解。

生物学术语	优化问题对应	含义
个体 (Individual)	解 (Solution)	问题的某一个可行解
种群 (Population)	解集 (Set of Solutions)	一组可行解的集合，并行搜索的基础
染色体 (Chromosome)	编码 (Encoding)	解的数字化表示（如二进制串）
基因 (Gene)	特征/分量 (Feature)	解的某一特定维度或属性
适应度 (Fitness)	目标函数值 (Objective Value)	衡量解质量好坏的标准

算法每一代包含以下步骤: - 种群初始化: 随机生成 \(N\) 个初始个体构成第一代种群。 - 适应度评估：计算每个个体的适应度值 \(F(x)\)，适应度通常要求非负且越大越好，对于最小化问题，需进行转换（如取倒数或相反数）。 - 选择操作：优胜劣汰，让适应度高的个体有更多机会遗传给下一代 - 轮盘赌选择 (Roulette Wheel Selection)：个体被选中的概率与其适应度成正比。概率 \(P_i = F_i / \sum F_j\) - 锦标赛选择 (Tournament Selection)：随机选取 \(k\) 个个体，其中最优者胜出 - 精英保留 (Elitism)：强制将当代最优个体直接复制到下一代，防止最佳基因丢失 - 遗传算子： - 交叉：按交叉概率 \(P_c\)（通常较大，如 0.9）选择两个父代个体，交换其部分染色体片段。 - 变异：按变异概率 \(P_m\)（通常极小，如 0.01~0.1）随机改变染色体上的某一位（如 0 变 1）。

---

以0-1 背包问题为例：给定 \(n\) 个物品（价值 \(p_i\)，重量 \(w_i\)）和背包容量 \(W\)，选择物品子集使得总价值最大且总重量不超过 \(W\)。

编码：常用二进制编码 \(X = (x_1, \dots, x_n)\)，\(x_i \in \{0, 1\}\)

对于随机生成或交叉产生的子代可能违反重量约束，可以在适应性函数中加入惩罚项，也可以将非法解修复为合法解： - 贪心修复：计算物品的性价比 \(p_i/w_i\) 并降序排列；对于超重的非法解，优先保留性价比高的物品，贪心地移除性价比低的物品，直到满足约束。

Algorithm GENETIC-KNAPSACK
Input:  n 个物品的集合 (价值 p, 重量 w)，背包容量 W，
        种群大小 N_pop，最大迭代次数 MaxGen，
        交叉概率 P_c，变异概率 P_m。
Output: 全局最优解 BestSol。

1. R_order ← Sort indices by (p_i / w_i) ascending
2. Population ← Generate N_pop random binary vectors
3. for each individual S in Population do
4.    GREEDY-REPAIR(S, W, R_order)   
5.    Evaluate Fitness(S)            
6. end for
7.  BestSol ← GetBest(Population)
8.  for gen ← 1 to MaxGen do
9.     NewPop ← ∅
10.    // 精英保留策略
11.    NewPop ← NewPop ∪ {BestSol}
12.    while |NewPop| < N_pop do
13.       // 锦标赛选择
14.       Parent1 ← TournamentSelect(Population)
15.       Parent2 ← TournamentSelect(Population)
16.       // 2. 交叉 (Crossover)
17.       if Random(0, 1) < P_c then
18.          (Child1, Child2) ← OnePointCrossover(Parent1, Parent2)
19.       else
20.          (Child1, Child2) ← (Parent1, Parent2)
21.       end if
22.       Mutate(Child1, P_m)
23.       Mutate(Child2, P_m)
24.       GREEDY-REPAIR(Child1, W, R_order)
25.       GREEDY-REPAIR(Child2, W, R_order)
26.       Evaluate Fitness(Child1)
27.       Evaluate Fitness(Child2)
28.       NewPop ← NewPop ∪ {Child1, Child2}
29.    end while
30.    Population ← NewPop
31.    CurrentBest ← GetBest(Population)
32.    if Fitness(CurrentBest) > Fitness(BestSol) then BestSol ← CurrentBest
33. end for
34. output BestSol

Algorithm GREEDY-REPAIR
Input:  个体解 S (二进制向量 x_1...x_n)，背包容量 W，
        排序索引列表 R_order (性价比从小到大)。
Output: 修复后的合法解 S (原地修改)。
1. CurrentWeight ← CalculateWeight(S)
2. if CurrentWeight > W then
3.    for each index i in R_order do
4.       if S[i] == 1 then
5.          S[i] ← 0                
6.          CurrentWeight ← CurrentWeight - w_i
7.          if CurrentWeight ≤ W then break  /
8.       end if
9.    end for
10. end if

免疫算法 IA

将生物免疫系统的概念（如抗原识别、抗体克隆、免疫记忆）引入遗传算法，旨在保留原算法优良特性的前提下，抑制早熟收敛和种群退化。

算法的流程为： - 初始化 (Initialization)：随机生成初始抗体种群（候选解集）。 - 亲和度计算 (Affinity Calculation)：评估每个抗体的质量（如计算目标函数值）。 - 选择与克隆 (Selection & Cloning)： - 对优秀抗体进行复制。关键点：克隆的数量与亲和度成正比（越优秀的解，复制的副本越多）。 - 超变异 (Hypermutation) - 对克隆后的抗体进行变异操作以探索局部区域，对克隆后的抗体进行变异操作以探索局部区域 - 抑制与多样性保持 (Suppression) - 计算抗体间的相似度（如欧氏距离、汉明距离）,若抗体过于相似（浓度过高），则移除或抑制冗余抗体，防止同质化 - 补充随机生成的“新抗体”以维持种群多样性 - 免疫记忆 (Immune Memory)：将历代最优抗体存入记忆库，用于加速后续搜索或应对动态环境变化。 - 终止判断：达到最大迭代次数或满足精度要求。

免疫算法比遗传算法更适合用来进行多模态优化和动态环境优化。

蚁群算法 ACO

蚂蚁在寻找食物过程中会分泌为信息素。由于短路径往返时间短，单位时间内通过的蚂蚁更多，留下的信息素累积更快，从而吸引更多后续蚂蚁，最终形成信息正反馈，使整个群体集中到最短路径上。

基本蚁群算法采用人工蚂蚁的行走路线表示可行解，通过信息素交换路径信息，形成集体自催化行为寻找最优路径。

以TSP问题为例： 蚂蚁 \(k\) 在 \(t\) 时刻由城市 \(i\) 转移到城市 \(j\) 的概率 \(P_{ij}^k(t)\) 定义为：

\[P_{ij}^k(t) = \frac{[\tau_{ij}(t)]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{s \in allowed_k} [\tau_{is}(t)]^\alpha \cdot [\eta_{is}]^\beta}\]

• \(\tau_{ij}(t)\)：边 \((i, j)\) 上的残留信息量。
• \(\eta_{ij} = 1/d_{ij}\)：启发式因子，反映由 \(i\) 转移到 \(j\) 的期望程度。
• \(\alpha, \beta\)：分别为信息启发因子和期望启发因子，反映了信息素与距离的相对重要程度。
• \(allowed_k\)：蚂蚁 \(k\) 下一步允许选择的城市集合。

信息素更新更新公式： \[\tau_{ij}(t+n) = (1-\rho) \tau_{ij}(t) + \Delta \tau_{ij}\] - \(\rho \in [0, 1)\)：信息素挥发系数 - \(\Delta \tau_{ij} = \sum_{k=1}^m \Delta \tau_{ij}^k\)：本轮全体蚂蚁在路径 \((i, j)\) 上留下的信息素增量

常见的更新策略 - 蚁周模型 (Ant-Cycle Model)：利用整体信息，在蚂蚁完成一个循环后更新路径信息素。释放量 \(\Delta \tau_{ij}^k = Q/L_k\) - 蚁量模型 (Ant-Quantity Model)：利用局部信息，蚂蚁每走一步更新一次。释放量 \(\Delta \tau_{ij}^k = Q/d_{ij}\)。

Algorithm ANT-COLONY-OPTIMIZATION-TSP
输入：城市坐标或距离矩阵 D，蚂蚁数量 m，最大迭代次数 Gen_max，
      信息启发因子 α，期望启发因子 β，挥发系数 ρ，信息素强度 Q。
输出：全局最优路径 BestTour 及其长度 BestLength。

1. 初始化所有边 (i, j) 上的初始信息素 τ_{ij} 为一常数 (如 1.0)
2. BestLength ← ∞
3. BestTour ← ∅
4. k_gen ← 0
5. while k_gen < Gen_max
6.    k_gen ← k_gen + 1
7.    for k ← 1 to m
8.       随机选择一个起始城市放入蚂蚁 k 的禁忌表 tabu_k 中
9.    end for
10.   // 蚂蚁构建路径 (逐步移动直至走完所有城市)
11.   for step ← 1 to n - 1    
12.      for k ← 1 to m
13.         i ← 蚂蚁 k 当前所在城市
14.         根据状态转移概率 P_{ij}^k(t) 选择下一个城市 j:
15.         将城市 j 加入 tabu_k，更新当前城市为 j
16.      end for
17.   end for
18.   // 计算并更新本轮最优解
19.   for k ← 1 to m
20.      L_k ← 蚂蚁 k 经过的路径总长度
21.      if L_k < BestLength then
22.         BestLength ← L_k
23.         BestTour ← tabu_k
24.      end if
25.   end for
26.   // 息素更新 (基于蚁周模型)
27.   for 每一条边 (i, j) in E do
28.      τ_{ij} ← (1 - ρ) * τ_{ij}
29.   end for
30.   for k ← 1 to m
31.      Δτ_k ← Q / L_k
32.      for 每一条属于 tabu_k 的边 (i, j) do
33.         τ_{ij} ← τ_{ij} + Δτ_k
34.      end for
35.   end for
36.   for k ← 1 to m do tabu_k ← ∅
37. end while
38. output BestTour, BestLength

粒子群优化算法 PSO

设想一群鸟在随机搜索食物，区域内只有一块食物，鸟儿不知道食物位置，但知道当前离食物有多远（通过适值函数评估）。 寻找食物的最优策略是搜寻目前离食物最近的鸟的周围区域。

PSO 将问题的每一个可行解看作解空间中的一个“粒子”。粒子在 \(D\) 维空间中以一定的速度飞翔，其位置随迭代动态变化。 - 第 \(i\) 个粒子的位置：\(x_{id}^k\)，代表当前的候选解。 - 第 \(i\) 个粒子的速度：\(v_{id}^k\)，决定飞行的方向和距离。 - 个体极值 (\(pbest_i\))：\(p_{id}^k\)，粒子 \(i\) 自身搜索到的历史最好点。 - 全局极值 (\(gbest\))：\(p_{gd}^k\)，群体内（或邻域内）所有粒子所经过的历史最好点。

演化方程 - 速度更新方程 \[v_{id}^{k+1} = \underbrace{v_{id}^k}_{\text{惯性作用}} + \underbrace{c_1 \xi (p_{id}^k - x_{id}^k)}_{\text{自我认知（经验）}} + \underbrace{c_2 \eta (p_{gd}^k - x_{id}^k)}_{\text{社会经验（学习）}}\] - \(\xi, \eta\) 为 \([0, 1]\) 上的独立随机变量。 - \(c_1, c_2\) 为加速因子 (Learning Factors)，调节向个体最优和群体最优靠近的步长 - 位置更新方程 \[x_{id}^{k+1} = x_{id}^k + v_{id}^{k+1}\]

算法每一步都根据演化方程维护所有粒子状态，直至终止。

---

5.3 综述：最短路径问题的多维视角 (Review: Shortest Path)

本节以“最短路径”为线索，串联全课算法思想。

5.3.1 问题描述

单源最短路径问题：在一个连通的有向无环图（或一般图）中，每条边带有非负权重（距离）。给定起点（源点）和终点，目标是找到一条路径，使得该路径上所有边的权重之和最小。

给定一个有向加权图 \(G = (V, E, W)\) - 顶点集 (Vertex Set)：\(V = \{v_1, v_2, \dots, v_n\}\)，表示网络中的所有节点。 - 边集 (Edge Set)：\(E \subseteq V \times V\)，其中每条边 \(e = (u, v)\) 表示从节点 \(u\) 到节点 \(v\) 的直接路径。 - 权重函数 (Weight Function)：\(w: E \rightarrow \mathbb{R}_{\geq 0}\)。对于每一条边 \((u, v) \in E\)，有一个非负实数权重 \(w(u, v)\)，代表物理距离、时间或成本。

路径定义 (Path Definition)：定义一条从起点 \(s\) 到终点 \(d\) 的路径 \(P\) 为顶点的序列： \[P = (v_0, v_1, v_2, \dots, v_k)\] 其中：\(v_0 = s\)，\(v_k = d\)。对于所有的 \(0 \leq i < k\)，满足 \((v_i, v_{i+1}) \in E\)。

目标函数 (Objective Function)定义路径 \(P\) 的总成本 \(C(P)\) 为该路径上所有边权重的累加和： \[C(P) = \sum_{i=0}^{k-1} w(v_i, v_{i+1})\] 我们的目标是寻找一条最优路径 \(P^*\)，使得： \[C(P^*) = \min \{ C(P) \mid P \text{ 是从 } s \text{ 到 } d \text{ 的可行路径} \}\]

算法名称	时间复杂度 (Time Complexity)	空间复杂度 (Space Complexity)	备注 (Remarks)
蛮力/穷举法 (Brute Force)	\(O(V \cdot V!)\)	\(O(V)\)	尝试所有全排列，仅适用于极小规模图。
图的 BFS (广度优先)	\(O(V!)\)	\(O(V \cdot V!)\)	允许顶点重复访问以穷尽路径，内存消耗极高。
图的 DFS (深度优先)	\(O(V!)\)	\(O(V)\)	允许重复访问。内存消耗较少，但搜索时间极长。
回溯法 (Backtracking)	\(O(V!)\) (最坏情况)	\(O(V)\)	引入可行性剪枝。对 DAG 或稀疏图效率显著提升。
分支定界法 (Branch & Bound)	\(O(V!)\) (最坏情况)	\(O(V^2)\) 或更多	基于 BFS + 最优性剪枝（如当前路径已超已知最短则舍弃）。
动态规划 (DP)	\(O(V+E)\)	\(O(V)\)	仅适用于有向无环图 (DAG)，利用拓扑序计算。
Dijkstra 算法	\(O(V^2)\)	\(O(V)\)	贪心策略。使用斐波那契堆可优化至 \(O(E + V \log V)\)。
Floyd-Warshall 算法	\(O(V^3)\)	\(O(V^2)\)	解决任意两点间的最短路径，而非单源。

5.3.2 穷举法

基础的穷举法列出全排列路径，对于\(n\)个节点的列表，总共有： \[1+\sum_{i = 1}^{n-2}\left(\prod_{j = 1}^{i}(x-j)\right) = O(n!)\]

种排列。对于每一种排列，需要\(O(n)\)的时间复杂度验证是否可行和计算权重。因此，这种算法的时间复杂度为\(O(n\cdot n!)\)

这种算法的伪代码可以写作：

Algorithm EXHAUSTIVESEARCH(V,s,d，E,W)
Input: 顶点集V，起点s，终点d，权重矩阵W，。
Output：最短路径P_m

V_mid <- V / {s,d}
P_m <- ∅
w_m <- infinity

for i <- 1 to |V_mid| do
    Cur_P = {s} ∪ sub_P ∪ {d}
    Cur_w = 0
    isValid = true
    for 子排列 Sub_P in V_mid的所有i个元素的排列 do
        for i <- 0 to |Sub_P| do
            if (Cur_P(i),Cur_P(i+1)) in E then
                Cur_w <- Cur_w + W(u,v)
            else
                isValid = false
                break
            end if
        end for
        if isValid and Cur_w < W_m then
            P_m <- Cur_P
            w_m <- Cur_w
        end if
    end for
end for
output P_m,w_m

5.3.3 广度优先搜索 BFS

广度搜索都能保证搜索到的路径一定是合法的。

• 从起点开始进行广度优先搜索，并维护一个储存(u,d)（顶点和到达该顶点的代价）的队列
• 每一步搜索从队列中取出\((u, d)\)，遍历 \(u\) 的所有邻居 \(v\)，对于每一个邻居，构造新状态 \((v, d + w(u, v))\) 并入队
• 如果 \(v\) 是终点 \(G\)，且当前路径长度 \(d + w(u, v)\) 小于已记录的全局最短距离 \(dist\_min\)，则更新 \(dist\_min\)，对于此节点，不再加入新节点到队列。
• 当队列空时，或已经计算的元素数大于\(\frac{n^n-1}{n-1}\)（n层的n叉完全树的总节点数）时截止计算（事实上，因为图是无环的，总计算书不会超过这个值）。

Algorithm BFS
w_m <- infinity
Queue <- empty queue
Queue.enqueue((s,0))
while Queue is not empty:
    (v,w_curr) <- Queue.dequeue()
    for each edge (u,v) in E do
        w_new <- w_curr+w(u,v)
        if v == d then
            if w_new < w_m then
                w_m = w_new
            end if
        else
            Queue.enqueue((v,w_new))
        end if
    end for
end while
output w_m

注意以上伪代码展示的算法没有将路径加入队列元素中。

算法的时间复杂度为\(O(n!)\)，相当于不需要检查可行性的枚举法。

算法的空间复杂度，如果需要储存路径，为\(O(n\cdot n!)\)

5.3.4 深度优先搜索&回溯法

深度优先搜索策略：

• 从起点开始进行深度搜索，并维护一个储存(u,d)的栈
• 其余部分与广度搜索策略基本完全相似

使用深度优先搜索可以将路径额外储存在一个长度为\(n\)的列表中，动态维护列表。为了保证能够正确回溯，需要使用递归方式来进行深度优先搜索。

Algorithm DFS
    p_m <- empty list [n]
    p_curr <- empty list [n]
    w_m <- infinity

    DFS(s,0)
    output w_m,p_m

Procedure DFS(u,w_curr)
    p_curr.append(u)
    if u = d then
        if w_curr < w_m then
            w_m <- w_curr
            p_m <- p_curr.copy()
        end if
    else
        for each edge (u, v) ∈ E do
            w_new <- w_curr + w(u, v)
            if w_new < w_m then
                DFS(v,w_new)
            end if
        end for
    end if
    p_curr.pop()

这种方法不改变时间复杂度，但是将空间复杂度降低到线性。

为了进一步优化性能，可以引入剪枝的思想，即当当前分支的w_curr已经超过w_m时，直接回溯。

5.3.5 分支定界法

这是一个最小化问题，因此v_m可以直接作为上界。我们寻找一种分支下界（可能能达到的最小值）的计算方法。

考虑算法结构，从s出发，s的所有邻域节点v都是可能的下个分支。一种可能的下界确定法： - 预计计算整个图中，除去起点所有节点的最小进入权重，也就是对于任意节点w，所有(x,w)的最大权重。 - 对于邻域v，其下界为已选路径权重（对于当前情况就是w(s,v)）+未选节点最小权重和 也就是贪心最小边下界

相同问题的下界确定法是v到终点的欧几里得距离或者哈密顿距离，但是问题没有相关约束，因此不能使用。

除此之外还可以想到，可以为每个顶点维护一个最短路径状态，即从原点到该顶点的已知端点距离。如果当前路径的这一项大于已知最短距离，则直接放弃该分支。

数据结构方面，我们使用优先队列，这是一种出列优先级最大的元素的队列。

Algorithm BB
输入：图 G=(V, E)，起点 s，终点 d，下界函数 LB(u)。
输出：最短距离 d_m，最短路径p_m

d_m <- ∞
PQ <- empty priority queue
PQ.push( (s, 0, emptylist, LB([s])) )
p_m <- empty List
Shorted_path <- empty Map
for vertex in V do
    Shorted_path.put((vertex,∞))
Shorted_path[s] <- 0

while PQ is not empty do
    (u, curr_w,curr_path, curr_bound) ← PQ.pop_min()
    // 两种剪枝可能
    if curr_w > Shorted_path[u] then
        continue
    else
        Shorted_path[u] = curr_w
    end if
    if curr_bound >= d_m then
        continue
    end if

    for each neighbor v of u do
        new_w <- curr_w + w(u,v)
        new_path = curr_path.append(v)
        if v = d then
            if new_w < d_m then
                d_m <- new_w
                p_m <- new_path
        else
            new_bound <- LB(new_path )+curr_w
            if new_bound > d_m then
                continue
            end if
            PQ.enqueue((v,new_w,new_path,new_bound))
        end if
    end for
end while
output d_m,p_m

这种算法的时间和空间复杂度都依赖于优先队列的大小\(E\)，分别为\(O(|E| \log |V|)\)和\(O(|E| \cdot |V|)\)，这种算法的最坏时间和空间复杂度与广度搜索相同（甚至因为使用了优先队列而更差）。

5.3.6 动态规划

该问题与各种分割问题，比如矩阵最少乘法问题相似。有递归式：

\[T(i,j) = min_{k\in i到j的中间节点集}(T(i,k)+T(k,j)) \]

问题主要在于中间节点集合如何求取。一种可行的设想是对节点进行拓扑排序

使得如果图中存在边 \((u, v)\)，则在排序结果中 \(u\) 必须出现在 \(v\) 之前。

直接写出自定而上的伪代码：

Algorithm DP

T <- double-dim List [n,n] initial with infinity
D <- TopologicalSort(s) // 为了方便，假定D[i]返回的是排序后i对应的位置
for i <- 0 to n do
    T[i,i] = 0

Check(s,d)//假定s、d为对应节点的编号

Procedure Check(i,j)

if D[i]>D[j] then
    return infinity //理论上不会进入这一步

if T[i,j] is not inifinity then
    return T[i,j]

if (i,j) in E then
    base_length = w(i,j)
else
    base_length = infinity
end if

for each k that D[k] < D[j] and D[i] < D[k] do
    possible_length = Check(i,k)+Check(k,j)
    if possible_length < base_length then
        base_length = possible_length
    end if
end for
T[i,j] <- base_length
return T[i,j]

其中TopologicalSort是我们讨论过的tanh算法，不断寻找并移除那些不依赖任何其他节点的节点。

Algorithm TOPOLOGICAL-SORT
1.  L ← empty list                  // 用于存储最终的拓扑序列
2.  S ← empty queue (或 stack)      // 存储所有入度为 0 的节点
3.  InDegree ← Map {v: 0 for v in V} // 初始化入度表
4.  // 1. 统计每个节点的入度 (In-degree)
5.  for each edge (u, v) ∈ E do
6.      InDegree[v] ← InDegree[v] + 1
7.  end for
8.  // 2. 将所有初始入度为 0 的节点加入集合 S
9.  for each vertex v in V do
10.     if InDegree[v] == 0 then
11.         S.push(v)
12.     end if
13. end for
14. // 3. 主循环：不断移除入度为 0 的节点
15. while S is not empty do
16.     u ← S.pop()
17.     L.append(u)                 // 将 u 加入拓扑序列
18.     // 遍历从 u 出发的所有边 (u, v)
19.     for each neighbor v of u do
20.         InDegree[v] ← InDegree[v] - 1  // “移除”边 (u, v)
21.         // 如果 v 的入度变为 0，说明它依赖的所有前驱都已处理
22.         if InDegree[v] == 0 then
23.             S.push(v)
24.         end if
25.     end for
26. end while
27. // 4. 环路检测
28. if |L| < |V| then
29.     return Error (图中有环，不存在拓扑序)
30. else
31.     return L
32. end if

这种算法的时间复杂度很高，对于表中的每个元素，都需要一个关于k的循环处理。在稠密图情况下，这个步骤可能是O(n)的时间复杂度，因此，总的时间复杂度来到了O(n^3)。

这个算法为什么会复杂那么多呢？这个算法，如其的递归形式，实际上可以计算任意两点间的最短路径，并没有使用到起点和终点唯一的约束。

实际上，这个算法已经与Floyd-Warshall算法复杂度相同，因此不如直接使用Floyd-Warshall算法。区别仅在于中间节点集合如何求取的问题。

现在使用拓扑排序是在有向无环图假设下，限制了k的规模，使得T[i,k]和T[k,j]一定已经得到计算（或者说T[i,k]和T[k,j]的计算不依赖于T[i,j]的计算）。Floyd-Warshall算法则将T在逻辑上拓展为三维：T[i,j,k]，在计算时状态转移方程变化为：

\[dp[k][i][j] = \min(dp[k-1][i][j], \quad dp[k-1][i][k] + dp[k-1][k][j])\]

也就是k被放在最外环运行：

Algorithm FLOYD-WARSHALL
1. D ← W 的拷贝
2. // k 在最外层！这是动态规划“阶段”的体现。
3. for k ← 1 to n do
4.    for i ← 1 to n do
5.       for j ← 1 to n do
6.          if D[i][k] + D[k][j] < D[i][j] then
7.             D[i][j] ← D[i][k] + D[k][j]
8.          end if
9.       end for
10.   end for
11. end for
12. 
13. output D

伪代码中可以看到，虽然形式上T被拓展为三维数组，当实际操作中只需要使用2维数组。很巧妙的算法。

---

重新考虑这个动规问题的阶段的定义。从起点开始，我们可以定义每增加一个节点是一个状态。此时的递归公式转换为：

\[T[v] = \min(T[u] + w(u, v))\]

变成了一个线性的动规问题。

Algorithm DP-SHORTEST-PATH-DAG
输入：有向无环图 G=(V, E)，起点 s，终点 d。
输出：最短距离 dist[d]。

1.  // 1. 预处理：拓扑排序 (确保计算 v 时，其所有前驱节点已计算完成)
2.  L ← TopologicalSort(G) 
3.  
4.  // 2. 初始化状态数组
5.  dist ← Map {v: ∞ for v in V}
6.  dist[s] ← 0
7.  parent ← Map {v: null for v in V} // 用于回溯路径
8.  
9.  // 3. 状态转移 (自底向上/线性扫描)
10. for each node u in L (从起点 s 所在的顺序开始) do
11.    if dist[u] < ∞ then
12.       for each neighbor v of u do
13.          // 核心转移方程：dist[v] = min(dist[v], dist[u] + w(u, v))
14.          if dist[u] + w(u, v) < dist[v] then
15.             dist[v] ← dist[u] + w(u, v)
16.             parent[v] ← u
17.          end if
18.       end for
19.    end if
20. end for
21. 
22. // 4. 重构路径
23. p_m ← ReconstructPath(parent, d)
24. output dist[d], p_m

在这个动规中，实际上维护了从起点到每个节点的可能的最近信息。这种算法的时间复杂度取决于拓扑排序，为\(O(E+V)\)

这个算法是有向无环图 (DAG) 的最优解法。

5.3.7 贪心算法

Dijkstra 算法

这是非负权单源图最短路路径的最优解，在这个图中，目前离起点最近的那个未访问节点，不可能通过绕路变得更近，也就是说，当准备计算离起点地n进的起点时，只有比它更近的节点可能会影响计算。

流程： - 在这个图中，目前离起点最近的那个未访问节点，不可能通过绕路变得更近 - 从堆中弹出距离最小的节点 \(u\) - 将 \(u\) 标记为“已确定”（后续不再处理） - 遍历 \(u\) 的邻居 \(v\)。如果 \(dist[u] + w(u, v) < dist[v]\)，则更新 \(dist[v]\) 并将 \(v\) 压入堆（或更新堆中 \(v\) 的优先级）。

这种算法的时间复杂度为O(ElogV)，即遍历边、最优队列每次维护的代价是logV

大规模图预处理：收缩层次结构

节点重要性排序 (Node Ordering)给图中的每一个节点 \(v\) 赋予一个等级 \(Rank(v)\)： - 试探性地移除节点 \(v\)，计算需要增加多少条“捷径”边，减去 \(v\) 原本的边数。需要增加的捷径越少，说明 \(v\) 越不重要（越处于死角），应该越先被移除

节点收缩，按照 Rank 从低到高，依次“收缩”（移除）节点。 假设我们要移除节点 \(v\)： - 找到所有能到达 \(v\) 的邻居 \(U = \{u_1, u_2, \dots\}\) - 找到所有从 \(v\) 出发的邻居 \(W = \{w_1, w_2, \dots\}\) - 对于每一对 \((u, w)\)，原本有一条路径 \(u \to v \to w\)。我们必须检查：在不经过 \(v\) 的情况下，是否还存在另一条比 \(u \to v \to w\) 更短或相等的路径 - 如果存在：说明 \(v\) 对这条路不重要，直接删掉 \(v\) - 如果不存在：说明 \(v\) 是必经之路。为了保持图的连通性和距离正确性，我们必须在 \(u\) 和 \(w\) 之间添加一条人工边，其权重为 \(w(u,v) + w(v,w)\)

查询变为双向 Dijkstra 搜索 - 从起点 \(s\) 出发，只走 \(Rank(neighbor) > Rank(current)\) 的边 - 从终点 \(t\) 出发，只走 \(Rank(neighbor) > Rank(current)\) 的反向边 两个搜索会在某个最高等级的节点 \(v_{top}\) 相遇，最短路径长度 = \(\min(dist_{fwd}[v] + dist_{bwd}[v])\)。