在线算法详解

关键词速览

关键词	解释
竞争分析	在线算法与最优离线算法的比较框架
竞争比	在线算法性能与最优算法的比值上界
最优在线决策	基于部分信息的顺序决策问题
Secretary Problem	经典的选择最优候选人问题
在线装箱	物品序列的在线分配
负载均衡	任务分配到多台机器
Ski Rental	在线租买决策问题
对抗性输入	分析在线算法的输入模型
随机化在线	使用随机性的在线算法
Yao原理	期望竞争比的下界证明

摘要

在线算法研究在信息不完整条件下进行决策的理论与实践。与离线算法拥有全部输入不同，在线算法必须在收到每个输入后立即做出不可撤回的决定。本文系统阐述竞争分析框架，通过经典案例（秘书问题、在线装箱、负载均衡、Ski Rental问题）展示问题建模与算法设计技术，并探讨随机化在线算法的优势。在线算法的思想广泛应用于操作系统调度、网络路由、搜索引擎排序和推荐系统等AI领域。

---

1. 在线算法的基本框架

1.1 在线与离线问题的对比

特征	离线算法	在线算法
输入	完整输入提前已知	逐步到达
决策时机	全局优化后决策	即时决策
后悔度	无	有
分析框架	近似比/精确性	竞争分析

核心挑战：在线算法必须在信息不完全时做出选择，且决策通常不可撤销。

1.2 竞争分析的定义

竞争分析是在线算法性能评估的标准方法。设 $\text{ALG}(I)$ 为算法 $\mathcal{A}$ 在输入 $I$ 上的代价，$\text{OPT}(I)$ 为最优离线算法在相同输入上的代价。

竞争比的定义：

一个在线算法 $\mathcal{A}$ 是 $c$-竞争的，当且仅当存在常数 $\alpha$ 使得

$$\text{ALG}(I)\le c\cdot \text{OPT}(I)+\alpha$$

对所有输入 $I$ 成立。

Note

通常关注渐进竞争比，即忽略常数 $\alpha$，要求 $\text{ALG}(I)\le c\cdot \text{OPT}(I)$ 对足够大的输入成立。

最小化 vs 最大化问题：

• 最小化问题：$\text{ALG}\le c\cdot \text{OPT}$（$c\ge 1$）
• 最大化问题：$\text{ALG}\ge \frac{1}{c}\cdot \text{OPT}$（$c\ge 1$）

1.3 输入模型分类

模型	描述	例子
对抗性模型	输入由敌手生成，最坏情况	经典竞争分析
随机模型	输入服从已知分布	平均情况分析
确定性子分布	任意分布的输入	通用在线算法

---

2. 秘书问题：最优停止理论

2.1 问题描述

秘书问题（Secretary Problem / Best Choice Problem）是最优停止理论的经典案例：

问题设定：

• 面试 $n$ 个候选人
• 候选人以随机顺序到达
• 每次面试后必须立即决定是否录用
• 一旦拒绝不可召回
• 目标：选择最佳候选人的概率最大

2.2 最优策略：观察-选择规则

def secretary_strategy(n):
    """
    观察前 r 个候选人，但不选择
    从第 r+1 个开始，选择第一个比之前所有候选人都好的
    """
    r = int(n / math.e)  # 最优观察期长度
    
    best_observed = -∞
    for i in range(1, n + 1):
        rating = get_candidate_rating(i)
        
        if i <= r:
            # 观察期：只记录，不选择
            best_observed = max(best_observed, rating)
        else:
            # 选择期：选择第一个超过历史最佳的
            if rating > best_observed:
                return i  # 选择第 i 个候选人
    
    # 如果没有更好的，选择最后一个
    return n

2.3 最优观察期分析

定理：当 $r=\lfloor n/e\rfloor$ 时，成功概率收敛到 $1/e\approx 0.3679$。

推导：

设选中的候选人是第 $j$ 个，且被选中当且仅当它是最佳且 $j>r$。

$$P(\text{成功})=\sum _{j=r+1}^{n}P(\text{第 }j\text{ 个是最佳})\cdot P(\text{选择第 }j\text{ 个}|\text{第 }j\text{ 个是最佳})$$ $$=\sum _{j=r+1}^n\frac{1}{n}\cdot \frac{r}{j-1}=\frac{r}{n}\sum _{j=r+1}^n\frac{1}{j-1}$$

当 $n$ 足够大且 $r/n\to x$ 时，

