贪心法与动态规划(1)-课件【PPT讲稿】.ppt

第8章贪心法与动态规划(1) 石志国大纲◎贪心法的基本概念,以及使用贪心法解决问题:哈夫曼编码、单源最短路径、最小生成树、背包问题◎动态规划的基本概念,以及使用动态规划解决问题:多源最短路径、背包问题、图像压缩和最长公共子序列问题。 贪心法贪心法是求解关于独立系统组合优化问题的一种简单方法。介绍贪心法的基本思想的前提下,重点介绍利用贪心法的思想如何解决一些实际问题?如哈夫曼编码、单源最短路径、最小生成树、背包问题。 问题提出假设有 4种硬币,它们的面值分别是二角五分、一角、五分和一分。现在有一个小孩买了价值四角的东西,并给售货员一元钱。当售货员找给小孩零钱时,希望她找给小孩的硬币数目最少。为使找回的零钱的硬币数目最少,一个很自然的方法是: ?首先选出 1个面值不超过六角的最大硬币,即二角五分,然后从六角减去二角五分,剩下三角五分。?再选出一个面值不超过三角五分的最大硬币,即二角五分,然后再从三角五分减去二角五分,剩下一角?此时,再选一个一角的硬币即可。?这种简单地从具有最大面值的币种开始,按递减的顺序考虑各种币种的方法称为贪心法(Greedy Method) ,或称为启发式搜索法。 问题提出对于诸如找零钱的类似问题可以描述为: ?它有 n个输入,而它的解由这 n个输入的某个子集组成,只有当某个子集满足某些事先给定的条件(称为约束条件)时才称此子集为该问题的一个可行解。?显然,满足约束条件的子集可能有多个。因此,一般来讲,可行解也存在多个。?为了衡量不同可行解的优劣,事先需要给出一定的判断标准。这些标准一般以目标函数的形式出现,只有保证目标函数能获取到极值的可行解才称为最优解。由于贪心法的精神是“今朝有酒今朝醉”。因此,每一步面临选择时, 贪心法都作对眼前来讲是最有利的选择, 不考虑该选择对将来是否有不良影响。换言之, 贪心法并不从整体的角度来考虑它做出的选择是否最优,该选择只是在某种意义上的局部最优就行。即贪心法只希望得到较为满意的解一种方法,而不是一种追求最优解的方法。实践表明,贪心法一般可以快速得到满意的解,因为它省去了为寻找最优解需要穷尽所有可能的操作。另外,贪心法对许多问题也能产生整体最优解?如对单源最短路经、最小生成树等问题的求解。在有些情况下,即使贪心法得不到整体最优解,但其最终结果也可能是最优解的近似解。 贪心法概述(1)贪心法的基本思想?贪心法的基本思路是从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快地方法求得更好的解。即当达到算法中的某一步不能再继续前进时,算法停止,得到问题的一个解。显然,该算法有如下特点: ?①不能保证求得的最终解是最佳的; ?②不能用来求最大或最小等有极值要求的问题的解; ?③只能求得满足某些约束条件的可行解。(2)贪心法的使用条件利用贪心法求解的问题应具备如下 2个特征: ①贪心选择性质?一个问题的整体最优解可通过一系列局部的最优解的选择达到,并且每次的选择可以依赖以前做出的选择,但不依赖于后面要做出的选择。这就是贪心选择性质。?对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。②最优子结构性质?当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。?在实际应用中,至于什么问题具有什么样的贪心选择性质是不确定的,需要具体问题具体分析。(3)解决问题的步骤利用贪心法求解问题的过程通常包含如下 3个步骤: ?①分解?将原问题分解为若干个相互独立的阶段。?②解决?对于每个阶段求局部的最优解,即进行贪心选择。在每个阶段,选择一旦做出就不可再更改。做出贪心选择的依据称为贪心准则( Greedy Criterion )。?贪心准则的制定是用贪心法解决最优化问题的关键,它关系到问题能否得到成功解决及解决质量的高低。?③合并?将各个阶段的解合并为原问题的一个可行解。贪心法的设计模式 Greedy (A , n){ ? A[0:n-1] 包含 n个输入; ?将解向量 solution 初始化为空; ? for(i =0; i<n; i++){ ? x = select (A) ; //从问题的某一初始解出发; ? if (x 可以包含在 solutioin ) ? solution = union ( solution,x ); //部分解空间进行合并?} ? return ( 解向量 solution ) } 贪心法应用举例 哈夫曼编码?哈夫曼编码是一种被广泛地应用于数据文件和图像压缩的编码方式,其压缩率通常在 20% ~ 90% 之间。