算法设计与分析复习笔记第四章贪心算法

目录

贪心算法的概念

最小生成树

Prim算法

Kruskal算法

0-1背包问题

单源最短路径

Dijkstra （迪杰斯特拉）算法

活动安排问题

最优装载问题

旅行商问题

---

贪心算法的概念

贪心算法的适用情形

设待求解问题有N个输入，根据必须满足的条件和目标函数，希望从问题的所有允许解中求出最优值。

贪心算法的特点

贪心算法总是作出在当前来看是最好的选择。

就是说，贪心算法并不从整体最优上来考虑，所作出的选择只是某种意义上的局部最优选择。

贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。

这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。

贪心算法的一般框架

GreedyAlgorithm(parameters){

初始化；

重复执行以下的操作：

选择当前可以选择的(相容)最优解；

将所选择的当前解加入到问题的解中；

直至满足问题求解的结束条件。

}

最小生成树

设G = (V, E)是一个无向连通带权图，即一个网络。E的每条边(v, w)的权为c[v][w]。

如果G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。

生成树的各边的权的总和称为该生成树的耗费。

在G的所有生成树中，耗费最小的生成树称为G的最小(优)生成树。

（也就是包含G的所有顶点，同时权的和最小的树）

树的基本性质

连通无回路的图G称为树。

树是点比边多一的连通图，G连通且q=p–1 。

树是点比边多一的无回路图：G无回路且q=p–1

树若添条边就有回路：G无回路，但对任意的u, v∈V(G)，若

，则G+uv中恰有一条回路

树若减条边就不连通：G连通，但对

不连通。

n个顶点的连通图的生成树含有n – 1条边。

最小生成树的贪心选择性质

令G中权最小的边为e1 。首先必定有图G的一棵最小生成树包含了e1 。

选定第一条边e1以后，该如何选择第二条边呢？

Prim算法的做法：在保证连通的前提下依次选出权重较小的n – 1条边（在实现中体现为n个顶点的选择）。

Kruskal算法的做法：在保证无回路的前提下依次选择权重较小的n – 1条边。

Prim算法

基本思想：在保证连通的前提下依次选出权重较小的n – 1条边。

G=(V, E)为无向连通带权图，令V={1, 2, …, n}。

设置一个集合S ，初始化S = {1}，T = Φ。

贪心策略：如果V–S中的顶点j与S中的某个点i连接且(i, j) 的权重最小，于是就选择j(将j加入S)，并将(i, j) 加入T中 。

重复执行贪心策略，直至V–S为空。

给定一个连通带权图如下：

Prim算法中的数据结构

关键点：如何有效地找出满足条件

，且权c[i][j]最小的边(i,j)？

图用连接矩阵C[i][j]给出，即C[i][j]为结点i到结点j的权重。

标志数组S[i]指示顶点i是否已经加入到S中。

为了有效地找出V–S中满足与S中的某个点i连接且(i, j) 权重最小的顶点j，对其中的每个顶点j设立两个数组closest[j]和lowcost[j]：

closest[j]是S中与j最近的顶点，(closest[j], j)即为选中的边，而lowcost[j]是相应边的权重。

Prim算法的实现

Kruskal算法

基本思想：在保证无回路的前提下依次选出权重较小的n – 1条边。

贪心策略：如果(i, j)是E中尚未被选中的边中权重最小的，并且(i, j)不会与已经选择的边构成回路，于是就选择 (i, j)。

问题：如何知道(i, j)不会造成回路？

答：若边(i, j) 的两个端点i和j属于同一个连通分支，则选择(i, j) 会造成回路，反之则不会造成回路

因此初始时将图的n个顶点看成n个孤立分支。

Kruskal算法的例子

Kruskal算法的数据结构

结构数组e[]表示图的边，e[i].u、e[i].v和e[i].w分别表示边i的两个端点及其权重。

函数Sort(e, w)将数组e按权重w从小到大排序。

一个连通分支中的顶点表示为一个集合。

函数Initialize(n)将每个顶点初始化为一个集合

函数Find(u)给出顶点u所在的集合。

函数Union(a, b)给出集合a和集合b的并集。

重载算符!=判断集合的不相等。

Kruskal算法的实现

Prim与Kruskal两算法的复杂性

贪心算法也能获得最优解

证明题：用Kruskal算法得到的生成树T*必是最优树。

0-1背包问题

