趣题: 磁带最优存储问题

趣题: 磁带最优存储问题 #

题目 #

磁带需要存储 $n$ 个 程序 $P_1, P_2, …, P_n$ , 程序 $P_i$ 占据 $s_i$ 的空间, 并且依据经验, 每次使用磁带有 $\pi_i$ 的概率是使用这个程序. 假设磁带有足够的空间, 存储信息的密度为常数, 读取速度也为常数, 此外, 读取完一个程序后需要将磁带倒带到初始状态. 如果程序以 $i_1, i_2, …, i_n$ 的顺序存储, 那么平均读取用时为 $$ \overline{T} = c\sum_{j = 1}^{n}(\pi_{i_j}\sum_{k = 1}^{j}s_{i_k}) $$ 其中 $c$ 为与磁带本身有关的常数. 要使平均读取用时最短, 求程序排列的顺序.

Solution 1 #

每次读取程序都必须将前面所有的程序都读取一遍, 因此我们希望:

• $s_i$ 越大的程序越靠后
• $w_i$ 越小的程序越靠前

综合这两个指标, 我们考虑将程序以 $\frac{\pi_i}{s_i}$ 不增的顺序排列. 下面来证明这种做法的正确性.

对于排列 $i_1, i_2, …, i_n$ , 假设存在 $(l, r)$ , 有 $\frac{\pi_{i_l}}{s_{i_l}} < \frac{\pi_{i_{r}}}{s_{i_{r}}}$ . 我们寻找这些数对 $(l, r)$ 里 $r - l$ 最小的那一对, 不妨记为 $(l_0, r_0)$ . 假设 $r_0\not = l_0 + 1$ , 因为 $(l_0, r_0)$ 是符合条件的数对中距离最小的, 所以对于 $(l_0 + 1, r_0)$ 有 $\frac{\pi_{i_{l_0+1}}}{s_{i_{l_0+1}}} \geq \frac{\pi_{i_{r_0}}}{s_{i_{r_0}}}$ , 对于$(l_0, l_0+1)$ 又有 $\frac{\pi_{i_{l_0}}}{s_{i_{l_0}}} \geq \frac{\pi_{i_{l_0+1}}}{s_{i_{l_0+1}}}$ , 故 $\frac{\pi_{i_{l_0}}}{s_{i_{l_0}}} \geq \frac{\pi_{i_{r_0}}}{s_{i_{r_0}}}$ , 与 $\frac{\pi_{i_{l_0}}}{s_{i_{l_0}}} < \frac{\pi_{i_{r_0}}}{s_{i_{r_0}}}$ 矛盾. 因此如果存在 $(l, r)$ 使得 $\frac{\pi_{i_l}}{s_{i_l}} < \frac{\pi_{i_{r}}}{s_{i_{r}}}$ , 那么我们一定能找到 $i_j, i_{j + 1}$ , 满足 $\frac{\pi_{i_j}}{s_{i_j}} < \frac{\pi_{i_{j+1}}}{s_{i_{j+1}}}$ . 记原平均读取用时为 $\overline{T}0$ , 交换 $i_j, i{j + 1}$ 后的平均读取用时为 $\overline{T}1$ , 则变化量 $$\Delta = \overline{T}1 - \overline{T}0 \= c[\pi{i{j + 1}}(\sum{k = 1}^{j - 1}s_{i_k} + s_{i_{j + 1}})) + \pi_{i_{j}}(\sum_{k = 1}^{j}s_{i_k} + s_{i_{j + 1}}) - \pi_{i_{j}}\sum_{k = 1}^{j}s_{i_k} - \pi_{i_{j + 1}}\sum_{k = 1}^{j + 1}s_{i_k}] \= c(\pi_{i_j}s_{i_{j + 1}} - \pi_{j+1}s_{i_j}) $$

由于 $$ \frac{\pi_{i_j}}{s_{i_j}} < \frac{\pi_{i_{j+1}}}{s_{i_{j+1}}} $$

故 $$ \pi_{i_j}s_{i_{j + 1}} < \pi_{j+1}s_{i_j} $$

所以 $$ \Delta<0 $$

每次这样的交换都会让 $\overline{T}$ 更小, 直到不能够交换为止. 因此, 将程序以 $\frac{\pi_i}{s_i}$ 不增的顺序排列能使平均读取时间最短.