动机
离线优化者在行动之前就知道整个输入。在线算法则必须随着信息陆续到来而作出选择,而当未来与其预期不同时,某个选择可能变得代价高昂。将在线代价与同一完整输入上的最优代价相比较,就给出了度量这种劣势的精确方式。租滑雪装备问题(ski-rental problem)把这一问题单独抽取出来:在活动持续期间可以每天租用,也可以一次性付费购买,但事先并不知道最后一天何时到来。
竞争保证是对所有可能输入长度的最坏情形陈述。它并不预测实际的天数,也不假设天数服从任何概率分布。本单元使用购买成本为整数的离散版本;其他的时间与成本约定会给出不同的常数。
定义
定义 7.1.1
(离散的滑雪租买问题)
固定整数 。共有 天,其中时间范围 对在线算法是未知的。在实际出现的每一天开始时,算法得知这一天存在;若尚未购买,则当天要么以成本 租用,要么以成本 购买。购买之后不再产生任何费用。时间范围可以在任何一天之后结束。离线算法事先知道 。
定义 7.1.2
(离线最优与竞争比)
在这个模型中,离线最优代价为 :要么租满 天,要么在第一天购买。若时间范围已知,则晚些购买不会比第一天购买更好,因为这会增加租金。对于在线算法 ,其竞争比定义为 在所有正整数时间范围上的上确界。此定义中不允许有加性项。
定义 7.1.3
(阈值算法)
阈值算法在前 天(若这些天出现)租用,并在第 天开始时购买(若该天出现)。当 时,它立即购买。算法在为第 天付费之前已得知该天存在,但并不知道之后是否还有下一天。
定理
定理 7.1.4
(阈值算法)
对每个整数 ,在上述模型中阈值算法的竞争比为 。
定理 7.1.5
(与之匹配的确定性下界)
在此模型中,每个确定性在线算法的竞争比至少为 。因此,就这一竞争比定义而言,阈值算法在确定性算法中是最优的。
证明思路
证明
(阈值算法的比值)
若 ,阈值算法每天都租用,付出 。若 ,它支付 的租金,再支付 购买,总计 。离线最优代价为 ,故比值为 。 时达到这个值,所以这就是精确的最坏情形比值。
证明
(购买日迫使出现坏的时间范围)
对于下界,固定任意一个确定性算法。它在无限持续的输入上的行动决定了它购买的第一天 (若它确实会购买)。在那一天之前它必须租用。若它从不购买,则对于任意大的 ,其代价为 ,而离线最优代价为 ;其比值无界。否则,考虑固定的时间范围 。算法在那一天购买,因为它观察到的历史与无限持续输入上的历史相同。它付出 。
若 ,则 ,比值为 。若 ,则离线最优代价为 ,比值为 。这也包括 的情形。因此,对于确定性算法的每一种购买日选择,都存在一个时间范围,使其比值至少达到所声称的值。下界是在检视了该确定性算法之后才构造时间范围的;这是一个最坏情形的存在性论证,并不是说算法知道自己的时间范围。
证明透视
从永不终止的输入读出购买日
下界证明有一个不明显的步骤:它先从算法在永不终止的输入上的行为读出购买日 ,然后才选取时间范围。这是合理的,因为确定性算法在见过第 天之后,无论雪季在第 天后结束还是继续,行动都完全相同。证明接着需要在 处分情形,因为离线最优 在那里改变形式: 时一直租用最优, 时立即购买最优。两种情形下,比值 都至少为 ,仅在 时取等号。永不购买的算法另行处理:它的比值无界。这个论证只建立了一个方向:对任意算法给出一个坏的时间范围,而阈值规则的上界则必须对每个时间范围都成立。
例题详解
例题 7.1.6
(时间范围在购买之前结束)
设 ,。阈值规则租用三次,成本为 。离线最优代价为 ,故比值为一。算法不会仅仅因为计划在第五天购买就去购买;那一天必须真的出现。
例题 7.1.7
(阈值日恰为最后一天)
设 ,。算法租用四天,并在第五天购买,共付出 。离线优化者立即购买或租满五天,两种方式都付出 。比值为 ,这正是该规则的最坏情形。算法知道第五天已经到来,但在作出当天的决定时无法知道这是否为最后一天。
例题 7.1.8
(买得太早或太晚)
对 ,在第 天购买的算法,当 时付出 ,而离线最优代价为 ;比值为 。在第 天购买的算法,当 时付出 ,而离线最优代价为 ;比值为 。两者都超过阈值比 。
常见错误
反例模式
知道当前是第几天并不等于知道时间范围
在第五天开始时,时间范围 与 的历史完全相同。在线算法无法让第五天的行动取决于最终会出现哪一个时间范围。若赋予它这种信息,就会悄悄地把这个决策变成离线决策。
常见错误
(比较不同时间范围上的代价)
竞争比比较的是同一时间范围上的代价。把长时间范围上的在线代价除以另一个短时间范围上的离线代价,是没有意义的。
常见错误
(把比值界当作在每个输入上都最优)
比值的界并不表示算法在每个输入上都是最优的:在阈值日,差距是实际存在的,尽管它是有界的。对 、,算法付出 ,而最优代价为 。
为什么阈值能平衡两种风险
假设某个确定性规则计划在第 天购买。对于恰好在那一天结束的时间范围,该规则要支付之前所有的租金以及购买费用。若 ,离线最优做法本应是一直租用,因此比值为 。当 向 增大时,该表达式减小。若 ,离线优化者本应立即购买,比值变为 ,它随 增大而增大。两个表达式在 处相交。这解释了该规则:买得太早,有在时间范围结束前夕才付出购买价格的风险;买得太晚,则会累积不必要的租金。
这一论证利用时间范围 为每个购买日推出一个下界。要确定阈值规则的精确比值,仍须像第一个定理那样分析所有时间范围。仅在某一个精心选取的时间范围上取值,只能给出某个特定算法最坏情形比值的下界。反过来,检验许多样本时间范围也无法建立普遍的上界;以 为界的情形划分涵盖了每个正整数时间范围。
例题 7.1.9
(比较小购买价格下每一个确定性阈值)
取 。第一天购买时,当 比值为 。第二天购买时,当 比值为 。第三天购买时,对每个 比值为 ,而对更短的时间范围比值为一。在任意第 天购买时,当 比值至少为 。从不购买的比值无界。因此第三天是最佳的确定性阈值,其比值与定理一致。
下面的互动图让你改变购买价格 与购买日 ,并显示每个 的精确最坏比值 ,其最小值 出现在 。
下界中的对手知道什么
对于确定性算法,在给定历史上的行动是固定的。在无限持续的输入上,算法要么在某一天购买,要么永远租用。这个假想的输入是确定其购买日的一种便利方式;用来见证下界的有限时间范围是在此之后才选取的。直到那一天为止,有限输入与无限输入的历史完全相同,所以算法的行动也完全相同。对该特定的确定性算法而言,下界所用的输入是一个有效的、固定的有限序列。
该论证并不假设真实的对手能够看到未来的随机种子。事实上,它并没有为随机化算法建立匹配的下界。随机化算法可能在不同的随机结果下选择不同的购买日,因此不一定存在单一的确定性 能描述它的所有运行。分析必须说明输入是否独立于随机选择而固定、所取的是什么期望,以及使用什么基准。若不加这些限定就重复使用确定性证明,会混淆不同的模型。
竞争比也不是对时间范围取的平均。时间范围的某个分布可能使某种策略在期望意义下具有吸引力,但那将是另一个目标。例如,若决策者确定地知道 且 ,则租用是最优的;若确定地知道 非常大,则立即购买是最优的。竞争性规则不作这类分布假设,并在这两类时间范围上都控制其损失。
时间与建模的选择
事件发生的顺序决定了定理。在我们的模型中,算法先得知当前这一天存在,然后选择租用或购买,之后才得知是否还有更多的日子。因此它不会为不存在的一天付费,但它可以在最后一个实际存在的日子购买。若规则必须在得知当天是否存在之前就作出承诺,或者购买只从次日起生效,则成本表达式会改变。针对某一种约定写出的证明,在未重新核对事件顺序之前,不得照搬到另一种约定上。
整数假设同样重要。这里的阈值日字面上就是 。若购买成本不是整数,就必须选择一个整数日并比较邻近的几种可能;把 换成非整数的日子并不是有效的算法。更一般地,每日租金 可以通过把所有成本除以 来归一化,但所得的购买与租金之比不一定是整数。明确的整数假设避免了取整问题,而不是悄悄地解决它。
该模型只允许购买至多一次,且此后拥有物品不再产生费用。若购买的物品会损耗、有每日的运行成本或可以转售,则在线算法与离线最优都会改变。这类变体仍可能是有用的在线问题,但公式 需要新的理由。基准必须体现与算法相同的规则与成本,只是它知道时间范围。
所提出竞争比的一份证书
要验证上界 ,需在每一类可能的输入上计算在线与离线代价,并在每一类中证明 。对于阈值规则,以 为界的划分已经足够,因为两侧的公式分别变成常数或简单形式。要说明 对该特定算法也是必要的,需给出一个使等号成立的时间范围。这里任何 都达到 。
对所有确定性算法的下界更强:它必须从任意算法出发,而不只是预先选好的另一个阈值。在这个简单的问题中,购买之前唯一可能的行动是租用,算法观察到的仅是日子的流逝。因此它在持续输入上的确定性行为决定了一个购买日,或者从不购买的行为。这一观察证明了把任意确定性策略化归为定理中各情形的合理性。在更丰富的在线问题中,历史包含更多信息,因此单一阈值可能无法描述每一种策略。
总结
租用推迟了承诺,购买则为未来的成本设定了上限。在这个离散模型中,平衡点出现在第 天,给出精确的比值 。对手可以利用算法的确定性购买日,构造出与之匹配的下界时间范围。
练习
快速检查
(对 ,分别计算 与 时阈值算法的成本与比值。)
解答 · 答案
当 时,它付出 ,最优代价为 ,比值为一。当 时,它付出 ,最优代价为 ,比值为 。
快速检查
(当 时会发生什么?)
解答 · 答案
阈值是第一天,所以它立即购买,成本为一。对每个正的时间范围,离线最优代价都是一;比值为一。
快速检查
(某确定性算法在 时于第 天购买。利用时间范围 计算其比值。)
解答 · 答案
它付出 ,最优代价为 ,故比值为 。
快速检查
(为什么从不购买的算法没有有限的竞争比?)
解答 · 答案
在时间范围 上它的成本为 ,而当 时最优代价为 。比值 无界增长。