第三章贪心算法课件

算法设计与分析——贪婪算法2023/7/201我们来看一个找硬币的例子。假设有四种硬币，它们的面值分别为二角五分、一角、五分和一分。现在要找给某顾客六角三分钱。这时，我们会不假思索地拿出2个二角五分的硬币，1个一角的硬币和3个一分的硬币交给顾客。这种找硬币方法与其他的找法相比，所拿出的硬币个数是最少的。这里，我们下意识地使用了这样的找硬币算法：首先选出一个面值不超过六角三分的最大硬币，即二角五分；然后从六角三分中减去二角五分，剩下三角八分；再选出一个面值不超过三角八分的最大硬币，即又一个二角五分，如此一直做下去。这个找硬币的方法实际上就是贪婪算法。贪婪算法（greedyalgorithms,也叫登山法）2023/7/202顾名思义，贪婪算法总是作出在当前看来是最好的选择。也就是说贪婪算法并不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，我们希望贪婪算法得到的最终结果也是整体最优的。上面所说的找硬币算法得到的结果就是一个整体最优解。虽然贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。如图的单源最短路径问题，最小生成树问题等。在一些情况下，即使贪婪算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。2023/7/203设天平有一些25克的砝码，一些10克的砝码，一些5克的砝码和一些1克的砝码。现要称63克的物体，问至少需要用几个砝码。用贪婪算法，为了砝码数最少，在不超过63克的前提下，每次都尽量选择大的砝码，即头两次选25克的，然后选一个10克的，最后选三个1克的。总共用六个砝码，事实说明这是最好的结果。例1．选取砝码2023/7/204如果问题改成：砝码的种类分别为11克、5克和1克，待称的物体是15克。用贪婪算法应先选一个11克的，然后选四个1克的，共用五个砝码。这不是最优结果，只要用三个5克的砝码就够了。贪婪算法虽不能保证得到最优结果，但对于一些除了“穷举”方法外没有有效算法的问题，用贪婪算法往往能很快地得出较好的结果，如果此较好结果与最优结果相差不是很多的话，此方法还是很实用的。2023/7/205设有n=8个体积分别为54，45，43，29，23，21，14，1的物体和一个容积为C=110的背包，问选择哪几个物体装入背包可以使其装的最满。如直接用贪婪算法，将物体由大到小顺次装入背包，到装不下时再逐个试装更小的一些，直至试到最小的一个或装满为止。按此处所给数据，先装入54和45两个，容积尚余11，最后只能再装入体积为1的一个，总体积达到100，并不算太满。此方法的好处是节省时间，主要的运算时间是用来对n个元素进行排序，故其复杂性是O（nlogn）。例2.背包问题2023/7/206如果对上述算法作一些改进，可得到更好的结果。先从n个物体中试着取j个总体积不超过C的装入背包，剩下的(n-j)个物体则利用贪婪算法尽量往里装。此j值从零开始逐渐增加，反复进行试探，直至j达到某预先给定的常数k(0<k<n)，最后从这些结果中取其最好的一个。如果在试探中能得到一个完全装满的方案，则此过程就可提前结束。因为从n个物体中取出j个共有

种方案，此值随着j的增加而增加较快，但可以证明此改进算法的复杂性为O（knk+1）,因k是常数，故仍为多项式界的算法。2023/7/207按本例所给数值，取j=0时，因就是前述普通贪婪算法，已经得到100的结果；取j=1时，共有8种方案，当用29或23先装入时，可得到54+29+23+1=107的更好结果；取j=2时，共有28种方案，其中有能将背包完全装满的结果（43+23+29+14+1=110）。故知此问题当取k≥2时就可得到最优解。2023/7/208当n不太大时，适当的取k值，此改进方法常常可以得到最优解，但不能因此就说一般背包问题有多项式算法。当n增大时，k不能随着n不断的加大，如k随n增大而同时加大，其复杂性就是指数型而不是多项式型的了，而如k取值较小，又不能保证得出最优解。2023/7/209设有5座城市，城市间的距离矩阵为：例3．巡回推销员问题2023/7/2010将城市间的距离从小到大排列有：d24(1),d13(2),d15(2),d25(3),d45(6),d35(9),d34(9),d12(14),d14(16),d23(25)。

