笔记仓库

正常人的正常笔记集

贪心算法小试牛刀 (一)

本篇主要介绍贪心算法和其在一些简单规划问题上的应用,对应Stanford算法课(Algorithms: Design and Analysis, Part 2)第一周内容,在此仅给出一些浅显的综述性的结论和证明,主要针对典型的规划(调度)问题,含有部分相关习题。而涉及图论部分的贪心算法应用预计在几天后在另一篇笔记中具体给出。


贪心算法(Greedy Algorithm)是指通过每一步决策的局部最优达到整体的全局最优的一类算法。我们对这个算法并不陌生,无论知道不知道这个名字,对于此类算法的应用都十分熟悉。比如我们寻找单源最短路径的Dijkstra最短路径算法就是贪心策略的典型应用,接下来也会讲到找到最小生成树两种贪心算法,即Prim算法和Kruskal算法。

总的来说,对于很多优化问题,我们很容易想到用贪心算法来解决,这是非常直觉性的选择,对于已经证明正确的贪心算法,分析运行时间也很容易。然而,证明这些已有的贪心算法本来就不是件容易的事,针对于具体的优化问题,依赖于直觉创造出来的贪心算法更是很难保证得到最优解。实际上,大多数贪心算法确实不会给出最优解。

本篇将介绍一些贪心算法在规划(调度)问题上的应用,并使用一种较为普遍适应的证明方法,也就是交换参数(Exchange Argument)法证明这些贪心算法的正确性。


最优Caching

问题定义

系统调用内容(比如变量)的序列被称为页请求(Page Request),为了提高计算效率,“常用”的内容会被从大而慢的存储空间(内存)中取出,放入小而快的存储空间(比如Cache),而系统在发出请求时优先到Cache中寻找请求内容是否在其中,如果不在(Cache Miss / Page Fault)则放弃速度去内存中取出该内容,并用它替换Cache中现存的某个内容。

受限于Cache的容量,有时缺页再所难免,但如果能够在替换这一操作时合理选择被替换的页(内容),可以避免接下来多次不必要的缺页发生。

Furthest(Farthest) in future算法

对于Caching问题来说,我们定义衡量缺页算法的优劣是依据发生缺页的次数,miss发生得越少,代表算法越好。

解决Caching问题的最优算法是Belady在1960s提出的furthest-in-future算法1,正如字面所示,每当缺页发生时,替换掉在调度序列中从当前项开始最晚出现的项。

当Cache中的初始项和系统请求序列如下所示2

Cache a b c d e f
请求序列 g a b c e d a b b a c d e a f a d e f g h …

处理第一个请求g时发生了缺页,此时选择替换原Cache中的一项,根据furthest-in-future原则,选择g之后在请求序列中最晚出现且在原Cache中的项即f作为被替换的项。

定理

furthest-in-future算法是最优的Caching算法,也就是使缺页(更替)次数最小的算法。

这是非常典型的贪心策略,接下来我们将证明该算法的正确性。

证明

证明这个算法所使用的是对于贪心算法非常常用的交换参数法。

首先介绍一种较为一般性的Caching算法分类,即简化淘汰调度(Reduced Eviction Schedules):仅当一项被请求时才把该项插入Cache的调度。
非简化调度与简化调度,左第一列代表左边表示请求序列,接下来三列为Cache内容,标红的项为该步发送替换(淘汰)的项<sup id="fnref:2"><a href="#fn:2" rel="footnote">2</a></sup>
而所有的非简化调度都可以转化为缺页次数不超过原调度的简化调度。

对于给定任意一个调度$S$,都可以被转换为调度$S’$,而$S’$发生缺页的次数不多于$S$,证明如下

证明

假设$S$在$t$时刻在Cache中放入$d$,而此时并没有发生$d$的请求(这也是被称为非简化调度的原因),令$c$表示放入$d$前Cache中存在的项(即被替换的项)

那么存在以下两种情况:

第一种情况是$d$并没有被保存到$d$的下一次请求,在$t’$时刻收到了$e$的请求,于是放弃了$d$存入了$e$
Case 1:在$t'$时刻($d$被再次请求前)$d$被$e$替代
显然在结果上可以等效于$t’$时刻用$e$替换$c$的调度,$S \to S’$减少了一次替换

第二种情况则是在$d$被替换之前,又收到了$d$的请求,此时因为$d$在Cache中,没有发生缺页
Case 2:在$t'$时刻$d$被请求前没有发生替换
很显然可以等效于在$t’$时刻用$d$替换$c$,$S \to S’$替换发生的次数不变 ■

值得一提的是,对于简化淘汰调度来说,发生缺页的次数等于发生更替的次数,但对于非简化调度调度,因为不发生缺页也会换页(替代),此时考察缺页次数就没什么意义了,从问题定义中我们就假设了所有调度都是用的简化淘汰的方法避免讨论缺页&换页哪个作为优化目标的问题,最终目标都是要优化替换次数的。