给定n个物品和一个背包。物品i的重量为wi，价值为vi，背包容量为c。问如何选择装入背包中的物品，使得装入背包的物品的价值最大？

在装入背包时，每种物品i只有两种选择，装入或者不装入，既不能装入多次，也不能只装入一部分。因此，此问题称为0-1背包问题。

如果在装入背包时，物品可以切割，即可以只装入一部分，这种情况下的问题称为背包问题。

0-1背包问题不适用贪心算法

但是背包问题却是适用贪心算法的。

贪心算法的基本要素

贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。

贪心选择每次选取当前最优解，因此它依赖以往的选择，而不依赖于将来的选择。

贪心算法通常以自顶向下的方式进行，每次贪心选择就将原问题转化为规模更小的子问题。

最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

如何确定贪心选择性质

证明贪心选择将导致整体的最优解：

首先证明存在问题的一个整体最优解必定包含了第一个贪心选择。

然后证明在做了贪心选择后，原问题简化为规模较小的类似子问题，即可继续使用贪心选择。

于是用数学归纳法可证明，经过一系列贪心选择可以得到整体最优解。

单源最短路径

给定一个图G = (V, E)，其中每条边的权是一个非负实数。另外给定V中的一个顶点v，称为源。求从源v到所有其它各个顶点的最短路径。
单源最短路径问题的贪心选择策略：选择从源v出发目前用最短的路径所到达的顶点，这就是目前的局部最优解。

单源最短路径的贪心算法

基本思想：首先设置一个集合S；用数组dis[]来记录v到S中各点的目前最短路径长度。然后不断地用贪心选择来扩充这个集合，并同时记录或修订数组dis[]；直至S包含所有V中顶点。

贪心选择：一个顶点u属于S当且仅当从v到u的最短路径长度已知。

初始化：S中仅含有源v。

Dijkstra （迪杰斯特拉）算法

Dijkstra 算法的做法是：由近到远逐步计算，每次最近的顶点的距离就是它的最短路径长度。然后再从这个最近者出发。即依据最近者修订到各顶点的距离，然后再选出新的最近者。如此走下去，直到所有顶点都走到。

Dijkstra算法举例

最开始从1开始，与1连通的有2，4，5。1到2=10，1到4=30，1到5=100，其中最小的是10，

接下来从2开始，与2连通的有3。1经过2到3=50+10=60，再继承上一轮的30，100，其中最小的是30，

接下来从4开始，与4连通的有3和5。1经过4到3=30+20=50，1经过4到5=30+60=90，其中最小的是50，

接下来从3开始，与5连通，2and4已确定故忽略。1到5的最短距离为50+10=60.

Dijkstra算法的贪心选择性质

Dijkstra 算法中所做的贪心选择是：若u是V–S中具有最短路径的特殊顶点，就将u选入S，并确定了从源到u的最短路径长度dis[u]。

为什么从源到u没有更短的路径呢？
若有，则将如下图所示：
?

若该路径经S外一点x到达u，则：dis[x]+d(x, u)＜dis[u]从而 dis[x]＜dis[u]，这与u的选取矛盾（因为u当时是距离最短的顶点）

Dijkstra算法的计算复杂性

活动安排问题

设有n个活动的集合E = {1, 2, …, n}，其中每个活动都要求使用同一资源，且在同一时间里只能有一个活动可以使用该资源。现要求给出一个活动安排，使得利用该资源活动为最多。

每个活动i都有使用该资源的一个启始时间si和一个结束时间fi，si＜fi，其占用资源的时间为半开区间[si , fi)。若区间[si , fi)与区间[sj , fj)不相交，则称活动i与活动j是相容的。

活动安排问题就是求E的最大相容活动子集。

活动安排的例子

贪心法求解活动安排问题的关键是如何选择贪心策略，使得按照一定的顺序选择相容活动，并能安排尽量多的活动。至少有两种看似合理的贪心策略：

（1）最早开始时间：可以增大资源的利用率。 （2）最早结束时间：可以使下一个活动尽早开始。

由于活动占用资源的时间没有限制，因此，后一种贪心选择更为合理。

活动安排问题的贪心算法

基本思想：某项活动结束时间愈早，安排其它活动的剩余区间愈大。所以贪心策略为尽量选择结束时间早的活动来安排。为此，将活动按结束时间的非减顺序排序，即f1≤f2≤…≤fn。显然排序需要的时间为O(nlogn)。

