算法导论27.1 Exercises 答案

27.1-1

令\(i(m)\)表示采取等待至多\(p\)个单位时间电梯时所花费的时间。那么可以写出\(i(m)\)为

\(i(m)= \left \{\begin{aligned} &m+1 & & \text{if}\quad m\le p \\ &p+k & & \text{if}\quad m>p\\ \end{aligned}\right.\)

那么此时的竞争比例为\(r=\max\{i(m)/t(m):0\le m<B\}\)。

如果有\(p<k-1\)，那么竞争比例为\(r=\max\left\{\dfrac{1}{1},\dfrac{2}{2},\dots,\dfrac{p-1}{p-1},\dfrac{p}{p},\dfrac{p+1}{p+1},\dfrac{p+k}{p+2},\dots,\dfrac{p+k}{k},\dfrac{p+k}{k},\dots,\dfrac{p+k}{k}\right\}=\dfrac{p+k}{p+2}=1+\dfrac{k-2}{p+2}\)。

如果有\(p=k-1\)，那么竞争比例为\(r=\max\left\{\dfrac{1}{1},\dfrac{2}{2},\dots,\dfrac{k-1}{k-1},\dfrac{k}{k},\dfrac{(k-1)+k}{k},\dots,\dfrac{(k-1)+k}{k}\right\}=\dfrac{p+k}{p+2}=\dfrac{2k-1}{k}\)。

如果有\(p=k\)，那么竞争比例为\(r=2\)。

如果有\(p>k\)，那么竞争比例为\(r=\max\left\{\dfrac{1}{1},\dfrac{2}{2},\dots,\dfrac{k}{k},\dfrac{k+1}{k},\dots,\dfrac{p-1}{k},\dfrac{p}{k},\dfrac{p+1}{k},\dfrac{p+k}{k},\dots,\dfrac{p+k}{k}\right\}=\dfrac{p+k}{k}>2\)。

由此可见，当取\(p=k-2\)时，可以得到最小的竞争比例\(r=\dfrac{2k-2}{k}\)。

27.1-2

对于一个能够预测到自己滑雪天数的预言家，他一定能够采取最优的策略。令\(t(m)\)表示滑雪\(m\)天时，预言家所采取最优策略需要的花费，可以给出为：

\(t(m)= \left \{\begin{aligned} &rm & & \text{if}\quad m<\lceil b/r\rceil \\ &b & & \text{if}\quad m\ge \lceil b/r\rceil \\ \end{aligned}\right.\)

考虑如下在线策略：对于前\(\lceil b/r\rceil-1\)天，每天都支付\(r\)元来支付租金。在第\(\lceil b/r\rceil\)天，买断这对滑雪板，从此以后不需要再花钱。因此，如果需要滑雪\(m\)天，令\(h(m)\)表示这个在线策略中，前\(m\)天的花费，如下：

\(h(m)= \left \{\begin{aligned} &rm & & \text{if}\quad m<\lceil b/r\rceil \\ &r(\lceil b/r\rceil-1) +b & & \text{if}\quad m\ge \lceil b/r\rceil \\ \end{aligned}\right.\)

可见，当\(m<\lceil b/r\rceil\)时，有\(t(m)=h(m)\)；当\(m\ge\lceil b/r\rceil\)时，有\(\dfrac{h(m)}{r(m)}=1+\dfrac{r(\lceil b/r\rceil-1)}{b}<2\)。因此可以得到竞争比例\(r=\max\{h(m)/t(m):m>1\}<2\)。因此如上策略满足题意。

27.1-3

假设现在一共有\(n\)匹配的卡片（一共有\(2n\)张）。对于一个能够预测到牌子底下动物的预言家，他一定能够采取最优的策略，即每次翻出一对相同的卡片。这意味着预言家只需要\(n\)回合就可以结束游戏。因此令\(t(n)\)表示包含\(n\)对卡片时，预言家所采取最优策略需要的回合数，可以给出为：\(t(n)=n\)。

考虑如下在线策略：每次揭开这\(2n\)张卡片中尚未曾经揭开过的两张，如果相同，那么移除，否则记住卡片上的动物并翻转回去，这个阶段一共包含了\(n\)回合的操作，并且至多只剩下\(m(m\le n)\)对卡片在卡片堆中。接下来只需要将这\(2m\)张卡片按照记忆，一对对进行翻转并移除即可，这个阶段包含了\(m\)次操作。因此这个在线算法的操作次数为\(h(n)=m+n\le n+n\le 2n\)。

由于\(\forall n\ge 1,\dfrac{h(n)}{t(n)}\le 2\)均成立，因此如上策略满足题意。