// 来自算法设计一书94页开始。
算法描述
已知缓存的大小以及访问元素的顺序，每次需要放入新的并且缓存已经满的情况（即缺失）下从缓存中去除下一个相同元素在最远的将来被访问到的元素。
证明
要证明算法的最优，需要说明不存在以下情况：其他方法回收在某一步的元素比上述算法在相同步骤回收的元素更远。但是可以证明，如果这种情况发生，会有别的位置的元素比这个算法更近，总的效果不会更好。
定义简化的调度为：只有在需要某个元素的时候才把这个元素放入缓存中。可以说明每一个非简化的调度都有对应的简化的调度（把放入元素的时机推后到该元素被使用即可）并且不会使得总的缺失次数变多。并且简化调度放入的项数就是缺失次数（不包含刚开始缓存没有满的时候放入的）
- 证明最远将来规则的最优性（即对于任意序列，由最远将来规则产生的调度 $S_{FF}$ 可以由 最小缺失次数的调度 $S’$ 转化过来并且不增加缺失次数。
- 首先证明：对于$j$，如果$S$和$S_{FF}$前$j$次回收相同，则存在另一个简化调度$S’$使得$S’$和$S_{FF}$在$j+1$次回收相同并且不比$S$产生更多的缺失：
- 在第$j+1$次回收的时候回收了不同的元素，假设$S$回收了$f$而$S_{FF}$和$S‘$回收了$e$，故必须让$S’$试图尽快回到和$S$相同的状态同时不产生不必要的缺失。
- 从第$j+2$次开始，就让$S’$和$S$的回收策略相同，直到：
- 如果某个位置，$S$回收了$e$，则直接让$S’$回收$f$即可。之后就和$S$一样了。
- 如果某个位置有$f$的需求（只会首先有$f$的需求而不会有$e$的需求，因为$e$是最远的），则$S$会扔掉某个元素并且放入$f$。在这种情况下，只需要将$S’$中对应的元素也扔掉，放入$e$即可。（之后可以改变放入$e$的位置以简化）之后就和$S$一样了。如果对应的元素就是$e$，就说明$S’$更好……（这种情况应该不会发生的），所以$S’$不会比$S$差。
- 首先证明：对于$j$，如果$S$和$S_{FF}$前$j$次回收相同，则存在另一个简化调度$S’$使得$S’$和$S_{FF}$在$j+1$次回收相同并且不比$S$产生更多的缺失：
既然已经说明，上述算法产生的序列有对应的缺失相同的最优序列，所以他就是最优的……证毕。
实际情况
实际上不可能直接这样直到要访问的，所以就考察已经访问过的，扔掉上一次访问最早的元素。（相当于把上述过程的序列倒过来）