磁带文件存放优化
《编程之美》4.5
书上给出的算法属于贪心算法。关于贪心算法,最重要的在于证明其正确性。
1、证明贪心选择性。
设X={x1,x2,x3,…,xn}是一个最优解.其中,作业xi的长度为L[xi],访问的概率为P[xi]。
设Y={y1,y2,y3,…,yn}是一个贪心解。其中,P[yi]/L[yi]>=P[y(i+1)]/L[y(i+1)]。
如果X和Y完全一样,则贪心解就是一个最优解。
如果X和Y不一样,设xi和yi是第一个不同的作业。设yi是X中的xj。
X=x1,x2,x3,..,xi,…,xj,…,xn
把xj插入到xi的前边,则X变成
X’=x1,x2,x3,…,xj,xi,…,xn
设X的代价是E(X),X’的代价是E(X’)......
阅读全文