贪心选择：当安排下第i个活动后，可能有：fi>si+1，所以第i+1个活动无法安排，这就必须舍弃第i+1个活动，检测第i+2个活动……直到第i+k个活动的si+k>fi，就把此活动安排进来。

活动安排的例子

先将所有活动按照结束时间f[i]递增排序

首先选定活动1，其结束时间f[1]=4。然后因s[4] = 5≥4，选定活动4，这时f[4] = 7。又因s[8] = 8≥7，选定活动8，这时f[8] = 11。最后因s[11] = 12≥11，选定活动11。最终的活动安排为：1、4、8和11

活动安排的贪心算法

将所有活动按结束时间排序，得到活动集合E={e1,e2…en}；先将e1选入结果集合A中，即A={e1}；依次扫描每一个活动ei：如果ei的开始时间晚于最后一个选入A的活动ej的结束时间，则将ei选入A中，否则放弃ei；

活动安排贪心算法的实现

算法正确性证明

需要证明：

活动安排问题有一个最优解以贪心选择开始；

活动安排问题具有最优子结构；

算法每一步按照贪心选择计算，最终可得到原问题的一个最优解。

贪心算法能够得到活动安排问题的最优解

设活动集合E={1, 2, …, n}已按结束时间的非减顺序排列，活动1具有最早结束时间。

首先必定有最优解包含活动1。否则设A是E的最优解，且A中最早结束的活动是k。若k＞1，则活动1必与A中除k以外的活动相容。令B=A–{k}∪{1}，则B也是最优解。

进一步，假设A是原问题的包含活动1的最优解，则A’=A–{1}是活动集合E’={i∈E且si≥f1}的一个最优解。反之，如果能够找到E’的一个解B’，它包含了比A’更多的活动，则将活动1加入到B’中将产生E的一个解B，它包含比A更多的活动。这与假设矛盾。

因此，所做的每一步贪心选择都将产生一个比原问题规模更小的具有相同特征的子问题。由数学归纳法可知，贪心法得到的是最优解。

算法复杂性分析

算法由两部分组成：

第一部分是排序，时间复杂度为O(nlogn)；

第二部分是选择合适的活动，是一个定长循环，时间复杂度为O(n)；

故总的时间复杂度为O(nlogn)。

最优装载问题

有一批集装箱要装上一艘载重为C的轮船。其中集装箱i的重量为Wi。假定装载体积不受限制，要将尽可能多(这个多，是指的货物数目)的集装箱装上轮船。

该问题的形式化描述为：

有约束条件

其中，xi=0表示不装入集装箱，xi=1反之。

最优装载问题的贪心算法

基本思想：这个题目比较简单，可以用贪心法求解。每次采用重量最轻者优先装入的贪心选择策略

贪心算法能够得到最优装载问题的最优解

S(B)=S(A)+wm

算法复杂性分析

很容易看出，算法主要的时间消耗在排序上，时间复杂度也和排序相同，是O(nlogn)。

旅行商问题

推销员从某城市出发，遍历n个城市最后返回出发城市。设从城市i到城市j的费用为c[i][j]，如何选择旅行路线使得该推销员此趟旅行的总费用最小?

图论语言表述：给定n个节点简单无向完全图G=<V,E,c>，c(i,j)是节点i到j的代价(边权)。在G中求遍历所有节点简单回路C，使C上所有边权的和最小。

旅行商问题的贪心算法

基本思想：首先设置一个集合Path和当前节点v，然后不断地用贪心选择来扩充这个集合，直至Path包含所有V中顶点。

贪心选择：如果V–Path中的顶点j是与当前节点v相邻接的顶点中边权最小的，于是就选择j(将j加入Path)，并将j作为新的当前节点 。

初始化：Path中仅含有源v。

最临近算法中的数据结构

图用连接矩阵W[i][j]给出，即W[i][j]为结点i到结点j的权重。

Path[]记录依次连接的城市，p记录当前到达的最后一个顶点，cost为当前路径长度。

如果节点k已经到达，则arrived[k]=true。

旅行商问题的最临近算法

旅行商算法举例

最临近法不保证求得旅行商问题的精确解，只能得到问题地近似解。一般地，贪心选择只依赖于前面选择步骤地最优性，因此是局部最优的，所以贪心法不能够确保求出问题的最优解。

改进的旅行商算法

如果分别从节点i出发（i=1,2,..n）执行算法Tray_Greedy，通过结果比较，取最小代价回路，可以求得更接近于最佳解的近似解。

Tray_Greedy算法的计算复杂性