在线算法

概述

在线算法（Online Algorithm）是一种在输入尚未完全已知时就必须做出决策的算法策略。由于无法预知未来的输入，在线算法通常无法总是做出最优决策。其性能通过竞争比（competitive ratio）来衡量，即在线算法的代价与最优离线算法代价之比的上界。

定义

在线算法（Online Algorithm）

在线算法是指在每个输入到达时，必须立即对该输入做出处理决策，而不能等待后续输入或回溯修改之前的决策。与之相对的是离线算法（Offline Algorithm），它可以在看到全部输入后再做决策。

形式化地，设输入序列为 $\sigma ={\sigma }_1,{\sigma }_2,\dots ,{\sigma }_n$，在线算法 $A$ 在处理 ${\sigma }_i$ 时只能利用 ${\sigma }_1,\dots ,{\sigma }_i$ 的信息。

竞争比（Competitive Ratio）

设 $A(\sigma )$ 为在线算法 $A$ 在输入序列 $\sigma$ 上的代价，$OPT(\sigma )$ 为最优离线算法在 $\sigma$ 上的代价。若存在常数 $c\ge 1$ 使得对所有输入序列 $\sigma$：

$A(\sigma )\le c\cdot OPT(\sigma )+b$

其中 $b$ 为常数，则称算法 $A$ 是 $c$-竞争的（$c$-competitive）。最小的 $c$ 称为算法的竞争比。

核心性质

性质	描述	备注
无未来信息	决策时无法预知后续输入	在线算法的根本限制
不可撤回	已做出的决策通常不能修改	与贪心算法类似
竞争比	衡量在线算法与最优离线算法的差距	竞争比越小越好
确定性 vs 随机化	随机化在线算法可能获得更好的期望竞争比	如随机化标记算法

应用场景

• 缓存淘汰（Paging）：

  • LRU（最近最少使用）：竞争比为 $k$（$k$ 为缓存大小），确定性算法的最优竞争比
  • 标记算法（Marking Algorithm）：确定性 $k$-竞争，随机化版本可达 $O(\log k)$-竞争
  • FIFO（先进先出）：竞争比为 $k$

• 在线装箱（Online Bin Packing）：

  • Next-Fit 算法：竞争比为 2
  • First-Fit 算法：竞争比为 1.7

• 在线排序：在不知道全部输入的情况下进行排序，竞争比分析较为复杂

参见

• 贪心算法 — 许多在线算法采用贪心策略
• 散列表 — 散列表的冲突处理可视为在线决策
• 概率分析 — 随机化在线算法的性能分析工具