第4章贪心算法ppt课件.pptx

2023/10/11计算机算法设计与分析1第四章贪心算法

2学习要点? 理解贪心算法的概念。? 掌握贪心算法的基本要素：（1）最优子结构性质（2）贪心选择性质理解贪心算法的一般理论通过应用范例学习贪心设计策略。最小生成树；单源最短路径；旅行商问题；活动安排问题；最优装载问题；

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

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

贪心算法的适用情形52023/10/11计算机算法设计与分析设待求解问题有N个输入，根据必须满足的条件和目标函数，希望从问题的所有允许解中求出最优值。

贪心算法的特点62023/10/11计算机算法设计与分析贪心算法总是作出在当前来看是最好的选择。就是说，贪心算法并不从整体最优上来考虑，所作出的选择只是某种意义上的局部最优选择。贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。 这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。

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

煤气管道的铺设某新建小区着手铺设煤气管道，已知每一幢楼的接入位置和距离，请求出最短的铺设方案。82023年10月25日

学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们之间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。92023年10月25日最优布线问题

最优通信网102023年10月25日若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。

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

树的基本性质122023/10/25计算机算法设计与分析连通无回路的图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条边。

2023年10月25日13实例BAED70605090757530080200BCAED705090300BCAED708050300BCAED706080C 50

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