算法导论27 Problems 答案

27-1

以下解答参考了这篇论文，它给出了一个竞争比例为\(9\)的在线算法。这个页面则描述了这个问题的原型。

对于一个输入未知输入\(x\)。接下来考虑这个在线算法\(F(x)\)的行为。考虑一个无限访问序列\(x_i=-\delta(-2)^i\)，可见\(\displaystyle{\lim_{i\rightarrow-\infty}}x_i=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所得到的\(C_1^P,C_2^P,\dots,C_n^P\)同样也是题目15-2-b的离线最优抢占式调度的一个最优解。由于非抢占式调度策略是抢占式调度策略的一个子集，因此\(C_1^{\ast},C_2^{\ast},\dots,C_{i}^{\ast}\)并不会比\(C_1^P,C_2^P,\dots,C_n^P\)更优。因此根据题目15-2-b的结论，有\(\displaystyle{\sum_{i=1}^nC_i^P\le \sum_{i=1}^n C_i^{\ast}}\)。

d

按照SPRT算法下的任务完成时间对任务进行排序完成后，考虑任务\(i\)完成的时刻，这时任务\(1,2,\dots,i-1\)都已经完成。因此有\(\displaystyle{C_i^P\ge \sum_{j=1}^i p_i}\)。

由于\(r_j\)是任务\(j\)的释放时间，\(C_j^P\)是任务\(j\)的完整时间，因此有\(r_j<C_j^P\)。又因为\(C_1^P,C_2^P,\dots,C_n^P\)是严格单调递增的，因此\(\forall j\in[1,i]\)，都有\(C_i^P>r_j\)成立。

因此有\(\displaystyle{C_i^P\ge\max\left\{\sum_{j=1}^i p_j,\max\{r_j:j\le i\}\right\}}\)，原结论成立。

e

对于前\(i\)个任务，最懒惰且最贪心的做法是先将这\(i\)个任务全部释放后，再一次性全部完成。等待全部任务释放需要花费\(\max\{r_j:j\le i\}\)的时间，一次性完成这些任务需要花费\(\displaystyle{\sum_{j=1}^i p_i}\)的时间。由于这\(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} C_i&\le \max\{r_j:j\le i\}+\sum_{j=1}^i p_j\\ &\le \max\left\{\sum_{j=1}^i p_j,\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}^n2C_i^P\\ &=2\sum_{i=1}^P C_i^P\\ &\le 2\sum_{i=1}^P C_i^{\ast}\\ \end{aligned}\)

由于\(C_1^{\ast},C_2^{\ast},\dots,C_{i}^{\ast}\)是非抢占式最优离线算法输出的结果，因此COMPLETION-TIME-SCHEDULE-ONLINE是\(2\)竞争的。