01 滑雪板租赁问题

在线算法

在计算机科学中，我们经常遇到这样的问题：给一些输入，询问答案；再给一些输入，再询问答案……对于这样的问题，如果每次询问时我们都先给出答案再读取接下来的输入，就称为一个“在线算法(Online Algorithm)”；如果允许先保存下所有的输入，到最后再回答所有的询问，就称为一个“离线算法(Offline Algorithm)”。如果离线是允许的，那我们总是能给出比在线算法更优的策略，因为我们有了关于后续的更多信息。但在很多应用场景下，离线是不被允许的，例如在战争中我们必须快速对部队的每一次请求快速做出回应，不能等一天的战况全都结束后再一一给出反馈。下面我们就开始思考第一个简单的在线算法问题。

滑雪板租赁问题

小A去滑雪场滑雪时需要滑雪板，每次到达滑雪场时可以选择租一次或者永久买下。租的价格为1元，买的价格为10元。由于每次到达滑雪场时，我们不知道小A未来还会不会再去滑雪，所以每次回答买还是租的问题就是一个在线算问题。我们需要帮助小A决策每次去滑雪应当租滑雪板还是买滑雪板，使得在小A决定再也不去滑雪的那天为止总消费尽量小。

这个问题如果可以用离线算法，就会变得非常容易。由于我们能够保存下来每一次询问，所以当我们要做出回答时已经知道了小A总共会去几次滑雪场。那么只需分类讨论，设小A总共去了$n$次滑雪场，如果$n<10$那么每次都租，花费$n$元；如果$n \geq 10$，那么第一次就买，花费$10$元。不可能有比这更优的策略，所以这是离线情形下的最优算法。

但是如果这是一个在线算法问题，我们每次作答的时候就无法获知之后小A会不会再去，也就难以有一个完美的决策方案。我们可以做出一些一般的决策，例如：总是在第一天就买下；如果不足8天就一直租，在第八天就买下；在第十天买下；等等。那么，如何衡量这样的一些决策是否是一个“好”的决策呢？

对于一个输入$I$，我们把离线的最优算法给出的答案记为$\text{OPT}(I)$，把我们选择的算法给出的输出记为$\text{ALG}(I)$。由于离线算法对于任何$I$总是最优的，比值$\dfrac{\text{ALG}(I)}{\text{OPT}(I)}$总是一个大于等于1的数，称为竞争比(competitive ratio)。我们可以用最坏情况(worst case)下算法的表现来衡量一个算法的好坏，也就是说我们关心竞争比关于$I$的最大值。在滑雪板租赁的例子当中，输入$I$就是一个正整数$n$，代表总共去了多少次滑雪场；输出也是一个正整数，代表价格。我们可以对所有可能的输入分类讨论：假设选择在第$t$天买下，$t<10$。那么在$n<t$时竞争比为$\dfrac{n}{n}=1$，在$t\leq n<10$时为$\dfrac{t-1+10}{n}=\dfrac{t+9}{n}$，在$n \geq 10$时为$\dfrac{t+9}{10}$，可见竞争比的最大值为$\dfrac{t+9}{t}$。“在第10天买下”的竞争比在$n<10$时为$\dfrac{n}{n}=1$，在$n\geq 10$时为$\dfrac{9+10}{10}=1.9$，可见竞争比的最大值为$1.9$。在超过10天以后再买下的方案显然是不如在第一天就买下，所以不需讨论。我们想要选出所有方案中最大竞争比最小的那个，在这里应当是“选择在第十天买下”，最大竞争比为$1.9$。

以上分析称为最坏情况分析(worst case analysis)，它本质就是在求解$\min\limits_{\text{ALG}}\max\limits_{I\leq 10}\dfrac{\text{ALG}(I)}{\text{OPT}(I)}$。我们之所以分析得到“在第十天买下”是最优的，是因为它能够保证如果我们去的天数不多不会太亏，去的天数很多也不会太亏，它在最坏情况下表现时良好的。如果“在第一天就买下”，这时如果去的天数多表现得很好，但是如果只去了一天就会亏十倍，所以在最坏情况分析下这个算法不如“在第十天买下”。

随机算法

我们发现，以上算法的竞争比之所以不能做得比$1.9$更好是因为在最坏情况分析下，“去的天数少”和“去的天数多”中总会有一种情况让我们的算法变得不太好，所以我们选择了“第十天再买”这一折中的策略。如果我们引入随机性，即以一定概率让算法在天数少时表现好，一定概率在天数多时表现好，会不会让结果更优呢？此时我们用算法输出的期望来定义竞争比：$\dfrac{\mathbb{E}[\text{ALG}(I)]}{\text{OPT}(I)}$。

假设我们采取这样的随机算法：50%的概率在第8天买下，50%的概率在第10天买下。那么$n<8$时，竞争比为$\dfrac{n}{n}=1$；$n=8$时，为$\dfrac{0.5\times 17+0.5\times 8}{8}=1.5625$；当$n=9$时，为$\dfrac{0.5\times 17+0.5\times 9}{9}\approx 1.44$；当$n=10$时，为$\dfrac{0.5\times 17+0.5\times 19}{10}=1.8$。可见最大竞争比为$1.8$，比确定性算法更优！