由于是5个城市，环绕一圈为5条边，贪婪方法求解此问题的过程是从最小边开始，依此从小到大取边加入到回路边集中，但在将1条边加入时不能使1顶点的度数超过3，也不能形成小回路。此问题解的过程如下：

2023/7/2011d24(1)；d24(1)+d13(2)；d24(1)+d13(2)+d15(2)；d24(1)+d13(2)+d15(2)+d25(3)；d24(1)+d13(2)+d15(2)+d25(3)+[d45(6)]；（下标中5出现了3次,顶点5有三条边相连,d45(6)放弃）d24(1)+d13(2)+d15(2)+d25(3)+[d35(9)]；（下标中5出现了3次,顶点5有三条边相连,d35(9)放弃）d24(1)+d13(2)+d15(2)+d25(3)+d34(9)。得到一条回路：v1→v3→v4→v2→v5→v1同由分枝限解方法得到的路径相同，因此是最佳的回路。2023/7/2012例4设有六个城市，其坐标分别为a(0,0),b:(4,3),c:(1,7),d:(15,7),e(15,4),f:(18,0)。如下图所示：2023/7/20136座城市间的距离矩阵为：2023/7/2014

用贪婪算法，先将任两城市间的连线距离按从小到大的次序排列，然后从中逐个选择。但有两种情况的连线应舍弃：

(1)使任一城市的度数（连线数）超过2的连线必须舍弃；

(2)在得到经过所有点的回路前就形成小回路的连线必须舍弃。

距离按从小到大的次序排列:Dde(3),Dab(5),Dbc(5),Def(5),Dac(7.07),Ddf(7.62),Dbe(11.01),Dbd(11.7),Dcd(14),Dbf(14.32),Dce(14.32),Dae(15.52),Dad(16.55),Daf(18),Def(18.38)2023/7/2015

按贪婪算法原则，其选择过程如下：Dde；Dde+Dab；Dde+Dab+Dbc；Dde+Dab+Dbc+Def；Dde+Dab+Dbc+Def+[Dac]；(形成小回路，舍弃)Dde+Dab+Dbc+Def+[Ddf]；(形成小回路，舍弃)Dde+Dab+Dbc+Def+[Dbe]；(b顶点度数超过2，舍弃)Dde+Dab+Dbc+Def+[Dbd]；(b顶点度数超过2，舍弃)Dde+Dab+Dbc+Def+Dcd；Dde+Dab+Dbc+Def+Dcd+[Dbf]；(b顶点度数超过2，舍弃)Dde+Dab+Dbc+Def+Dcd+[Dce]；(c、e顶点度数超过2，舍弃)Dde+Dab+Dbc+Def+Dcd+[Dae]；(e顶点度数超过2，舍弃)Dde+Dab+Dbc+Def+Dcd+[Dae]；(e顶点度数超过2，舍弃)Dde+Dab+Dbc+Def+Dcd+[Dad]；(d顶点度数超过2，舍弃)Dde+Dab+Dbc+Def+Dcd+Daf；得到1条回路2023/7/2016最后得到的回路如图（a）的结果，总长度为50。2023/7/2017不过，这不是此问题的最优解，此问题的最优解为下图所示的路径(可以用分枝限界等方法求得)，总长度为48.39。用贪婪方法得到的结果同最优解相比只多了3.3%。2023/7/2018设有n个独立的作业{1,2,…,n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的子作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

例5:多机调度问题2023/7/2019这个问题是一个NP完全问题，到目前为止还没有一个有效的解法。对于这一类问题，用贪婪选择策略有时可以设计出较好的近似算法。采用最长处理时间作业优先的贪婪选择策略可以设计出解多机调度问题的较好的近似算法。按此策略，当n≤m时，我们只要将机器i的[0,ti]时间区间分配给作业i即可。当n＞m时，我们首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。2023/7/2020例如，设7个独立作业{1,2,3,4,5,6,7}由3台机器M1,M2,和M3来加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。按贪婪算法产生的作业调度如图4-13所示，所需的加工时间为17。当n＞m时，因此算法所需的计算时间复杂度为O(nlogn)。2023/7/2021

一般情况下，用贪婪算法得到的是近似解，而不能保证得到最优解。但用贪婪方法计算最小生成树，却可以设计出保证得到最优解的算法。设G=(V,E)是一个无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的费用。在G的所有生成树中，费用最小的生成树称为G的最小生成树。网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v][w]表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。例6:最小生成树2023/7/2022