$$\underset{n\to \infty }{\lim }P(\text{成功})=-x\ln x$$

最大化 $-x\ln x$ 得到 $x=1/e$，此时成功概率为 $1/e$。

Example

招聘场景：面试100人，观察前37人不录用，从第38人开始录用第一个比之前所有都优秀的人，成功概率约36.8%。

---

3. 在线装箱问题

3.1 问题定义

在线装箱（Online Bin Packing）问题：

• 输入：物品序列 $a_1,a_1,...,a_n$，每个物品大小 $s_i\in (0,1]$
• 目标：将物品装入最少数量的箱子（容量为1）

3.2 First Fit Decreasing (FFD)

FFD是一个经典的离线近似算法：

def ffd(items):
    """
    1. 按物品大小降序排列
    2. 依次使用 First Fit 策略装箱
    """
    items.sort(reverse=True)
    bins = []
    
    for size in items:
        # 找第一个能容纳该物品的箱子
        placed = False
        for bin in bins:
            if bin.current_load + size <= 1:
                bin.add(size)
                placed = True
                break
        
        if not placed:
            # 创建新箱子
            new_bin = Bin()
            new_bin.add(size)
            bins.append(new_bin)
    
    return len(bins)

FFD的近似比：$11/9\cdot OPT+6/9$

3.3 在线装箱算法

Next Fit (NF)：

• 打开一个箱子，当前物品装入
• 如果下一个物品装不下，开新箱
• 简单但竞争比差：$2$

Best Fit (BF)：

• 将物品放入能容纳它且当前负载最满的箱子
• 竞争比：$1.7$

First Fit (FF)：

• 从第一个箱子开始，找第一个能容纳物品的
• 竞争比：$1.7$

Harmonic Fit：

• 按大小分类处理，避免大物品进入小箱子
• 竞争比：$\mathrm{1.691...}$

3.4 Asymptotic Approximation

对于大箱子数，关注渐近竞争比：

$$\underset{OPT\to \infty }{\lim }\frac{ALG}{OPT}$$

Harmonic H 的渐近竞争比：

$$H_k=\sum _{i=1}^{k-1}\frac{1}{i}\approx \ln k$$

---

4. 在线负载均衡

4.1 问题定义

在线负载均衡（Online Load Balancing）：

• $m$ 台机器
• 作业序列 $J_1,J_2,...,J_n$ 依次到达
• 作业 $j$ 有处理时间 $p_j$
• 目标：最小化最大机器负载（makespan）

4.2 Greedy策略分析

Graham的LPT算法（离线）：按处理时间降序分配

在线贪婪算法（List Scheduling, LS）：

def list_scheduling(machines, jobs):
    for job in jobs:
        # 分配到当前负载最小的机器
        min_machine = min(machines, key=lambda m: m.load)
        min_machine.add(job)
    return max(m.load for m in machines)

竞争比：$2-\frac{1}{m}$（对任意 $m$ 台机器）

4.3 竞争比下界

定理：任何确定性在线算法的竞争比至少为 $2-\frac{1}{m}$。

构造：前 $m-1$ 个作业大小为 1，最后一个作业大小为 $m$。

• 最优离线：可以找到平衡分配，makespan = $m/(m-1)+1<3$
• 在线算法：前 $m-1$ 个作业分散到 $m-1$ 台机器，大作业必须放到某台已有负载1的机器，makespan = $1+m$

比值趋于 2。

---

5. Ski Rental问题

5.1 问题描述

Ski Rental 问题模拟在线租买决策：

问题设定：

• 滑雪 $d$ 天（$d$ 未知）
• 每天租金 $r$ 元，或一次性购买 $p$ 元
• 每天结束后决定是否继续滑雪
• 目标：最小化总花费

5.2 最优在线策略

关键洞察：存在一个最优的”买断点”。

def ski_rental(r, p):
    """
    策略：在租了 p/r 天后购买装备
    """
    days_rented = 0
    
    while still_skiing():
        day_cost = r
        days_rented += 1
        
        if days_rented * r >= p:
            # 购买
            total_cost = p
            break
        else:
            # 继续租
            total_cost = days_rented * r
    
    return total_cost

竞争比分析：

设最优租期为 $d^{\ast }$ 天。

• 若 $d^{\ast }\le p/r$：只租不买，花费 $d^{\ast }r$，在线算法同
• 若 $d^{\ast }>p/r$：最优为购买，花费 $p$

