算法导论27.2 Exercises 答案
27.2-1
由于每次查询都是相互独立的，因此假设每一次查询需要进行检索的期望值为$e$（与查询的序号无关）。由于需要检索关键字的概率为$x_i$，因此这时$e$值为
$\begin{aligned}
e&=\sum{k=1}^n k\cdot\left(\sum{x\in S\land rL(x)=k} p(x)\right)\
&=\sum{i=1}^n r_L(x_i)\cdot p(x_i)
\end{aligned}$
因此$m$次查询的总期望次数为$\displaystyle{me=m\sum_{i=1}^n r_L(x_i)\cdot p(x_i)}$。
如果$L$中的关键字$xi$不是按照查询概率$p$从大到小出现的，那么必定存在一对不同的关键字$x_j,x_k$，使得$r_L(x_j)<r_L(x_k)$并且有$p(x_j)<p(x_k)$。那么考虑新构造的静态表$L’$，它是将关键字$x_j$和$x_k$进行了交换，由此可见$r_L(x_i)=r{L’}(xj),r_L(x_j)=r{L’}(xi)$。考虑计算静态表上$L’$进行一次检索的花费的期望值，可以得到$\displaystyle{e’=\sum{i=1}^n r_{L’}(x_i)\cdot p(x_i)}$。
那么得到
$\begin{aligned}
e’-e&=p(xj)\cdot r{L’}(xj)+p(x_k)\cdot r{L’}(xk)-p(x_j)\cdot r{L}(xj)-p(x_k)\cdot r{L’}(xk)\
&=p(x_j)(r{L’}(xj)-r{L}(xj))+p(x_k)(r{L’}(xk)-r{L}(xk))\
&=p(x_j)(r{L}(xk)-r{L}(xj))+p(x_k)(r{L}(xj)-r{L}(xk))\
&=p(x_j)(r{L}(xk)-r{L}(xj))-p(x_k)(r{L}(xk)-r{L}(xj))\
&=(p(x_j)-p(x_k))(r{L}(xk)-r{L}(x_j))\
&<0
\end{aligned}$
因此$L$不是使查找期望数最小的静态表。最终，只有按照$p(x_i)$降序的静态表才是所求的。
27.2-2
这个结论是错误的。FORESEE考虑的是全局最优的策略，每一个步骤的开销都并非比MOVE-TO-FRONT优秀。
考虑对序列$\langle 1,2,3,4,5\rangle$，接下来$3$次搜索分别是检索$3,5,5$，那么有
$\begin{array}{c|ccccc|ccccc}
\begin{array}{c}\text{element}\\text{searched}\end{array} &L&\begin{array}{c}\text{search}\\text{cost}\end{array}&\begin{array}{c}\text{swap}\\text{cost}\end{array}&\begin{array}{c}\text{search +}\\text{swap}\\text{cost}\end{array}&\begin{array}{c}\text{cumulative}\\text{cost}\end{array}&L&\begin{array}{c}\text{search}\\text{cost}\end{array}&\begin{array}{c}\text{swap}\\text{cost}\end{array}&\begin{array}{c}\text{search +}\\text{swap}\\text{cost}\end{array}&\begin{array}{c}\text{cumulative}\\text{cost}\end{array}\\hline
3&\langle 1,2,3,4,5\rangle&3&4&7&7&\langle 1,2,3,4,5\rangle&3&2&5&5\
5&\langle 5,1,2,3,4\rangle&1&0&0&8&\langle 3,1,2,4,5\rangle&5&4&9&14\
5&\langle 5,1,2,3,4\rangle&1&0&0&9&\langle 5,3,1,2,4\rangle&1&0&0&15
\end{array}$
可见在这个检索序列中，FORESEE的总操作开销小于MOVE-TO-FRONT的总操作，但是FORESEE的第一步开销大于MOVE-TO-FRONT的第一步开销，从而证伪原结论。
27.2-3
结论：这种通过关键字的访问次数维护表$L$的策略并非是常数竞争比例的。
考虑一个表$L$中有如下关键字：$\langle 1,2,3,\dots,n\rangle$，以及一个访问序列：首先进行$n$次对$1$的访问，然后进行$n$次对$2$的访问，接下来进行$n$次对$3$的访问……最后对$n$进行$n$次访问。也就是说，一共对表$L$进行了$n^2$次检索。在这个过程中，不失一般性，如果存在元素的访问次数相同，那么对列表重排后，相同访问次数的元素相对顺序不变。那么在这个过程中，表$L$所有的关键字的顺序将会维持不变（因为访问次数全程都是非递增的）。
在这$n^2$检索中，对于第$(k-1)n+1$到第$kn$次访问（其中$k\in[1,n]$），都是访问$L$中的第$k$个元素，所花费的代价为$k$。因此，这$n^2$次操作的代价为$\displaystyle{c1(n)=\sum{k=1}^nnk=n\cdot \dfrac{n(n+1)}{2}=\dfrac{n^2(n+1)}{2}}$。
考虑使用MOVE-TO-FRONT算法充当FORESEE算法的角色。对于第$(k-1)n+1$到第$kn$次访问中，第$k(n-1)$次访问使用了$k$的开销寻找到了这个元素，并且用$k-1$的开销将其移动到最前面，因此总共有$2k-1$的开销；而第$(k-1)n+2$到第$kn$次访问中，仅仅使用了$1$的代价用于寻找。因此，这$n^2$次操作的代价为$\displaystyle{c2(n)=\sum{k=1}^n(2k-1+n-1)=n^2-2n+n(n+1)=2n^2-n}$。
可见，$\dfrac{c_1(n)}{c_2(n)}=O(n)$，因此这种策略不是常数竞争比例的。
27.2-4
如果MOVE-TO-FRONT算法移动元素不需要花费任何的代价，那么方程27.3可以改写成：
$ci^M=r{{L}_{i-1}^M}(x)$
如果使用势函数$\Phii=I(L_i^M,L_i^F)$，并且这个模型下中，第$i$次操作的真实代价为$c_i^{M}$，均摊代价为$\hat{c}_i^M$。那么有$\hat{c}_i^M=c_i^M+\Phi{i}-\Phi{i-1}$，并且按照$I$的定义，可见有$\Phi_0=0,\forall i\in[1,n],\Phi{i}\ge 0$。考虑计算$\hat{c}_i^M$，通过书上类似的论证方式，有
$\begin{aligned}
\hat{c}i^M&=c_i^M+\Phi{i}-\Phi{i-1}\
&=r{{L}{i-1}^M}(x)+(|BB|-|BA|+t_i)\
&=r{{L}{i-1}^M}(x)+(|BB|-(r{{L}{i-1}^M}(x)-1-|BB|)+t_i)\
&=2|BB|+1+t_i\
&\le 2|BB|+2|AB|+2t_i+2\
&= 2(|BB|+|AB|+t_i+1)\
&=2(r{L_{i-1}^F}(x)+t_i)\
&=2c_i^F
\end{aligned}$
那么由于$\displaystyle{\sum{i=1}^m\hat{c}_i^M=\sum{i=1}^mci^M+\Phi_m-\Phi_0\ge \sum{i=1}^mc_i^M}$
$\begin{aligned}
\sum{i=1}^m\hat{c}_i^M&=\sum{i=1}^mci^M+\Phi_m-\Phi_0\
&\ge \sum{i=1}^mc_i^M，
\end{aligned}$
因此有
$\begin{aligned}
\sum{i=1}^mc_i^M&\le\sum{i=1}^m\hat{c}i^M\
&\le\sum{i=1}^m2ci^F\
&=2\sum{i=1}^mc_i^F\
\end{aligned}$
最终在这个模型下，如果不计算算法MOVE-TO-FRONT移动关键字的代价，那么它是$2$竞争的。