《编程之美》4.5磁带文件存放优化:最优解是怎样炼成的

简介:

问题描述:

  要定义磁带上第n个文件,须要依次经过前面n-1个文件。假设磁带上有n个文件,长度分别为L[0],L[1], ..., L[n-1]且被访问的概率分别为P[0],P[1],...,P[n-1],请问怎样安排它们在磁带上的存储顺序最好?

分析:

  最好的安排方式应该对应期望最小的方式。思考一下,不难写出期望的表达式: 

(注意,访问第i个文件,因为要完整地读入这个文件,经过的长度是L[0]+L[1]+...+L[i],不是L[0]+L[1]+...+L[i-1]。我第一次写的时候就写错了。)

  这时就犯难了:L[0],L[1], ..., L[n-1]与P[0],P[1],...,P[n-1]一一对应,那么期望E实际上是序列的函数——这个序列指把n个L和对应的P放入L[0...n-1]和P[0...1]中——每种序列对应了一个E的值。这可如何求呢?

  《编程之美》先探讨了两种简单情况:

P[0]=P[1]=...=P[n-1],即概率相等时,把最长的文件放前面、最短的文件放后面L[0]>=L[1]>=...>=L[n-1]时,期望最小;

L[0]=L[1]=...=L[n-1],即长度相等时,按概率大小从大到小排列,期望最小。

  概率和长度都不同时怎么办呢?《编程之美》提出了一个折中方案,并举了L[0]=10,L[1]=6,P[0]=0.4,P[1]=0.6的例子来验证:

按照P/L由大到小排列构造序列。

  P/L?嗯,确实综合考虑P和L两个因素了。其实有很多数学模型不都是这样嘛,将正相关的做分子,负相关的做分母。但这里是求解,而不是建模啊。如果你也满足于此,那下面就不用看了。为了证明这种方式确实是最优的,先是想了一些主题在网上搜索了一些资料,虽然都不是很满意,不过受到了不少启发。先列举一下这些资料的链接和启发,再来谈谈我的思路,如果没有兴趣看这些资料可以直接跳过这部分:

关于编程之美4.5.磁带文件存放优化算法的解释:分割很好理解,我们把等概率的来自同一文件单位长度的分割后的新文件串在一起。但是,我们访问文件时一定要读到文件的尾端,而不是这些分割后的单个文件的尾端,怎么合并,就不好理解了,我没有再深入下去。

《编程之美》读书笔记15: 4.5 磁带文件存放优化:交换的思路很不错,但是这篇博文只限于相邻交换,似乎有局限性,怎么通过交换来获得最优解?

磁带文件存放优化:(很不幸,没找到原出处)证明贪心解是最优解的思路很好,而且这篇博文提到的交换方式从适用性来看要由于上一篇,但是证明过程写的并不是很简练易懂;不过总的来说,这篇文章给我的启发最大。

 

  下面给出我对这个问题的分析。

  在我们上文提到的贪心解也即按照P/L由大到小排列的序列中,我们考察其中i到j这一段,并采取把最末的j插入到i前面,i到j-1整体后移,即下图所示:

  可以写出后者减去前者的期望变化量为:ΔE=L[j](P[i]+...+P[j-1]) - (L[i]+...+L[j-1])P[j]。由于P[j]/L[j]<=P[j-1]/L[j-1]<=...<=P[i]/L[i],每个对应项相减都非负,其和ΔE也非负。我总结了一个规律:

  更一般地,对于任意序列,如果其中存在一个子序列i...j且P[j]/L[j]最小,经过这样的调整,新序列对应的期望E总是不减的,而且当P/L不全相等时,新期望值总会增加。反之,如果做相反的操作,把P/L大的调整到前面,那么在没有相等的情况下,新序列的的期望总会减少,直到最后不能再调整,也即P/L从大到小排列时,期望E最大。

  
  根据这个规律,就说明了为什么“按照P/L由大到小排列构造序列”获得的是最优解了。

  太抽象、不好理解?No problem,拿一个例子来说明。

  假定有一个P/L值为5、4、3、2、1构成的序列,那么在所有可能的排序中,5 4 3 2 1应该是最优解。而对于其他排列,比如2 3 5 4 1,用上面的方法调整为最优解的过程,就是其期望E不断变小的过程。这个调整过程是:

      2      3      5      4      1            (1)原始序列,5调到2前面

      5      2      3      4      1            (2)4调到2前面

      5      4      2      3      1            (3)3调到2前面

      5      4      3      2      1            (4)已经找不出序列i...j使得Pj/Lj大于序列中其他值,调整结束

  这个调整过程看上去是不是很熟悉?没错,它和选择排序很像,殊途同归。我一开始没有想到这个期望最小化问题居然能和选择排序扯上了关系,直到挖掘到这一步。同时,用选择排序说明了,所有的序列最终都能转化成一个从大到小的排列,也即,所有序列转化成最优解时,对应期望E都在不断地减少(如果所有P/L都不等),“最优解”确实是最优解。最优解是怎么炼成的,这下明白了吧?




本文转自五岳博客园博客,原文链接:www.cnblogs.com/wuyuegb2312/p/3182896.html,如需转载请自行联系原作者

目录
相关文章
【动态规划上分复盘】下降路径最小和|礼物的最大价值
【动态规划上分复盘】下降路径最小和|礼物的最大价值
|
7月前
|
存储 算法
代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
40 1
|
7月前
|
存储 算法 决策智能
非启发式算法学习知识目录
非启发式算法学习知识目录
72 0
数据在内存中的存储(超级无敌究极详细!)
数据在内存中的存储(超级无敌究极详细!)
|
机器学习/深度学习 传感器 安全
2023 年高教社杯D题圈养湖羊的空间利用率思路及参考代码(持续更新)
2023 年高教社杯D题圈养湖羊的空间利用率思路及参考代码(持续更新)
|
算法 C++
【软/自考】算法实用技巧——递归VS迭代
【软/自考】算法实用技巧——递归VS迭代
91 0
|
机器学习/深度学习 存储 人工智能
啊哈 算法读书笔记 第 1 章 一大波数正在靠近——排序
首先出场的是我们的主人公小哼,上面这个可爱的娃就是啦。期末考试完了老师要将同 学们的分数按照从高到低排序。小哼的班上只有 5 个同学,这 5 个同学分别考了 5 分、 3 分、 5 分、 2 分和 8 分,哎考得真是惨不忍睹(满分是 10 分)。接下来将分数进行从大到小排序, 排序后是 8 5 5 3 2 。你有没有什么好方法编写一段程序,让计算机随机读入 5 个数然后将这 5 个数从大到小输出?
91 0
|
存储
【锟斤拷�⊠是怎样炼成的】——两分钟帮你彻底弄懂计算机的编码原理
【锟斤拷�⊠是怎样炼成的】——两分钟帮你彻底弄懂计算机的编码原理
205 0
树的储存形势&代码实现(跑路人笔记1)
树的储存形势&代码实现(跑路人笔记)
树的储存形势&代码实现(跑路人笔记1)