算法导论-ch16 greedy algorithms

《算法导论-ch16 greedy algorithms》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析DesignandAnalysisofAlgorithms主讲人徐云FallFall2012,2012,USTCUSTCPart1FoundationPart2SortingandOrderStatisticsPart3DataStructurePart4AdvancedDesignandAnalysisTechniqueschap15DynamicProgrammingchap16chap16GreedyAlgorithmsGreedyAlgorithmschap17AmortizedAnalysisPart5AdvancedDataStructuresPar

2、t6GraphAlgorithmsPart7SelectedTopicsPart8Supplement第16章章贪心算法贪心算法16.1方法概述16.2小数背包16.3活动安排1616416.4最优装载16.5找钱问题16.1方法概述基本思想求解步骤适合求解问题的特征存在的问题与动态规划法的比较示例2012/10/31算法设计与分析4基本思想从问题的某一个初始解出发，通过一系列的贪心选择——当前状态下的局部最优选择，逐步逼近给定的目标，尽可能快地求得更好的解。在贪心算法（greedymethod）中也采用逐步构造最优解的方法。在每个阶段，都作出一个按某个评价函

3、数最优的决策，该评价函数最优称为贪心准则（greedycriterion）。贪心算算性法的正确性，就是要证明按贪心准则求得的解是全局最优解。贪心算法不能对所有问题都得到全局最优解。但对许多问题它能产生全局最优解，如单源最短路经问题，最小生成树问题等。2012/10/31算法设计与分析5求解步骤从问题的某一初始解出发；while依据贪心策略朝给定目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；2012/10/31算法设计与分析6适合求解问题的特征贪心选择性质：可通过局部最优（贪心）选择达到全局最优解；－通常以自顶向下的方式进行，每每择次选择后将

4、问题转化为规模更小的子问题；－该性质是贪心法使用成功的保障，否则得到的是近优解；最优子结构性质：问题的最优解包含它的子问题的最优解；－并不是所有具有最优子结构性质的问题都可以采用贪心策略；－往往可以利用最优子结构性质来证明贪心选择性质；2012/10/31算法设计与分析7存在的问题如果不满足贪心选择性质，贪心算法存在：不能保证求得的最后解是最优的；只能求满足某些约束条件范围的局部最优解。注：贪心算法虽不能保证得到最优结果，但对于一些除了“穷举”方法外没有有效算法的问题，用贪心算法往往能很快地得出较好的结果，此方法还是很实用的。2012/10/31算法设计与分析8与动态规

5、划法的比较DynamDynamcrogrammngicProgrammingGreedygorthmsyAlgorithmsAteachstep,thechoiceAteachstep,wequicklymakeaisdetermsdetermnedbasedoninedbasedonchochocethatcurrentlylooksbest.icethatcurrentlylooksbest.solutionsofsubproblems.-Alocaloptimal(greedy)choice.Sub-problemsaresolvedGreedychoGreedycho

6、cecanbemadeicecanbemadefirst.firstbeforesolvingfurthersub-problems.Bottom-uphapproachTop-dhdownapproachCanbeslower,morecomplexUsuallyfaster,simpler2012/10/31算法设计与分析9示例（1）例1:两种背包问题(1)0-1背包问题(2)小数背包问题两种背包问题都满足最优子结构性质，都可以用动态规划来求解；小数背包问题还具有贪心选择性质，用贪心法求解更简单、更快速（见16.2节）；但0-1背包问题用贪心法求解不一定能得到最优解；2

7、012/10/31算法设计与分析10示例（2）例2:找钱问题：用最少的货币数找出钱A(1)货币数量和种类不限制情形：具有贪心选择性质，可以使用贪心法：按货币单位从高往低给付，总能得到最优解（见16516.5节）。(2)货币数量和种类有限制情形：贪心法并不总能得到最优解设n个货币P{p,p,...,p},d和x分别是p的货币单位和选择的12niii数量，问题的形式描述为：nminxii1ndixiAs.t.i1x0,1xi0,12012/10/31算法设计与分析11示