那么，如何找到一个最优的随机算法呢？也即如何求解$\min\limits_{\text{ALG}}\max\limits_{I\leq 10}\dfrac{\mathbb{E}[\text{ALG}(I)]}{\text{OPT}(I)}$？一个随机算法就是确定性算法的概率分布，而在这个问题中一个确定性算法就对应一个正整数（在第几天买）。而我们已经知道任何超过第十天买的确定性策略不如在第一天就买的策略，所以我们可以把任何一个随机算法看作“在第一天买”、……、“在第十天买”这十个确定性算法的概率分布，记为$p=(p_1,\cdots,p_{10})$。当$n\leq 10$时，竞争比为$\dfrac{\sum\limits_{i=1}^{n}p_i(i+9)+\sum\limits_{i={n+1}}^{10}p_i\cdot n}{n}$，$n>10$时竞争比为$\dfrac{\sum\limits_{i=1}^{10}p_i(i+9)}{10}$。后者和前者在$n=10$时的取值相同，所以我们最终要求解的问题就是$\min\limits_{p}\max\limits_{n\leq 10}\dfrac{\sum\limits_{i=1}^{n}p_i(i+9)+\sum\limits_{i={n+1}}^{10}p_i\cdot n}{n}$。

我们可以这样求解这个问题：设有$[0,10]$上的连续函数$p$满足$\displaystyle\int_{i-1}^{i} p(x)\text{ d} x=p_i$，那么$\displaystyle\int_{0}^{10} p(x)\text{ d} x=\sum\limits_{i=1}^{10}p_i=1$，可见$p$是$[0,10]$上的概率分布。于是，$\sum\limits_{i=1}^{n}p_i(i+9)=\sum\limits_{i=1}^{n}\left[(i+9)\displaystyle\int_{i-1}^{i} p(x)\text{ d} x\right]$ $\leq \sum\limits_{i=1}^{n}\left[\displaystyle\int_{i-1}^{i} p(x)(x+10)\text{ d} x\right]$ $= \displaystyle\int_{0}^{n} p(x)(x+10)\text{ d} x$，$\sum\limits_{i={n+1}}^{10}p_i\cdot n=\sum\limits_{i={n+1}}^{10}n\displaystyle\int_{i-1}^{i} p(x)\text{ d} x=n\displaystyle\int_{n}^{10} p(x)\text{ d} x$，所以$\dfrac{\sum\limits_{i=1}^{n}p_i(i+9)+\sum\limits_{i={n+1}}^{10}p_i\cdot n}{n}\leq\dfrac{\displaystyle\int_{0}^{n} p(x)(x+10)\text{ d} x+n\displaystyle\int_{n}^{10} p(x)\text{ d} x}{n}$。我们求解$\min\limits_{p}\max\limits_{n\leq 10}\dfrac{\displaystyle\int_{0}^{n} p(x)(x+10)\text{ d} x+n\displaystyle\int_{n}^{10} p(x)\text{ d} x}{n}$一定会得到一个更大的答案，如果这个答案能被bound住，说明原问题的答案一定也被bound住。这一问题可以等价地写作$\min\limits_{p}\alpha$使得$\forall n\leq 10$，$\alpha \geq\dfrac{\displaystyle\int_{0}^{n} p(x)(x+10)\text{ d} x+n\displaystyle\int_{n}^{10} p(x)\text{ d} x}{n}$。可以证明，$\min\alpha$一定在所有大于等于号都取等时取到。所以得到方程$\forall n\leq 10,\alpha \cdot n = \displaystyle\int_{0}^{n} p(x)(x+10)\text{ d} x+n\displaystyle\int_{n}^{10} p(x)\text{ d} x$。对于每个方程，把$n$看作连续的变量对$n$求导得$\alpha=p(n)(n+10)+\displaystyle\int_{n}^{10} p(x)\text{ d} x-np(n)$，也即$\alpha = 10\cdot p(n)+\displaystyle\int_{n}^{10} p(x)\text{ d} x$。再次求导可得$0=10\cdot p'(n)-p(n)$，也即$p(n)=Ce^{\frac{n}{10}}$，由$\displaystyle\int_{0}^{10} p(x)\text{ d} x=1$可得$C=\dfrac{1}{10(e-1)}$，$p(n)=\dfrac{1}{10(e-1)}e^{\frac{n}{10}}$。代入可得$\alpha = \dfrac{e}{e-1}\approx 1.58$。这样我们就证明了，存在一个最大竞争比不超过1.58的随机算法。

在以上放缩中，我们把离散的变量$n$看作了连续，所以事实上滑雪板的价格趋向无穷时，这一步放缩是tight的。1.58在滑雪板价格趋向无穷时就是最优随机算法的竞争比。

对于较小的滑雪板价格，我们已经证明了最优的随机算法的竞争比小于1.58。可以证明， 设滑雪板价格为$b$，最优竞争比为$\dfrac{1}{1-\left(\dfrac{b-1}{b}\right)^b}$。这再次佐证，当$b\to\infty$时竞争比趋向$\dfrac{e}{e-1}$。