【学术讨论】有关存储管理的猜想

回复帖子

@chenfengna 2019-06-11 17:35 回复

如果你有2N个箱子,用于塞进你宿舍里的所有个人物品,考虑到日后取用方便,现定义"存取代价":存取代价由取出物体时需要移走的压在上面的物件个数、该物体的未来使用概率来衡量。现有人提出了一个猜想,不需要对存取代价进行解析,也可以得到最优解:对所有物件按未来使用频率和体积分别排序两次。分别从使用频率列表中选择最大、最小的两个物件,不常用的大物件和常用的小物件放A箱,不常用的大物件放下面 ;再从体积列表中选择最大、最小的两物件,常用的大物件和不常用的小物件放B箱,不常用的小物件放下面。每轮动作结束后,对调A、B所指代的箱子,重复上述过程,直到箱子装满,再拿来下一个箱子。当最终所有箱子都不留空隙后,该解为最优解。 如何证明这个猜想是正确的还是错误的?

@chenfengna 2019-06-11 19:33 回复 举报

之前那个被推翻了 于是我微调了一下:

如果你有2N个箱子,用于塞进你宿舍里的所有个人物品,考虑到日后取用方便,现定义"存取代价":存取代价由取出物体时需要移走的压在上面的物件个数、该物体的未来使用概率来衡量。 现有人提出了一个猜想,不需要对存取代价进行解析,也可以得到最优解: 第一步,对所有物件按未来使用频率和体积分别排序两次。分别从使用频率列表中选择最前、最后的两物件,再从体积列表中选择最前、最后的两物件,注意,每次对一个表作选择后,要分别对两个表作修改,即删除相应物体的记录。这样最终得到4类物件:常用物件,不常用物件,较大物件,较小物件。 第二步,对上述4组物体组内再次排序,常用组的较大物件和较小组的不常用物件放A箱,不常用者放底部,另一个放顶部(忽视重力,假设放在顶部后不掉下去);不常用组的较小物件和较大组的常用物件放B箱,较小者放底部,另一个放顶部。每轮动作结束后,对调A、B所指代的箱子,重复上述过程,直到箱子装满,再拿来下一个箱子。 猜想,当最终所有箱子都不留空隙后,该解为最优解。 如何证明这个猜想是正确的还是错误的?

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。