通过以上证明,很容易得出结论,最优Caching调度一定是简化淘汰调度。

现在要证明一个定理

定理

对于任意$n \ge 0$且不超过请求队列长度的整数$n$,存在一个前$n$项所有换页都与farthest-in-future调度$S_{FF}$相同的最优简化淘汰调度$S$。

这个定理基本上就是直接说了farthest-in-future调度就是最优算法了。

仍然是“这也要证?”的废话证明的方法是归纳法:

首先当$n=0$时显然这个定理成立这不废话么

接下来我们假设当$n=j$时定理的结论成立,存在一个这样的$S$,需要证明当$n=j+1$时这个定理依然成立,因为是存在性证明,只需要借助于$S$构造一个前$j+1$项换页与$S_{FF}$完全一致的最优简化淘汰调度$S’$,这里假设第$j+1$个请求的内容为$d$,分为以下几种情况讨论:

Case 1

如果$d$已经在Cache中了,那么没有缺页发生,不存在换页,$S’=S$即可符合要求。

Case 2

如果$d$不在Cache中但$S$和$S_{FF}$换掉了同一项内容,依然可以令$S’=S$使命题成立。

这两种情况都没有在$S$的基础上增加$S’$的换页次数,$S’$依然是简化最优调度,且与$S_{FF}$在前$j+1$歩完全一致。

如果$d$不在Cache中,为了把$d$放入Cache,$S_{FF}$换掉了$e$,而$S$换掉了$f$且$f \ne e$,就是我们讨论的第三种情况。

在Case 3我们要证明的是换掉$e$不比换掉$f$差,这也就是$S_{FF}$的体现,现在构造基于$S$构造一个$S’$,把$S$的Cache中的$e$换成$f$

容易看出$S’$和$S$目前为止换页次数相同,既然$S$是最优的,$S’$目前(至少前$j+1$步)也可以认为是最优的。

$S$与$S'$在第$j+1$步换掉了不同的项,除此以外其他部分完全相同<sup id="fnref:2"><a href="#fn:2" rel="footnote">2</a></sup>

用$j’$表示在$j+1$步后$S$和$S’$第一次发生不同操作的歩数,这个操作也必然与$e$或$f$中至少一个相关,令$g$代表$j’$时刻的请求项

Case 3a: $g=e$

这是不可能发生的情况,$S_{FF}$要求替换最晚出现的项,既然在$S_{FF}$ 中已经换掉了$e$,说明$e$是当时Cache中最晚出现的,所以$e$的请求不可能先于$f$

Case 3b: $g=f$

$f$不在$S$的Cache中,假设接下来$S$换掉的Cache内容为$e’$

  • 如果$e’=e$,$S’$直接可以从Cache中获得$f$而不发生缺页,现在$S$和$S’$的Cache内容相同,
  • 如果$e’ \ne e$,$S’$把$e’$换成$e$后Cache内容和$S$相同,此事$S’$不是简化最优调度,但可以转化为换页次数不多于其本身的简化最优调度,而且根据Case 3a的讨论,转化后新的$S’$前$j+1$步也与$S_{FF}$一致

Case 3b: $g \ne e$且$g \ne f$

此时$S$必然换掉$e$,只需要$S’$换掉$f$,两者的Cache内容就再次相同

至此,我们找到了一个前$j+1$步换页与$S_{FF}$完全一致的简化最优调度$S’$,因此命题成立 ■

综上所述,当取$n$为调度队列长度时,命题依然成立,因此可以认为farthest-in-future算法是最优的Caching算法

后记

本文只是简单地介绍和证明了贪心算法的一个微小的应用,更多内容将在以后的笔记中给出。

笔记中的证明脉络主要参考了2,因为我认为这是我看见的材料中最清晰完整的证明,当然也有很多相关的资料可以阅读一下,比如3给出的是类似的思路而且更具体(实例化)一些,但符号标记问题可能看着有些麻烦;再如4紧扣Argument Exchange大法用词颇为规范当读上去略晦涩。

当然这个问题本身不是很实际,在实践中,几乎不可能一开始就知道完整的请求队列,更不可能知道将来最晚出现的是Cache中的哪一项,我们讨论的是离线Caching问题,可以在调度前就知道请求队列,而事实上比较受关注的问题是如何在不知道后面会请求什么内容的情况下的在线Caching问题,常用的是LRU算法5

至于为什么要费这么大力气去写farthest-in-future的证明,看似是毫无意义的茴香豆,实际上对于此类贪心算法证明的规范训练是件很有意义的事,至少有了这样的思路帮助我们看待其他问题的时候,依靠直接迅速找到一个正确的贪心算法,并知道怎样去证明这个贪心算法为什么是正确的,这是应用贪心算法过程中两个非常困难的问题,但很多时候解决的方法和farthest-in-future并无本质差异。