贪心算法ch16

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

1、算法设计与分析算法设计与分析DesignandAnalysisofAlgorithmsDesignandAnalysisofAlgorithmsDesignandAnalysisofAlgorithms主讲人主讲人徐徐云云FallFall20102010,,USTCUSTCPart1FoundationPart2SortingandOrderStatisticsPart3DataStructurePart4AdvancedDesignandAnalysisTechniqueschap15DynamicProgrammingcha

2、p16GreedyAlgorithmschap17AmortizedAnalysisPart5AdvancedDataStructuresPart6GraphAlgorithmsPart7SelectedTopicsPart8Supplement第第1616章章贪心算法贪心算法16.116.1方法概述方法概述16.216.2小数背包小数背包16.316.3活动安排活动安排16.416.4最优装载最优装载16.516.5找钱问题找钱问题16.1方法概述ò基本思想ò求解步骤ò适合求解问题的特征ò存在的问题ò与动态规划法的比较ò示例2

3、010-10-13算法设计与分析4基本思想ò从问题的某一个初始解出发，通过一系列的贪心选择——当前状态下的局部最优选择，逐步逼近给定的目标，尽可能快地求得更好的解。ò在贪心算法（greedymethod）中也采用逐步构造最优解的方法。在每个阶段，都作出一个按某个评价函数最优的决策，该评价函数最优称为贪心准则（greedycriterion）。ò贪心算法的正确性，就是要证明按贪心准则求得的解是全局最优解。ò贪心算法不能对所有问题都得到全局最优解。但对许多问题它能产生全局最优解，如单源最短路经问题，最小生成树问题等。2010-10-

4、13算法设计与分析5求解步骤从问题的某一初始解出发；while依据贪心策略朝给定目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；2010-10-13算法设计与分析6适合求解问题的特征ò贪心选择性质：可通过局部最优（贪心）选择达到全局最优解；－通常以自顶向下的方式进行，每次选择后将问题转化为规模更小的子问题；－该性质是贪心法使用成功的保障，否则得到的是近优解；ò最优子结构性质：问题的最优解包含它的子问题的最优解；－并不是所有具有最优子结构性质的问题都可以采用贪心策略；－往往可以利用最优子结构性质来证明贪

5、心选择性质；2010-10-13算法设计与分析7存在的问题如果不满足贪心选择性质，贪心算法存在：ò不能保证求得的最后解是最优的；ò只能求满足某些约束条件范围的局部最优解。注：贪心算法虽不能保证得到最优结果，但对于一些除了“穷举”方法外没有有效算法的问题，用贪心算法往往能很快地得出较好的结果，此方法还是很实用的。2010-10-13算法设计与分析8与动态规划法的比较DynamicProgrammingGreedyAlgorithmsAteachstep,thechoiceAteachstep,wequicklymakeaisdet

6、erminedbasedonchoicethatcurrentlylooksbest.solutionsofsubproblems.-Alocaloptimal(greedy)choice.Sub-problemsaresolvedGreedychoicecanbemadefirst.firstbeforesolvingfurthersub-problems.Bottom-upapproachTop-downapproachCanbeslower,morecomplexUsuallyfaster,simpler2010-10-1

7、3算法设计与分析9示例（1）ò例1:两种背包问题(1)0-1背包问题(2)小数背包问题两种背包问题都满足最优子结构性质，都可以用动态规划来求解；小数背包问题还具有贪心选择性质，用贪心法求解更简单、更快速（见16.2节）；但0-1背包问题用贪心法求解不一定能得到最优解；2010-10-13算法设计与分析10示例（2）ò例2:找钱问题：用最少的货币数找出钱A(1)货币数量和种类不限制情形：具有贪心选择性质，可以使用贪心法：按货币单位从高往低给付，总能得到最优解（见16.5节）。(2)货币数量和种类有限制情形：贪心法并不总能得到最优解

8、设n个货币P={p,p,...,p},d和x分别是p的货币单位和选择的12niii数量，问题的形式描述为：n⎧⎫min⎨∑xi⎬⎩i=1⎭n⎧⎪∑dixi=As.t.⎨i=1⎪x=0,1⎩i2010-10-13算法设计与分析11示例（3）ò例2:找钱问题：（Co