第六章_贪心法.ppt

算法分析与设计算法分析与设计主讲: 徐晓蓉联系电话: ********** 邮箱: rortyrong@ 所在院系: 计算机科学与技术学院第六章第六章贪心法贪心法贪心法的学习提纲一般方法适合求解的问题基本思想(求解问题的过程 ) :找硬币 元,要求硬币数最少。找硬币方法就是一种贪心算法. (1)面值; 5分、 2分、 1分: (2)面值: 11分、 5分、 1分: 从此例可以看出: 1 ,贪心法未必总能求得问题的最优解; 2 ,,它所作出的选择只是在某种意义上的局部最优选择。虽然贪心算法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它都能产生最优解。如单源最短路径问题,最小生成树问题等。而且,在一些情况下,即使贪心算法不能得到整体最优解,但其最终结果却是最优解的很好的近似解! 3个5分 ( 最优) 1个 11 分4个1分 ( 次优) 一般方法?贪心方法适合的问题是最优化问题。最优化问题: 有n个输入,而它的解就由这 n个输入的满足某些事先给定的约束条件的某个子集组成,而把满足约束条件的子集称为该问题的可行解。显然,可行解一般来说是不唯一的,为了衡量可行解的好坏,问题还给出某个值函数,称为目标函数,使目标函数取极值(极大或极小)的可行解,称为最优解。?? 31 min i ix 目标函数: 约束条件(函数): 15 .0 31???i iixp)01 .0,02 .0,05 .0(?p,.......} 2,1,0{? ix 其中: }0,0,3{ 1?X }1,7,0{ 2?X}15 ,0,0{ 3?X 可行解: ?如找硬币问题可描述如下: 最优化问题的解可表示成一个 n元组 X= ( x1,x2 …xn ), 其中每个分量取自某个值集 S, 所有允许的 n-元组组成一个侯选解集。 一般方法?贪心方法适合的问题是最优化问题。最优化问题: 有n个输入,而它的解就由这 n个输入的满足某些事先给定的约束条件的某个子集组成,而把满足约束条件的子集称为该问题的可行解。显然,可行解一般来说是不唯一的,为了衡量可行解的好坏, 问题还给出某个值函数,称为目标函数,使目标函数取极值(极大或极小)的可行解,称为最优解。?最优化问题的解是一个 n元组?贪心法是通过分步决策的方法来解决问题的。贪心法在求解问题的每一步上作出某种决策,产生 n-元组的一个分量,贪心法要求根据题意,选定一种最优量度标准,作为选择当前分量的依据,这种在贪心法每一步上用做决策依据的选择准则被称为最优量度标准(贪心准则,也称贪心选择性质)。 一般方法?贪心法的基本思想:是依据题意选取一种量度标准,然后按照这种量度标准对这 n个输入进行排序,并按序一次输入一个量,作为 n-元组的一个分量,如果这个输入量的加入不满足约束条件,则不把此输入加入到部分解向量中. ?贪心法求解问题的过程: ?选取最优量度标准?依最优量度标准对 n个输入排序?初始状态下,解向量 solution= φ中; ?按序一次取一个输入量,作为 n-元组的一个分量,若加入该分量满足给定的约束条件,则加入,否则,不加入,继续检测下一个分量. 贪心方法的抽象化控制算法 贪心法的控制流程 SolutionType Greedy(SType a[] , int n) { SolutionType solutions= φ//将解向量 solution 初始化为空/ for(int i=0;i<n;i++) { SType x=Select(a); if (Feasiable(solution,x)) solutions=UNION(solution,x); } return solution; } 从算法 可看出,一旦能选择出某个问题的最优量度标准,那么用贪心方法求解这个问题则特别简单有效。 n个输入按某种量度标准排序……按序一次选择一个输入量。满足约束条件,加入解解不满足约束条件,扬弃….. 对于一个给定的问题,往往可能有好几种量度标准。用其中的大多数量度标准作贪心处理所得到该量度意义下的最优解并不是问题的最优解,而是次优。选择能产生问题最优解的最优量度标准是使用贪心法设计求解的核心问题。 一般方法?贪心法小结: ?适合求解的问题:解为 n-元组的最优化问题; ?贪心法是分步决策,每一步决策产生 n-元组的一个分量?贪心法并不是从整体上考虑最佳,而是做