Kruskal

在1956年提出了1个最小生成树算法，它的思路很容易理解。设G=(V,E)是一个连通带权图，V={1,2,…,n}。将图中的边按其权值由小到大排序，然后作如下的贪婪选择，由小到大顺序选取各条边，若选某边后不形成回路，则将其保留作为树的一条边；若选某边后形成回路，则将其舍弃，以后也不再考虑。如此依次进行，到选够（n-1）条边即得到最小生成树。Kruskal最小生成树算法2023/7/2023例如，对于下图中的带权图各边按权值排序为：d13=1d46=2d25=3d36=4d14=

5d34=5d23=5d12=6d35=6d56=62023/7/2024按Kruskal算法选取边的过程如下图所示。d13=1d46=2d25=3d36=4d14=5d34=5d23=5d12=6d35=6d56=62023/7/2025

Prim在1957年提出另一种算法，这种算法特别适用于边数相对较多，即比较接近于完全图的图。此算法是按逐个将顶点连通的步骤进行的，它只需采用一个顶点集合。这个集合开始时是空集，以后将已连通的顶点陆续加入到集合中去，到全部顶点都加入到集合中了，就得到所需的生成树。设G=(V,E)是一个连通带权图，V={1,2,…,n}。构造G的一棵最小生成树的Prim算法的过程是：首先从图的任一顶点起进行，将它加入集合S中置，S={1}，然后作如下的贪婪选择，从与之相关联的边中选出权值c[i][j]最小的一条作为生成树的一条边，此时满足条件iS，jV-S，并将该j加入集合中，表示连两个顶点已被所选出的边连通了。Prim最小生成树算法2023/7/2026以后每次从一个端点在集合中而另一个端点在集合外的各条边中选取权值最小的一条作为生成树的一条边，并把其在集合外的那个顶点加入到集合S中，表示该点也已被连通。如此进行下去，直到全部顶点都加入到集合S中。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。由于Prim算法中每次选取的边两端总是一个已连通顶点和一个未连通顶点，故这个边选取后一定能将该未连通点连通而又保证不会形成回路。2023/7/2027例如，对于下图(a)中的带权图，按Prim算法选取边的过程如下图(b)所示。2023/7/2028设一个带权的图表示一交通运输网络，以图的各个顶点代表一些城市，图的各条边表示城市之间的交通运输路线，每条边的权值则表示此路线的长度或表示沿此路线运输所需花费的时间或运费等。运输路线往往是有方向性的，例如汽车运输有时会遇到单行路,而且不同的方向所花费的时间或尺价可能不同，例如汽车的上山和下山、水路的顺水和逆水花费的时间或代价就不相同，所以交通运输网络一般是有向图，所谓最短路径(Shortestpath)问题指的是：如果从图中某顶点出发(此点称为源点),经图的边到达另一顶点（称之为目的点）的路径不止一条，如何找到一条路径使沿此路径上各边的权值之和为最小。例7:最短路径2023/7/2029给定一个带权有向图G=(V,E),其中每条边的权是一个非负实数。另外,还给定V中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

Dijkstra于1959年提出了解决此问题的一般算法，此算法可按边的权值由小到大的次序，通过贪婪选择，逐步得到由给定源点到图的其余各点间的最短路径。其基本作法是，设置一个顶点集合S，一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源点。设vi是G的某一个顶点，我们把从源点到vi且中间只经过S中顶点的路称为从源点到vi的路径，并用数组dist来记录当前S中每个顶点所对应的最短路径长度。1．单源最短路径2023/7/2030

Dijkstra算法每次从V-S中取出具有最短路径长度的顶点vi，将vi添加到S中，同时检查vi添加到S中后，源点到V-S中各顶点的距离是否可以通过源点到vi的路径而缩短，如果缩短则对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。例如下图所示距离矩阵2023/7/2031现以顶点6为源点，求到其他各顶点的最短路径长度。2023/7/20322023/7/2033

例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其他顶点间最短路径的过程列在下页的表中。2023/7/2034迭代