第三章贪心算法优秀课件.pptVIP

第三章贪心算法

2024/11/13计算机算法设计与分析2找硬币假设有四种硬币，面值分别为二角五分一角五分一分现在要找给某顾客六角三分钱，哪种找钱方法拿出的硬币个数最少呢？二角五分二角五分一角一分一分一分首先选出一个面值不超过六角三分的最大硬币，即二角五分；然后从六角三分中减去二角五分，剩下三角八分；再选出一个面值不超过三角八分的最大硬币，即又一个二角五分，如此一直做下去。这种方法实际上就是贪心算法。

2024/11/13计算机算法设计与分析3再找硬币若硬币的面值改为一分、五分和一角一分3种，而要找个顾客的是一角五分钱。还用贪心算法，将找个顾客1个一角一分的硬币和4个一分的硬币。然而，3个五分的硬币显然才是最好的找法。

2024/11/13计算机算法设计与分析4贪心算法的特点贪心算法总是作出在当前来看是最好的选择。就是说，贪心算法并不从整体最优上来考虑，所作出的选择只是某种意义上的局部最优选择。当然希望贪心算法得到的最终结果是最优的。可是贪心算法并不能保证最终结果是最优的。不过，在许多情况下，应用贪心算法能够得到整体最优解；并且在一些情况下，即使得到的不是最优解，也是一个很好的近似解。

2024/11/13计算机算法设计与分析5贪心算法的一般框架GreedyAlgorithm(parameters){初始化；重复执行以下的操作：选择当前可以选择的(相容)最优解；将所选择的当前解加入到问题的解中；直至满足问题求解的结束条件。}

2024/11/13计算机算法设计与分析6最小生成树设G=(V,E)是一个无向连通带权图，即一个网络。E的每条边(v,w)的权为c[v][w]。如果G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树的各边的权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小(优)生成树。

2024/11/13计算机算法设计与分析7树的基本性质连通无回路的图G称为树。树是点比边多一的连通图，G连通且q=p–1。树是点比边多一的无回路图：G无回路且q=p–1树若添条边就有回路：G无回路，但对任意的u,v∈V(G)，若uv?E(G)，则G+uv中恰有一条回路树若减条边就不连通：G连通，但对?e∈E(G),G–e不连通。n个顶点的连通图的生成树含有n–1条边。

若G的任何最小生成树都不包含e1。设T为G的最小生成树，e1?T。于是T+e1是一个有回路的图且该回路中包含e1。该回路中必有条不是e的边ei。令T’={T+e1}–ei。T’也是G的生成树。又c(T’)=c(T)+c(e1)–c(ei)，c(e1)≤c(ei)，从而c(T’)≤c(T)，T’是G的最小生成树且含有边e1。矛盾。故必定有图G的最小生成树包含了e1。2024/11/13计算机算法设计与分析8最小生成树的贪心选择性质令G中权最小的边为e1。首先必定有图G的一棵最小生成树包含了e1。选定第一条边e1以后，该如何选择第二条边呢？依据各条边的权重，依次选出权重较轻的n–1条边。这n–1条边必定包括了G的n个顶点。这样就得到了G的一棵最小生成树。这样做是否可以呢？不行！因为不能保证这n–1条边构成树？要保证这n–1条边构成树，必须使这n–1条边是连通的或者是无回路的。Prim算法的做法：在保证连通的前提下依次选出权重较小的n–1条边（在实现中体现为n个顶点的选择）。Kruskal算法的做法：在保证无回路的前提下依次选择权重较小的n–1条边。

2024/11/13计算机算法设计与分析9Prim算法基本思想：在保证连通的前提下依次选出权重较小的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为空。

2024/11/13计算机算法设计与分析10Prim算法中的数据结构图用连接矩阵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]是相应边的权重。

2024/11/13计算机算法设计与分析11Prim算法的实现Prim(intn,Type**c){初始化：结点1