在线算法花费：$\min (d^{\ast }r,p+(p/r-1)r)<2p-r$

竞争比：$2-r/p<2$

5.3 贝叶斯扩展

若 $d$ 服从分布 $F$，可以计算最优策略的期望竞争比。

---

6. 随机化在线算法

6.1 随机化的优势

确定性在线算法在某些问题上无法改进，但随机化可以打破对称性：

例子：在线匹配

def randomized_matching(G):
    """
    在随机顺序下使用贪心策略
    """
    random.shuffle(G.edges())
    M = ∅
    
    for (u, v) in edges:
        if u not in M and v not in M:
            M.add((u, v))
    
    return M

竞争比：$O(\log n)$ vs 确定性算法的 $O(\sqrt{n})$

6.2 Yao原理：期望竞争比下界

Yao原理连接随机化在线算法和输入分布：

一个随机化算法 $\mathcal{R}$ 的期望竞争比满足

$$\mathbb{E}[{\text{ALG}}_{\mathcal{R}}(I)]\le c\cdot \mathbb{E}[\text{OPT}(I)]$$

对所有输入 $I$ 成立，当且仅当对所有输入分布 $\pi$， 存在确定性算法 $\mathcal{A}$ 使得

$${\mathbb{E}}_{\pi }[{\text{ALG}}_{\mathcal{A}}(I)]\le c\cdot {\mathbb{E}}_{\pi }[\text{OPT}(I)]$$

推论：要证明随机化算法的期望竞争比下界，只需构造一个输入分布，使得所有确定性算法的期望竞争比有一个下界。

6.3 随机化负载均衡

随机分配（Random Assignment）： 每个作业随机分配到一台机器。

def random_assignment(jobs, m):
    for job in jobs:
        machine = random.randint(0, m-1)
        machines[machine].add(job)

竞争比：$O(\log m/\log \log m)$（对数因子改进）

---

7. 对抗性分析与鲁棒性

7.1 自适应对抗模型

更强的对抗者：对抗者可以看到在线算法的实际决策，动态调整后续输入。

• 轻度自适应：对抗者在看到算法决策后生成下一输入
• 完全自适应：对抗者完全知道算法并优化最坏情况

7.2 排程问题的自适应下界

定理（对两台机器排程）：任何确定性在线算法的竞争比至少为 $5/3$。

构造：前两个作业大小为 $(1,ϵ)$，根据算法分配决定第三个作业大小。

7.3 指数后退策略

对于某些问题，随机化是抵抗自适应对抗的唯一手段。

---

8. 在线算法在AI中的应用

8.1 推荐系统

用户交互数据流式到达，推荐算法必须在线更新模型：

场景	在线算法
bandits	平衡探索与利用
流推荐	实时协同过滤
A/B测试	在线实验

8.2 自动驾驶决策

自动驾驶中的路径规划和控制都是在线问题：

• 部分可观测环境
• 决策必须在实时约束内完成
• 使用模型预测控制（MPC）等在线优化技术

8.3 大语言模型推理

LLM的自回归生成是典型的在线决策过程：

• token逐个生成
• 不能”预知”未来内容
• 使用束搜索（beam search）进行在线剪枝

---

9. 核心算法对比表

问题	确定性竞争比	随机化竞争比	下界
秘书问题	1（随机顺序）	1/e	1/e
在线装箱	1.7	1.691	1.531
负载均衡	$2-1/m$	$O(\log m/\log \log m)$	$\mathrm{1.371...}$
Ski Rental	$2-r/p$	同	$1-O(1/\ln (p/r))$
在线匹配	$O(\sqrt{n})$	$O(\log n)$	$\omega (1)$

---

参考来源

1. Borodin, A., & El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cambridge University Press.
2. Sleator, D. D., & Tarjan, R. E. (1985). Amortized Efficiency of List Update and Paging Rules. CACM.
3. Graham, R. L. (1966). Bounds for Certain Multiprocessing Anomalies. Bell System Technical Journal.
4. Karp, R. M. (1992). On-Line Algorithms. On-Line Algorithms.
5. Mehta, A., Saberi, A., Vazirani, U., & Vazirani, V. (2005). AdWords and Generalized Online Matching. JACM.

---

相关文档

• 计算复杂性理论深度 - 问题的离线复杂度
• 近似算法详解 - 离线近似技术
• 随机算法深度 - 随机化方法
• 组合优化深度指南 - 离线组合优化