算法导论27 Problems 答案
27-1
以下解答参考了这篇论文，它给出了一个竞争比例为$9$的在线算法。这个页面则描述了这个问题的原型。
对于一个输入未知输入$x$。接下来考虑这个在线算法$F(x)$的行为。考虑一个无限访问序列$xi=-\delta(-2)^i$，可见$\displaystyle{\lim{i\rightarrow-\infty}}xi=0$，因此起点是$x{-\infty}=0$，然后按这个顺序依次访问中间的所有节点。如果当前从$x{-\infty}=0$按顺序访问到了第$k$个节点，那么访问的距离总共为$\displaystyle{|x_k|+\sum{i=-\infty}^{k-1}|x_i|}$。
对于输入$x$，假设算法$F$所产生的步行距离为$f(x)$。现在假设$x>0$，那么可以选择$n$使得$x{2n-1}<x\le x{2n+1}$，即$-\delta \cdot (-2)^{2n-1}<x\le -\delta\cdot (-2)^{2n+1}$。算法$F$将从$x{-\infty}$逐步访问节点到$x{2n}$，再从$x_{2n}$访问到$x$。那么有
$\begin{aligned}
f(x)&= x+2\cdot\sum_{i=-\infty}^{2n} |x_i|\
&=x+\delta\cdot 2^{2n+2}\
&<x+8x &\qquad(A)\
&=9x
\end{aligned}$
其中步骤$(A)$是从$-\delta \cdot (-2)^{2n-1}<x$得到$\delta\cdot 2^{2n}<2x$。
现在假设$x<0$，那么可以选择$n$使得$x{2n+2}\le x< x{2n}$，即$-\delta \cdot (-2)^{2n+2}\le x<-\delta\cdot (-2)^{2n}$。算法$F$将从$x{-\infty}$逐步访问节点到$x{2n+1}$，再从$x_{2n+1}$访问到$x$。那么有
$\begin{aligned}
f(x)&= |x|+2\cdot\sum_{i=-\infty}^{2n+1} |x_i|\
&=-x+\delta\cdot 2^{2n+3}\
&<-x-8x &\qquad(B)\
&=-9x
\end{aligned}$
其中步骤$(B)$是从$x<-\delta\cdot (-2)^{2n}$得到$\delta\cdot 2^{2n}<-x$。
如果$x=0$，那么算法$F$不需要移动即可，即$f(x)=0$。
对于一个离线最优算法的花费$g(x)$，它知道$x$在哪个地方，因此只需要径直走过去即可，需要步行的距离为$g(x)=|x|$。
也就是说，$\forall x\in (-\infty,\infty)$，都有$f(x)\le 9g(x)$，因此算法$F$是线性查找问题中一个竞争比例为$9$的算法。
实际上，如果来回行走时到达了路径的终点，就可以立即返回。
27-2
这篇论文和本题目相关。
a
假设有如下$n$个任务${a_{1},a_2,\dots,a_n}$，其中$r_1=0,p_1=m(m>n)$，并且$\forall i\in[2,n],r_i=1,p_i=1$。考虑这个在线算法和最优离线算法的行为。
首先考虑在线算法的行为。一开始$(t=0)$，在线算法检查到未运行的最短时间任务$a_1$，那么它将会运行这个任务，并且最终在$C_1=m$这个时刻完成了它。完成$a_1$后，它检查到了任务$a_2,a_3,\dots,a_n$。由于它们所需要花费的时间都相同，因此不失一般性，按照$a_2,a_3,\dots,a_n$的时间运行。因此$\forall i\in[2,n]$，都有$C_i=m+i-1$。因此总共需要的时间为$C=\dfrac{(m+m+n-1)n}{2}$。
对于一个最优离线算法，它会先等待$n-1$个短任务$a_2,a_3,\dots,a_n$的到来，并执行完成。因此$\forall i\in[2,n]$，都有$C_i’=i$。接下来执行任务$a_1$，最终有$C_1’=n+m$。因此总共需要的时间为$C’=\dfrac{(2+n)(n-1)}{2}+m+n$。
那么，可见这个在线算法的竞争比例$r$至少为$C/C’=\Omega(mn/(n^2+m))$。如果$m=\omega(n^2)$，那么有$r=\Omega(m/n)$。也就是说，竞争比例取决于最长任务$a_1$的运行时间$m$。因此并不存在一个正常数$d$，使得这个算法是$d$竞争的。也就是说，这个算法的竞争比例是无界的。
b
对于任意一个时刻，如果当前处理机处于空闲状态，那么从任务队列$Q$中取一个剩余时间最短的任务运行。在运行某一个任务$a_i$中，如果在线算法发现一个新释放的任务$a_j$所需要的运行时间比当前任务的剩余运行时间还要短，那么$a_i$便会挂起，推入$Q$，并开始运行$a_j$；否则继续运行$a_i$，且将$a_j$推入$Q$中。
c
SPRT算法是题目15-2-b的所提供算法的最优解，同时它也是抢占式算法下平均完成时间的最优解，因此它是一个$1$竞争的在线算法。也就是说，运行算法SPRT所得到的$C1^P,C_2^P,\dots,C_n^P$同样也是题目15-2-b的离线最优抢占式调度的一个最优解。由于非抢占式调度策略是抢占式调度策略的一个子集，因此$C_1^{\ast},C_2^{\ast},\dots,C{i}^{\ast}$并不会比$C1^P,C_2^P,\dots,C_n^P$更优。因此根据题目15-2-b的结论，有$\displaystyle{\sum{i=1}^nCi^P\le \sum{i=1}^n C_i^{\ast}}$。
d
按照SPRT算法下的任务完成时间对任务进行排序完成后，考虑任务$i$完成的时刻，这时任务$1,2,\dots,i-1$都已经完成。因此有$\displaystyle{Ci^P\ge \sum{j=1}^i p_i}$。
由于$r_j$是任务$j$的释放时间，$C_j^P$是任务$j$的完整时间，因此有$r_j
因此有$\displaystyle{Ci^P\ge\max\left{\sum{j=1}^i p_j,\max{r_j:j\le i}\right}}$，原结论成立。
e
对于前$i$个任务，最懒惰且最贪心的做法是先将这$i$个任务全部释放后，再一次性全部完成。等待全部任务释放需要花费$\max{rj:j\le i}$的时间，一次性完成这些任务需要花费$\displaystyle{\sum{j=1}^i pi}$的时间。由于这$i$个任务是紧密完成的，因此必定有$\displaystyle{C_i\le \max{r_j:j\le i}+\sum{j=1}^i p_j}$，否则，必定存在某些时刻，处理机空闲且仍有任务未执行的情况，而这种情况必定不是最优的。
f
对算法COMPLETION-TIME-SCHEDULE可以改成如下离线版本COMPLETION-TIME-SCHEDULE-ONLINE：如果任务$a_j$在抢占式算法下于时刻$C_j^P$结束，那么在线非抢占式算法则只需要在$C_j^P$时间开始运行。如果此时不是空闲，那么需要等待上一个任务完成后，任务$a_j$需要开始执行。
g
结合题目27-2-d和题目27-2-e的结论，有
$\begin{aligned}
Ci&\le \max{r_j:j\le i}+\sum{j=1}^i pj\
&\le \max\left{\sum{j=1}^i pj,\max{r_j:j\le i}\right}+\max\left{\sum{j=1}^i p_j,\max{r_j:j\le i}\right}\
&\le 2C_i^P
\end{aligned}$
针对题目27-2-f提出的算法COMPLETION-TIME-SCHEDULE-ONLINE的输出结果，以及题目27-2-c的结论，有
$\begin{aligned}
\sum{i=1}^nC_i &\le \sum{i=1}^n2Ci^P\
&=2\sum{i=1}^P Ci^P\
&\le 2\sum{i=1}^P C_i^{\ast}\
\end{aligned}$
由于$C1^{\ast},C_2^{\ast},\dots,C{i}^{\ast}$是非抢占式最优离线算法输出的结果，因此COMPLETION-TIME-SCHEDULE-ONLINE是$2$竞争的。