一、引言：不确定性下的决策
日常工程中我们时常面对一类特殊的算法问题：输入不是一次性给出的，而是随时间逐步揭示，且每一步的决策不可撤销。 这就是在线算法（online algorithm）的核心特征。
缓存替换时，你不知道未来会访问哪些页面；云计算中，你不知道一台虚拟机还要运行多久；广告投放中，你不知道下一个用户的点击价值。所有这些场景都有一个共同特点：决策必须在信息不完整时做出。
自然而然地，一个问题浮现出来：
在最坏情况下，在线算法与拥有完整信息的离线最优解相比，性能差距的上界是多少？
竞争分析（competitive analysis） 正是回答这个问题的数学框架。它由 Sleator 和 Tarjan 于 1985 年引入，已成为理论计算机科学中分析在线算法最重要的工具之一。
本文是算法系列的第 115 篇，也是最后一篇。我们将系统讲解竞争分析的核心理论、经典问题和工程应用，为整个系列画上句号。
二、在线算法与离线算法
2.1 基本定义
离线算法（offline algorithm）：拥有完整输入信息，可以一次性计算出最优解。
在线算法（online algorithm）：输入序列 \(\sigma = \sigma_1, \sigma_2, \ldots, \sigma_n\) 逐个到达。算法在收到 \(\sigma_i\) 时，必须立即做出不可撤销的决策，且不知道 \(\sigma_{i+1}, \ldots, \sigma_n\)。
形式化地，设在线算法 \(A\) 对输入序列 \(\sigma\) 的代价为 \(A(\sigma)\)，离线最优算法（通常称为 adversary 或 OPT）对同一输入的代价为 \(\text{OPT}(\sigma)\)。
2.2 对手模型
在线算法的分析中，我们假设存在一个”对手”（adversary），它选择最不利的输入序列来最大化在线算法的相对代价。对手有三种强度：
| 对手类型 | 能力 | 适用场景 |
|---|---|---|
| 遗忘对手（oblivious adversary） | 预先确定整个输入序列，不依赖算法的随机选择 | 随机化算法的分析 |
| 自适应在线对手（adaptive online adversary） | 能看到算法过去的决策，动态选择后续输入 | 更强的下界 |
| 自适应离线对手（adaptive offline adversary） | 能看到算法的所有决策（包括未来的随机选择） | 最强的对手模型 |
对于确定性在线算法，三种对手模型等价。对于随机化算法，遗忘对手模型最常用。
2.3 一个直觉的例子
考虑一个简单的问题：你每天早上出门时需要决定是否带伞。如果带了伞但没下雨，你承受了携带的不便（代价 1）；如果没带伞却下了雨，你被淋湿（代价 10）。
离线最优：完美天气预报，只在下雨天带伞。
在线算法：没有预报，只能基于历史信息或固定策略做决策。
竞争分析衡量的就是：你的策略在最坏天气模式下，代价是离线最优的多少倍？
三、竞争比的严格定义
3.1 确定性竞争比
一个确定性在线算法 \(A\) 称为 \(c\)-竞争的（\(c\)-competitive），如果存在常数 \(\alpha\)，使得对所有输入序列 \(\sigma\)：
\[A(\sigma) \leq c \cdot \text{OPT}(\sigma) + \alpha\]
其中 \(c\) 称为 竞争比（competitive ratio），\(\alpha\) 是与输入长度无关的加法常数。
当 \(\alpha = 0\) 时，称算法是 严格 \(c\)-竞争的（strictly \(c\)-competitive）。
算法 \(A\) 的竞争比定义为：
\[c_A = \sup_{\sigma} \frac{A(\sigma)}{\text{OPT}(\sigma)}\]
3.2 随机化竞争比
对于随机化在线算法 \(A\)，在遗忘对手模型下，\(A\) 称为 \(c\)-竞争的，如果对所有输入序列 \(\sigma\)：
\[\mathbb{E}[A(\sigma)] \leq c \cdot \text{OPT}(\sigma) + \alpha\]
期望取自算法内部的随机选择。
3.3 竞争比的含义
竞争比捕捉的是 信息缺失的代价。如果一个问题的最佳竞争比为 \(c\)，意味着：
- 没有任何在线算法能在所有输入上做到比 OPT 差 \(c\) 倍以内（下界）。
- 存在某个在线算法能保证在所有输入上不超过 OPT 的 \(c\) 倍（上界）。
竞争比越接近 1 = 信息缺失的代价越小 = 在线可以做得几乎和离线一样好
竞争比很大 = 信息极其关键 = 不知道未来意味着巨大的性能损失3.4 与近似比的区别
| 比较维度 | 竞争比 | 近似比 |
|---|---|---|
| 信息模型 | 输入逐步揭示 | 输入完全已知 |
| 比较对象 | 在线算法 vs 离线最优 | 多项式算法 vs NP-hard 最优 |
| 困难来源 | 信息不完整 | 计算复杂度 |
| 不可撤销性 | 通常要求 | 不要求 |
四、滑雪租赁问题
滑雪租赁（Ski Rental）是竞争分析中最经典、最直观的入门问题。
4.1 问题定义
你去滑雪度假，但不知道自己会滑多少天。每天有两个选择：
- 租滑雪板：每天花费 1 元。
- 买滑雪板：一次性花费 \(B\) 元，之后免费使用。
你不知道总共会滑多少天（设为 \(n\) 天），需要在每一天决定是继续租还是买。一旦买了，就不会再租。
离线最优：如果 \(n < B\)，只租，代价 \(n\)；如果 \(n \geq B\)，第一天就买，代价 \(B\)。因此 \(\text{OPT} = \min(n, B)\)。
4.2 确定性最优策略
策略：在第 \(B\) 天购买（即租了 \(B-1\) 天后买入）。
分析：
情况一：\(n < B\)（实际滑雪天数少于 \(B\) 天）。 - 算法代价：\(n\)（只租，没到第 \(B\) 天就结束了）。 - OPT 代价：\(n\)。 - 比值：\(1\)。
情况二：\(n \geq B\)。 - 算法代价：\((B-1) + B = 2B - 1\)（前 \(B-1\) 天的租金加上购买费用）。 - OPT 代价：\(B\)。 - 比值：\((2B-1)/B = 2 - 1/B < 2\)。
因此，该策略是 2-竞争的。
这是确定性最优吗？ 是的。考虑任何确定性策略在第 \(d\) 天购买：
- 若 \(d < B\)：对手选择 \(n = d\)，代价为 \(d - 1 + B\)，而 OPT 为 \(d\)，比值为 \((d - 1 + B)/d\)。当 \(d\) 较小时比值很大。
- 若 \(d > B\)：对手选择 \(n = d\)，代价为 \(d - 1 + B\)，而 OPT 为 \(B\)，比值为 \((d - 1 + B)/B > 2\)。
- 若 \(d = B\)：如上分析，比值最优，趋近于 \(2\)。
4.3 确定性下界
定理：没有确定性在线算法对滑雪租赁问题能达到严格小于 2 的竞争比。
证明：对手采用如下策略。设算法在第 \(d\) 天购买。
- 如果 \(d \leq B\)，对手让 \(n = d\)。算法代价 \(= (d-1) + B\)，OPT \(= d\)。比值 \(= (d - 1 + B) / d = 1 + (B-1)/d \geq 2 - 1/B\)（取 \(d = B\) 时最小）。
- 如果 \(d > B\)，对手让 \(n = B\)。算法代价 \(= B\)（只租了 \(B\) 天），OPT \(= B\)。比值 \(= 1\)。但对手也可以让 \(n = d\)，算法代价 \(= (d-1) + B\)，OPT \(= B\)，比值 \(> 2\)。
综合来看，对手总能迫使确定性算法的竞争比至少为 \(2 - 1/B\)。当 \(B \to \infty\) 时趋向 2。
4.4 随机化策略
随机化可以突破确定性下界。
策略：在第 \(i\) 天（\(1 \leq i \leq B\)）以概率 \(p_i\) 购买，其中：
\[p_i = \frac{(1 - 1/B)^{i-1}}{B}\]
这不太直观。等价地，可以理解为：以均匀分布在 \([0, B]\) 上选择一个阈值 \(T\)，在第 \(\lceil T \rceil\) 天购买。
定理：上述随机化策略是 \(\frac{e}{e-1}\)-竞争的，约为 1.58。
证明思路：
对于遗忘对手选择的 \(n\)：
若 \(n < B\)： \[\mathbb{E}[\text{cost}] = \sum_{i=1}^{n} \Pr[\text{未在前 } i-1 \text{ 天购买}] \cdot 1 + \sum_{i=1}^{n} p_i \cdot (i - 1 + B)\]
通过仔细计算可以证明 \(\mathbb{E}[\text{cost}] \leq \frac{e}{e-1} \cdot \text{OPT}\)。
这是随机化最优吗？ 是的。Karlin 等人在 1994 年证明了 \(e/(e-1)\) 是随机化下界。
4.5 云计算类比
滑雪租赁问题直接对应云计算中的经典决策：
| 滑雪租赁 | 云计算 |
|---|---|
| 每天租滑雪板 | 按需实例（on-demand） |
| 一次性购买 | 预留实例（reserved instance） |
| 不知道滑多少天 | 不知道工作负载持续多久 |
| 买入价格 \(B\) | 预留实例的预付费用 |
| 确定性 2-竞争 | 在第 \(B\) 个计费周期转为预留 |
AWS、Azure 等云厂商的定价模型本质上就是这个问题。工程师在选择按需 vs 预留 vs Spot 实例时，滑雪租赁的理论结果提供了有价值的参考。
4.6 Python 模拟
import random
import math
from typing import List, Tuple
def ski_rental_deterministic(n: int, B: int) -> int:
"""确定性策略：在第 B 天购买。"""
if n < B:
return n # 只需租 n 天
else:
return (B - 1) + B # 租 B-1 天 + 购买
def ski_rental_randomized(n: int, B: int) -> int:
"""随机化策略：在 [1, B] 上按几何分布选择购买日。"""
# 等价实现：在 [0, B) 上均匀选择阈值
threshold = random.uniform(0, B)
buy_day = int(threshold) + 1 # 购买日为 ceil(threshold)
if buy_day > n:
return n # 没来得及买就结束了
else:
return (buy_day - 1) + B # 租到购买前一天 + 购买费用
def ski_rental_optimal(n: int, B: int) -> int:
"""离线最优。"""
return min(n, B)
def simulate_competitive_ratio(
B: int, trials: int = 100000
) -> Tuple[float, float]:
"""模拟确定性和随机化策略的竞争比。"""
det_worst_ratio = 0.0
rand_worst_ratio = 0.0
for n in range(1, 3 * B + 1):
opt = ski_rental_optimal(n, B)
# 确定性
det_cost = ski_rental_deterministic(n, B)
det_ratio = det_cost / opt
det_worst_ratio = max(det_worst_ratio, det_ratio)
# 随机化：蒙特卡洛估计期望代价
rand_costs = [ski_rental_randomized(n, B) for _ in range(trials)]
rand_expected = sum(rand_costs) / len(rand_costs)
rand_ratio = rand_expected / opt
rand_worst_ratio = max(rand_worst_ratio, rand_ratio)
return det_worst_ratio, rand_worst_ratio
if __name__ == "__main__":
B = 10
det_cr, rand_cr = simulate_competitive_ratio(B, trials=50000)
e_ratio = math.e / (math.e - 1)
print(f"B = {B}")
print(f"确定性竞争比（实验）：{det_cr:.4f}，理论：{2 - 1/B:.4f}")
print(f"随机化竞争比（实验）：{rand_cr:.4f}，理论：{e_ratio:.4f}")运行结果应接近：
B = 10
确定性竞争比（实验）：1.9000，理论：1.9000
随机化竞争比（实验）：1.5810，理论：1.5820五、分页问题
分页问题（Paging Problem，也称为缓存问题 Caching Problem）是在线算法理论中研究最深入的问题之一。
5.1 问题定义
系统有一个大小为 \(k\) 的快速缓存（cache）和一个无限大的慢速内存。程序依次请求页面 \(\sigma_1, \sigma_2, \ldots, \sigma_n\)。
- 如果请求的页面在缓存中：命中（hit），代价为 0。
- 如果不在缓存中：缺页（page fault），必须将该页面调入缓存，代价为 1。如果缓存已满，需要驱逐（evict）一个页面。
目标：最小化总缺页次数。
5.2 经典替换策略
| 策略 | 规则 | 竞争比 |
|---|---|---|
| LRU（Least Recently Used） | 驱逐最久未被访问的页面 | \(k\) |
| FIFO（First In First Out） | 驱逐最先进入缓存的页面 | \(k\) |
| LFU（Least Frequently Used） | 驱逐访问频率最低的页面 | 无界 |
| LIFO（Last In First Out） | 驱逐最后进入的页面 | 无界 |
| OPT（Belady） | 驱逐未来最久不会被访问的页面 | 最优（离线） |
5.3 LRU 是 k-竞争的
定理（Sleator & Tarjan, 1985）：LRU 算法是 \(k\)-竞争的，其中 \(k\) 是缓存大小。
证明思路：使用势能法（potential function method）。
定义势能 \(\Phi\) 为：LRU 缓存中有但 OPT 缓存中没有的页面数量。
对于每个请求 \(\sigma_i\)：
情况一：LRU 命中。 - LRU 代价 \(= 0\)。势能不增。
情况二：LRU 缺页，OPT 也缺页。 - LRU 代价 \(= 1\)，OPT 代价 \(\geq 1\)。 - LRU 驱逐一个页面，调入新页面。最坏情况势能增加 1。 - 但 OPT 也驱逐一个页面。如果 OPT 驱逐的恰好是 LRU 中有的页面，势能可能减少。
情况三：LRU 缺页，OPT 命中。 - LRU 代价 \(= 1\)，OPT 代价 \(= 0\)。 - 这种情况需要在势能分析中仔细处理。
通过对势能变化的精细分析，可以证明在 \(k\) 次 LRU 缺页期间，OPT 至少缺页一次。因此 LRU 是 \(k\)-竞争的。
关键引理：在 LRU 的任何长度为 \(k\) 的缺页子序列中，涉及的不同页面至少有 \(k + 1\) 个（因为 LRU 在驱逐最久未用的页面后，缓存中所有页面都是最近 \(k\) 个不同的页面）。而 OPT 的缓存大小也是 \(k\)，无法同时容纳 \(k + 1\) 个页面，所以 OPT 在这 \(k\) 次缺页中至少也产生一次缺页。
5.4 确定性下界
定理：对于缓存大小为 \(k\) 的分页问题，没有确定性在线算法能达到小于 \(k\) 的竞争比。
证明：考虑 \(k + 1\) 个不同的页面和大小为 \(k\) 的缓存。对手总是请求当前不在缓存中的那个页面。
- 在线算法：每次请求都缺页，代价为 \(n\)（总请求数）。
- OPT（Belady 算法）：每次缺页时驱逐将来最晚被请求的页面。在每 \(k\) 次在线缺页中，OPT 最多缺页一次（使用”lazy”分析）。
因此比值趋向 \(k\)。
更精细的论证：对于 \(k + 1\) 个页面的循环请求序列，OPT 使用”最远未来”策略，可以在每 \(k\) 个请求中只产生 1 次缺页。而任何确定性算法在对手自适应选择下，每次请求都缺页。
5.5 随机化：标记算法
标记算法（Marking Algorithm）是一种优雅的随机化分页算法。
算法：
初始化：所有页面未标记
对于每个请求 p：
如果 p 在缓存中：
标记 p
否则（缺页）：
如果所有缓存页面都已标记：
取消所有标记（开始新阶段）
从未标记的缓存页面中均匀随机选一个驱逐
调入 p 并标记 p定理：标记算法是 \(2H_k\)-竞争的，其中 \(H_k = 1 + 1/2 + \cdots + 1/k\) 是第 \(k\) 个调和数，约等于 \(\ln k + 0.577\)。
证明思路：
将请求序列划分为”阶段”（phase）。每个阶段从取消所有标记开始，到下一次取消标记结束。在每个阶段中，至多有 \(k\) 个不同的页面被请求（一旦超过 \(k\) 个不同页面，新阶段开始）。
在一个阶段内，设有 \(l\) 个”新”页面（上个阶段不在缓存中的页面）和 \(k - l\) 个”旧”页面。
OPT 在该阶段至少缺页 \(l\) 次（因为这 \(l\) 个新页面加上上阶段就在缓存中的页面超过了 \(k\)）。
对于标记算法，分析每个新页面导致驱逐未标记旧页面的概率。第 \(j\) 个新页面到达时，未标记的旧页面有 \(k - l\) 到 \(k - l - (j - 1)\) 个。通过仔细的概率分析，期望缺页数可以用调和级数界定。
5.6 随机化下界
定理（Fiat et al., 1991）：对于缓存大小为 \(k\) 的分页问题，任何随机化在线算法（对遗忘对手）的竞争比至少为 \(H_k\)。
这通过 Yao 原理证明（我们将在第八节详细介绍）。
5.7 Python 模拟
import random
from collections import OrderedDict
from typing import List, Tuple
class LRUCache:
"""LRU 分页算法。"""
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
self.faults = 0
def request(self, page: int) -> bool:
if page in self.cache:
self.cache.move_to_end(page)
return True # 命中
else:
self.faults += 1
if len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # 驱逐最久未用
self.cache[page] = True
return False # 缺页
class FIFOCache:
"""FIFO 分页算法。"""
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
self.faults = 0
def request(self, page: int) -> bool:
if page in self.cache:
return True
else:
self.faults += 1
if len(self.cache) >= self.capacity:
self.cache.popitem(last=False)
self.cache[page] = True
return False
class MarkingCache:
"""标记算法（随机化）。"""
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # page -> marked
self.faults = 0
def request(self, page: int) -> bool:
if page in self.cache:
self.cache[page] = True # 标记
return True
else:
self.faults += 1
if len(self.cache) >= self.capacity:
# 检查是否所有页面都已标记
unmarked = [p for p, m in self.cache.items() if not m]
if not unmarked:
# 新阶段：取消所有标记
for p in self.cache:
self.cache[p] = False
unmarked = list(self.cache.keys())
# 随机驱逐一个未标记页面
victim = random.choice(unmarked)
del self.cache[victim]
self.cache[page] = True # 调入并标记
return False
class BeladyCache:
"""Belady 离线最优算法。"""
def __init__(self, capacity: int, sequence: List[int]):
self.capacity = capacity
self.sequence = sequence
self.cache = set()
self.faults = 0
self.pos = 0
def request(self, page: int) -> bool:
self.pos += 1
if page in self.cache:
return True
else:
self.faults += 1
if len(self.cache) >= self.capacity:
# 驱逐未来最晚使用的页面
farthest = -1
victim = None
for p in self.cache:
try:
next_use = self.sequence[self.pos:].index(p)
except ValueError:
next_use = float('inf')
if next_use > farthest:
farthest = next_use
victim = p
self.cache.discard(victim)
self.cache.add(page)
return False
def generate_adversarial_sequence(
k: int, length: int
) -> List[int]:
"""生成对确定性算法不利的序列：k+1 个页面的循环。"""
pages = list(range(k + 1))
return [pages[i % (k + 1)] for i in range(length)]
def paging_experiment(k: int, length: int, trials: int = 100):
"""分页算法竞争比实验。"""
seq = generate_adversarial_sequence(k, length)
# 确定性算法：运行一次
lru = LRUCache(k)
fifo = FIFOCache(k)
belady = BeladyCache(k, seq)
for page in seq:
lru.request(page)
fifo.request(page)
belady.request(page)
# 随机化算法：多次运行取期望
marking_total = 0
for _ in range(trials):
marking = MarkingCache(k)
for page in seq:
marking.request(page)
marking_total += marking.faults
opt_faults = belady.faults
print(f"缓存大小 k = {k}，序列长度 = {length}")
print(f"OPT (Belady) 缺页数：{opt_faults}")
print(f"LRU 缺页数：{lru.faults}，比值：{lru.faults/opt_faults:.2f}")
print(f"FIFO 缺页数：{fifo.faults}，比值：{fifo.faults/opt_faults:.2f}")
marking_avg = marking_total / trials
print(f"Marking 平均缺页数：{marking_avg:.1f}，"
f"比值：{marking_avg/opt_faults:.2f}")
print(f"理论确定性下界：{k}，随机化下界 H_k ≈ "
f"{sum(1/i for i in range(1, k+1)):.2f}")
if __name__ == "__main__":
paging_experiment(k=4, length=1000)六、k-server 问题
k-server 问题是在线计算中最深刻、最具影响力的问题之一，被称为”在线算法的圣杯”。
6.1 问题定义
给定一个度量空间 \((M, d)\)，其中 \(d\) 是度量（距离函数），\(k\) 个服务器分布在空间中的不同点上。请求序列 \(\sigma_1, \sigma_2, \ldots\) 依次到达，每个请求 \(\sigma_i\) 是空间中的一个点。
对于每个请求，必须移动某个服务器到该点来服务它。代价是该服务器移动的距离。目标是最小化总移动距离。
注意：分页问题是 k-server 问题的特例，其中度量空间是均匀度量（所有不同点之间距离相等）。
6.2 k-server 猜想
猜想（Manasse, McGeoch, Sleator, 1988）：对于任何度量空间，存在 \(k\)-竞争的确定性在线算法。
这个猜想提出了三十多年，至今未被完全证明（在一般度量空间上）。
已知结果：
| 结果 | 竞争比 | 作者/年份 |
|---|---|---|
| 线段上的 2 个服务器 | 2-竞争 | Manasse et al., 1988 |
| 树上的 k-server | \(k\)-竞争 | Chrobak & Larmore, 1991 |
| 一般度量空间 | \((2k-1)\)-竞争 | Koutsoupias & Papadimitriou, 1995 |
| 确定性下界 | \(k\) | Manasse et al., 1988 |
| 随机化下界 | \(\Omega(\log k)\) | Bartal et al. |
6.3 Work Function Algorithm
Work Function Algorithm（WFA）是目前已知对一般度量空间最好的确定性 k-server 算法。
定义：对于一个配置 \(C\)（\(k\) 个服务器的位置集合）和请求序列 \(\sigma_1, \ldots, \sigma_t\)，工作函数 \(w_t(C)\) 是服务前 \(t\) 个请求的最小代价，使得最终服务器配置恰好为 \(C\)。
算法： 当请求 \(\sigma_{t+1}\) 到达时，选择服务器 \(s\) 移动到 \(\sigma_{t+1}\)，使得下式最小化：
\[w_t(C') + d(s, \sigma_{t+1})\]
其中 \(C'\) 是将服务器 \(s\) 移动到 \(\sigma_{t+1}\) 后的配置。
直觉上，WFA 在”利用历史信息”和”响应当前请求”之间做了最佳权衡。
定理（Koutsoupias & Papadimitriou, 1995）：WFA 在任意度量空间上是 \((2k-1)\)-竞争的。
k-server 猜想等价于证明 WFA 是 \(k\)-竞争的。这已在一些特殊度量空间上得到验证，但一般情况仍然开放。
6.4 双服务器问题的代码示例
def two_server_greedy(
requests: List[float],
s1_init: float,
s2_init: float
) -> Tuple[float, List[Tuple[float, float]]]:
"""贪心策略：总是移动较近的服务器。"""
s1, s2 = s1_init, s2_init
total_cost = 0.0
history = [(s1, s2)]
for r in requests:
d1 = abs(s1 - r)
d2 = abs(s2 - r)
if d1 <= d2:
total_cost += d1
s1 = r
else:
total_cost += d2
s2 = r
history.append((s1, s2))
return total_cost, history
def two_server_optimal_dp(
requests: List[float],
s1_init: float,
s2_init: float
) -> float:
"""2-server 离线最优（动态规划）。
状态：(当前请求索引, 另一个服务器的位置)。
一个服务器总在上一个请求处。
"""
n = len(requests)
if n == 0:
return 0.0
# memo[i][pos] = 服务完第 i 个请求后，
# 非活跃服务器在 pos 时的最小代价
# pos 只可能是初始位置或之前的请求位置
INF = float('inf')
# 可能的位置集合
positions = {s1_init, s2_init}
for r in requests:
positions.add(r)
positions = sorted(positions)
pos_idx = {p: i for i, p in enumerate(positions)}
# DP: dp[other_pos] = 到目前为止的最小代价
# "active"服务器在 requests[i-1]（或初始位置）
# "other"服务器在 other_pos
# 初始状态：
# 如果移动 s1 去服务 requests[0]，other = s2
# 如果移动 s2 去服务 requests[0]，other = s1
prev = {}
r0 = requests[0]
cost1 = abs(s1_init - r0) # 移动 s1
cost2 = abs(s2_init - r0) # 移动 s2
prev[s2_init] = min(prev.get(s2_init, INF), cost1)
prev[s1_init] = min(prev.get(s1_init, INF), cost2)
for i in range(1, n):
curr = {}
r = requests[i]
prev_r = requests[i - 1]
for other_pos, cost in prev.items():
# 选项一：移动活跃服务器（在 prev_r）到 r
move_cost = abs(prev_r - r)
new_other = other_pos
key = new_other
if key not in curr or cost + move_cost < curr[key]:
curr[key] = cost + move_cost
# 选项二：移动另一个服务器（在 other_pos）到 r
move_cost = abs(other_pos - r)
new_other = prev_r
key = new_other
if key not in curr or cost + move_cost < curr[key]:
curr[key] = cost + move_cost
prev = curr
return min(prev.values()) if prev else 0.0七、在线二分搜索与单向交易
7.1 问题定义
你持有一个资产，需要在某个时间卖出。价格序列 \(p_1, p_2, \ldots, p_n\) 逐天揭示，你已知价格范围 \([m, M]\)（\(m > 0\)），但不知道具体的价格序列。
每天你可以选择卖出（获得当天价格）或持有。一旦卖出，不可撤销。如果到最后一天还没卖出，被迫以最后一天的价格卖出。
目标：最大化卖出价格（等价于最小化”遗憾”——最高价与实际卖出价的差距）。
7.2 确定性策略
阈值策略（Reservation Price Policy）：预设一个阈值 \(p^*\)，当价格首次达到 \(p^*\) 时卖出。
最优阈值：\(p^* = \sqrt{m \cdot M}\)（几何均值）。
竞争比：\(\sqrt{M/m}\)。
证明：设 \(\phi = M/m\) 为价格波动比。
情况一：最高价 \(\geq p^* = \sqrt{mM}\)。算法卖出价 \(\geq p^*\)，OPT 卖出价 \(\leq M\)。比值 \(\leq M / \sqrt{mM} = \sqrt{M/m} = \sqrt{\phi}\)。
情况二：最高价 \(< p^*\)。算法被迫在最后以某个价格 \(\geq m\) 卖出。OPT 也不超过 \(p^* = \sqrt{mM}\)。比值 \(\leq \sqrt{mM} / m = \sqrt{M/m} = \sqrt{\phi}\)。
7.3 随机化策略
可以通过随机选择阈值来改进。设 \(\phi = M/m\)，将 \([m, M]\) 划分为若干区间，在区间上随机选择卖出阈值。
最优随机化策略可以达到 \(O(\log \phi)\) 竞争比，远优于确定性的 \(\sqrt{\phi}\)。
7.4 与最优停止理论的联系
在线二分搜索与经典的”秘书问题”有深刻联系：
| 问题 | 在线二分搜索 | 秘书问题 |
|---|---|---|
| 信息 | 知道价格范围 | 知道候选人数量 |
| 决策 | 何时卖出 | 何时录用 |
| 不可撤销 | 卖出后不能反悔 | 录用/拒绝不可撤销 |
| 最优策略 | 阈值策略 | 观察 \(n/e\) 个后选最好的 |
两者都属于 最优停止理论（optimal stopping theory） 的范畴。核心思想：先探索（积累信息），再利用（做出决策）。
八、Yao 原理
8.1 背景
Yao 原理（Yao’s Minimax Principle, 1977）是证明随机化算法下界最强大的工具。它将博弈论中的 minimax 定理应用到算法分析中。
8.2 minimax 定理
冯·诺伊曼的 minimax 定理（1928）指出：在零和博弈中，
\[\max_q \min_A \mathbb{E}_{q}[\text{cost}(A, \sigma)] = \min_A \max_q \mathbb{E}_{q}[\text{cost}(A, \sigma)]\]
其中 \(A\) 是（混合）策略，\(q\) 是输入上的（混合）分布。
8.3 Yao 原理的陈述
定理（Yao, 1977）：设 \(P\) 是在线问题的一个实例集合。则：
\[\min_{\text{随机化} A} \max_{\sigma \in P} \frac{\mathbb{E}[A(\sigma)]}{\text{OPT}(\sigma)} \geq \max_{\text{分布} q \text{ on } P} \min_{\text{确定性} A} \frac{\mathbb{E}_q[A(\sigma)]}{\mathbb{E}_q[\text{OPT}(\sigma)]}\]
直觉：
- 左边：随机化算法对最坏情况输入的竞争比。
- 右边：确定性算法对随机输入的竞争比。
要证明随机化下界 \(c\)，只需找到一个输入分布 \(q\)，使得 任何确定性算法 在 \(q\) 下的期望竞争比至少为 \(c\)。
8.4 应用：分页问题的随机化下界
使用 Yao 原理证明分页的 \(H_k\) 随机化下界。
输入分布：在 \(k + 1\) 个页面上均匀随机选择每次请求。
分析：
对于任何确定性算法，当前缓存中有 \(k\) 个页面。下一次请求是缓存外页面的概率为 \(1/(k+1)\)（因为有 \(k+1\) 个页面，缓存只能存 \(k\) 个）。
嗯，更精确地说：在上述均匀随机输入下，OPT 的期望缺页率和任何确定性算法的期望缺页率的比值可以精确计算，最终得到 \(H_k\) 的下界。
具体地，通过分析 \(k+1\) 个页面的均匀随机请求序列，可以证明：
- 任何确定性算法的期望缺页率 \(\geq 1/(k+1)\)。
- OPT 的期望缺页率 \(\leq 1/(k(k+1))\) 乘以某个因子。
通过仔细的组合论证，最终得到竞争比下界为 \(H_k\)。
8.5 Yao 原理的方法论意义
Yao 原理的威力在于将”随机化算法的最坏情况分析”转化为”确定性算法在随机输入上的平均情况分析”。后者通常更容易处理。
证明随机化下界的步骤：
1. 构造一个"难"的输入分布 q
2. 证明任何确定性算法在 q 下的期望代价 >= c * E_q[OPT]
3. 由 Yao 原理，随机化下界 >= c九、在线负载均衡
9.1 问题定义
有 \(m\) 台机器和 \(n\) 个作业在线到达。第 \(j\) 个作业的处理时间为 \(p_j\)。每个作业到达时必须立即分配给某台机器，不可迁移。
目标：最小化 makespan（最大机器负载）。
\[\text{makespan} = \max_{i=1}^{m} \sum_{j \in S_i} p_j\]
其中 \(S_i\) 是分配给机器 \(i\) 的作业集合。
9.2 贪心策略
贪心（Greedy / List Scheduling）：将作业分配给当前负载最小的机器。
定理（Graham, 1966）：贪心算法是 \((2 - 1/m)\)-竞争的。
证明思路：
设最终 makespan 由机器 \(i\) 达到，其负载为 \(L_i\)。设机器 \(i\) 上最后分配的作业处理时间为 \(p_j\)。
在分配 \(p_j\) 之前，机器 \(i\) 的负载是所有机器中最小的，因此： \[L_i - p_j \leq \frac{1}{m} \sum_{j'} p_{j'}\]
又 \(\text{OPT} \geq \frac{1}{m} \sum_{j'} p_{j'}\) 且 \(\text{OPT} \geq p_j\)。
所以： \[L_i = (L_i - p_j) + p_j \leq \text{OPT} + \text{OPT} \cdot (1 - 1/m) = (2 - 1/m) \cdot \text{OPT}\]
等等，更准确地说：\(L_i - p_j \leq \frac{1}{m} \sum p_{j'} \leq \text{OPT}\)。加上 \(p_j \leq \text{OPT}\)，得到 \(L_i \leq 2 \cdot \text{OPT}\)。要得到 \((2 - 1/m)\)，需要更精细的分析：\(L_i - p_j \leq (1 - 1/m) \cdot \text{OPT}\)，因为平均负载不超过 OPT，而机器 \(i\) 在分配前是最轻的。
9.3 改进策略
- LPT（Longest Processing Time First）：先对作业按处理时间降序排列。这是离线算法，达到 \((4/3 - 1/(3m))\)-竞争。
- 对于在线问题，更复杂的算法可以达到接近 \(1.9\) 的竞争比。
十、广告分配与 Adwords 问题
10.1 问题定义
搜索引擎广告竞价模型：有 \(n\) 个广告商，每个广告商 \(i\) 有预算 \(B_i\)。查询序列在线到达，每个查询 \(q\) 有一组出价 \(b_{iq}\)（广告商 \(i\) 对查询 \(q\) 的出价）。
算法需要将每个查询分配给一个广告商（或不分配），使得总收入最大化，同时不超过任何广告商的预算。
10.2 贪心与 BALANCE 算法
贪心：将查询分配给出价最高的广告商。竞争比 \(= 1/2\)。
BALANCE 算法（Mehta et al., 2007）：
当所有出价相等（\(b_{iq} \in \{0, 1\}\)）时，将查询分配给剩余预算比例最高的广告商。
定理：BALANCE 算法是 \((1 - 1/e)\)-竞争的，约 0.632。这是最优的。
一般情况（出价不等）：
使用指数权重策略。对于广告商 \(i\) 对查询 \(q\) 的有效出价：
\[\text{score}_{iq} = b_{iq} \cdot (1 - e^{-\psi(f_i)})\]
其中 \(f_i\) 是广告商 \(i\) 已花费的预算比例，\(\psi\) 是一个精心设计的函数。
10.3 与在线匹配的关系
Adwords 问题是在线二部匹配（online bipartite matching）的加权推广。Karp、Vazirani 和 Vazirani 在 1990 年证明了在线二部匹配的 \((1 - 1/e)\) 竞争比上界，使用一种优雅的随机化算法 RANKING。
def balance_algorithm(
queries: List[int],
budgets: List[float],
bids: List[List[float]]
) -> Tuple[float, List[int]]:
"""BALANCE 算法（简化版，等价出价）。
queries: 查询序列
budgets: 各广告商的预算
bids: bids[i][q] = 广告商 i 对查询 q 的出价
返回：(总收入, 分配方案)
"""
n_advertisers = len(budgets)
remaining = list(budgets)
total_revenue = 0.0
assignments = []
for q in queries:
best_advertiser = -1
best_fraction = -1.0
for i in range(n_advertisers):
if bids[i][q] > 0 and remaining[i] >= bids[i][q]:
fraction = remaining[i] / budgets[i]
if fraction > best_fraction:
best_fraction = fraction
best_advertiser = i
if best_advertiser >= 0:
bid = bids[best_advertiser][q]
remaining[best_advertiser] -= bid
total_revenue += bid
assignments.append(best_advertiser)
else:
assignments.append(-1) # 未分配
return total_revenue, assignments十一、TCP 拥塞控制的竞争分析视角
11.1 AIMD 作为在线算法
TCP 的加法增/乘法减（AIMD）拥塞控制可以用在线算法的语言来理解：
- 输入：网络状况（拥塞信号）逐步揭示。
- 决策：发送窗口大小。
- 不可撤销性：已发送的数据包不能回收。
- 目标：最大化吞吐量，同时避免拥塞崩溃。
11.2 竞争分析视角
将 TCP 拥塞控制建模为一个在线优化问题：
- 代价函数：\(\alpha \cdot \text{丢包率} + \beta \cdot (1/\text{吞吐量})\)。
- OPT：知道整个网络状况的理想算法。
- 在线算法：基于丢包信号的 AIMD。
Karp（2001）等人的分析表明，AIMD 在某些简化的网络模型下具有 \(O(1)\) 的竞争比。
11.3 从理论到实践
竞争分析的精确性在 TCP 中有所折损，因为实际网络不完全是最坏情况对手。但竞争分析提供的思维方式——考虑最坏情况、设计鲁棒策略——深刻影响了网络协议的设计。
十二、工程实践与反思
12.1 工程注意事项
| 问题 | 常见陷阱 | 建议 |
|---|---|---|
| 缓存替换 | 盲目使用 LRU，忽略实际访问模式 | 监控命中率，必要时结合频率信息（ARC、W-TinyLFU） |
| 云实例选择 | 全用按需或全用预留 | 滑雪租赁分析：工作负载稳定部分用预留，突发部分用按需 |
| 负载均衡 | 简单轮询，不考虑异构机器 | 加权策略或 power-of-two-choices |
| 广告竞价 | 贪心分配，预算耗尽过早 | BALANCE/MSVV 算法，考虑预算消耗速度 |
| 数据库索引 | 为所有查询建索引 | 在线学习哪些索引最有价值，定期重评估 |
| 限流策略 | 固定速率限制 | 自适应限流，考虑历史请求模式 |
12.2 竞争比的局限性
竞争分析虽然优雅，但有几个实际局限：
过于悲观：最坏情况可能极端罕见。LRU 在实际中远好于 \(k\)-竞争的理论预测，因为真实访问模式具有局部性。
加法常数问题：\(\alpha\) 可能很大，在实际规模的问题中不可忽略。
对手模型过强：现实中”对手”通常不是完全恶意的。
改进方向：
- 比较分析（comparative analysis）：比较两个在线算法，而非与 OPT 比较。
- 资源增强分析（resource augmentation）：给在线算法更多资源（例如更大的缓存），看能否匹配 OPT。
- 参数化竞争比：在输入具有某些结构属性时分析竞争比。
- 学习增强（learning-augmented）算法：利用机器学习预测辅助在线决策。
12.3 学习增强算法
近年来最热门的方向是 学习增强在线算法（learning-augmented online algorithms）。核心思想：
- 用机器学习模型预测未来输入。
- 设计算法在预测正确时表现极好（一致性，consistency），在预测错误时仍有保障（鲁棒性，robustness）。
例如，对于滑雪租赁问题：
- 预测模型估计你会滑 \(\hat{n}\) 天。
- 如果 \(\hat{n} < B\)，不买。如果 \(\hat{n} \geq B\)，立即买。
- 结合随机化，可以在预测误差 \(\eta = |n - \hat{n}|\) 上参数化竞争比。
def ski_rental_learning_augmented(
n: int, B: int, prediction: int, lam: float = 0.5
) -> int:
"""学习增强滑雪租赁策略。
lam: 信任预测的程度 (0 = 纯在线, 1 = 完全信任预测)
"""
# 如果完全信任预测
if prediction >= B:
buy_day = 1 # 预测要滑很久，立即买
else:
buy_day = n + 1 # 预测要滑不久，不买
# 混合策略：以概率 lam 使用预测，1 - lam 使用经典策略
if random.random() < lam:
# 使用预测
if buy_day <= n:
return B # 第一天买
else:
return n # 只租
else:
# 经典 2-竞争策略
return ski_rental_deterministic(n, B)12.4 完整的竞争比实验框架
import random
import math
from typing import Dict, List
def comprehensive_experiment():
"""综合竞争分析实验。"""
print("=" * 60)
print("竞争分析综合实验")
print("=" * 60)
# 实验一：滑雪租赁
print("\n--- 实验一：滑雪租赁 ---")
for B in [5, 10, 20, 50]:
det_ratios = []
rand_ratios = []
for n in range(1, 5 * B + 1):
opt = min(n, B)
det_cost = ski_rental_deterministic(n, B)
det_ratios.append(det_cost / opt)
rand_costs = [
ski_rental_randomized(n, B) for _ in range(10000)
]
rand_ratios.append(sum(rand_costs) / len(rand_costs) / opt)
print(f" B={B:3d}: 确定性最坏={max(det_ratios):.3f} "
f"(理论 {2-1/B:.3f}), "
f"随机化最坏={max(rand_ratios):.3f} "
f"(理论 {math.e/(math.e-1):.3f})")
# 实验二：分页
print("\n--- 实验二：分页（对抗序列） ---")
for k in [3, 4, 5, 8]:
length = 500
seq = generate_adversarial_sequence(k, length)
lru = LRUCache(k)
belady = BeladyCache(k, seq)
for page in seq:
lru.request(page)
belady.request(page)
ratio = lru.faults / max(belady.faults, 1)
h_k = sum(1.0 / i for i in range(1, k + 1))
print(f" k={k}: LRU/OPT={ratio:.2f} "
f"(确定性下界 {k}, 随机化下界 H_{k}={h_k:.2f})")
# 实验三：分页（真实 LRU 友好序列）
print("\n--- 实验三：分页（局部性序列） ---")
for k in [4, 8, 16]:
# 模拟具有时间局部性的访问模式
seq = []
working_set = list(range(k))
for _ in range(1000):
if random.random() < 0.8:
seq.append(random.choice(working_set))
else:
seq.append(random.randint(0, 3 * k))
lru = LRUCache(k)
belady = BeladyCache(k, seq)
for page in seq:
lru.request(page)
belady.request(page)
ratio = lru.faults / max(belady.faults, 1)
print(f" k={k}: LRU/OPT={ratio:.2f} "
f"(远好于最坏情况 {k})")
if __name__ == "__main__":
comprehensive_experiment()12.5 个人观点
写到系列的最后一篇，我想分享几点对在线算法和竞争分析的个人看法。
竞争分析作为思维框架：即使不直接应用竞争比的精确值，竞争分析的思维方式在工程中极其有价值。它逼迫你思考：
- 你的算法在最坏情况下会多差？ 这比平均情况分析更能发现系统的脆弱性。
- 信息的价值是什么？ 竞争比衡量的就是”不知道未来”的代价。如果代价很高，投资于预测（缓存、预取、容量规划）就更值得。
- 鲁棒性 vs 最优性的权衡。 完美优化通常依赖准确的预测；鲁棒算法在所有情况下都不会太差。工程师需要在两者之间找到平衡。
理论与实践的张力：竞争分析的最坏情况可能过于悲观。LRU 在实践中表现出色，因为真实工作负载具有局部性——这不是最坏情况。但理论的价值在于：当你不能保证输入是”友好的”时，竞争分析给出了你能依赖的底线。
在线算法无处不在：当我们审视整个系列，会发现在线算法的影子无处不在。页面置换是分页问题，负载均衡是在线调度，TCP 拥塞控制是带宽分配……理解在线算法，就是理解”在不确定性中做决策”的本质。
最好的算法不是全知全能的，而是在信息不完整时仍能做出好决策的。
这也许就是算法教给我们的最深刻的工程智慧。
附录 A：竞争分析核心结论速查表
| 问题 | 确定性竞争比 | 随机化竞争比 | 经典算法 |
|---|---|---|---|
| 滑雪租赁 | 2 | \(e/(e-1) \approx 1.58\) | 第 \(B\) 天购买 / 几何分布 |
| 分页（缓存大小 \(k\)） | \(k\) | \(\Theta(\log k)\) | LRU / 标记算法 |
| k-server（一般度量） | \(\leq 2k-1\)（猜想 \(k\)） | \(O(\text{poly}(\log k))\) | WFA |
| 在线负载均衡（\(m\) 台机器） | \(2 - 1/m\) | \(\Theta(\log m / \log\log m)\) | 贪心 |
| 在线二部匹配 | \(1/2\) | \(1 - 1/e \approx 0.632\) | RANKING |
| Adwords | \(1/2\) | \(1 - 1/e\) | BALANCE / MSVV |
| 单向交易（\(\phi = M/m\)） | \(\sqrt{\phi}\) | \(O(\log \phi)\) | 阈值策略 |
附录 B：符号表
| 符号 | 含义 |
|---|---|
| \(\sigma\) | 输入序列 |
| \(A(\sigma)\) | 算法 \(A\) 对输入 \(\sigma\) 的代价 |
| \(\text{OPT}(\sigma)\) | 离线最优对输入 \(\sigma\) 的代价 |
| \(c_A\) | 算法 \(A\) 的竞争比 |
| \(B\) | 滑雪租赁中的购买价格 |
| \(k\) | 缓存大小 / 服务器数量 |
| \(H_k\) | 第 \(k\) 个调和数 \(\sum_{i=1}^{k} 1/i\) |
| \(\phi\) | 价格波动比 \(M/m\) |
附录 C：进一步阅读
- Borodin, A., & El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cambridge University Press.——在线算法领域的经典教科书。
- Sleator, D. D., & Tarjan, R. E. (1985). Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2), 202-208.——竞争分析的开创性论文。
- Karlin, A. R., et al. (1994). Competitive randomized algorithms for nonuniform problems. Algorithmica, 11(6), 542-571.——滑雪租赁随机化最优解。
- Koutsoupias, E., & Papadimitriou, C. H. (1995). On the k-server conjecture. Journal of the ACM, 42(5), 971-983.——WFA 的 \((2k-1)\)-竞争性证明。
- Mehta, A., et al. (2007). AdWords and generalized online matching. Journal of the ACM, 54(5), 22.——Adwords 问题的 BALANCE 算法。
- Lykouris, T., & Vassilvitskii, S. (2021). Competitive caching with machine learned advice. Journal of the ACM, 68(4), 1-25.——学习增强在线算法的代表工作。
- Yao, A. C. (1977). Probabilistic computations: Toward a unified measure of complexity. FOCS, 222-227.——Yao 原理的原始论文。
- Manasse, M. S., McGeoch, L. A., & Sleator, D. D. (1988). Competitive algorithms for server problems. STOC, 322-333.——k-server 问题与猜想。
算法系列导航：上一篇：随机化算法：当运气成为武器 | 本篇是系列最后一篇