贪心法与动态规划精品文稿.ppt

《贪心法与动态规划精品文稿.ppt》由会员分享，可在线阅读，更多相关《贪心法与动态规划精品文稿.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、贪心法与动态规划第1页，本讲稿共22页大纲大纲 贪心法的基本概念，以及使用贪心法解决贪心法的基本概念，以及使用贪心法解决问题问题：哈夫曼编码哈夫曼编码、单源最短路径、最小生、单源最短路径、最小生成树、成树、背包问题背包问题 动态规划的基本概念，以及使用动态规划动态规划的基本概念，以及使用动态规划解决问题：多源最短路径、背包问题、图像解决问题：多源最短路径、背包问题、图像压缩和最长公共子序列问题。压缩和最长公共子序列问题。第2页，本讲稿共22页8.1 贪心法贪心法贪心法是求解关于独立系统组合优化问题的贪心法是求解关于独立系统组合优化问题的一种简单方法。一种简单方法。介绍贪心法的基本思想的前提下，

2、重点介绍介绍贪心法的基本思想的前提下，重点介绍利用贪心法的思想如何解决一些实际问题利用贪心法的思想如何解决一些实际问题n如如哈夫曼编码哈夫曼编码、单源最短路径、最小生成树、单源最短路径、最小生成树、背背包问题包问题。第3页，本讲稿共22页8.1.1 问题提出问题提出假设有假设有4种硬币，它们的面值分别是种硬币，它们的面值分别是二角五分、一角、五分和一二角五分、一角、五分和一分分。现在有一个小孩买了价值四角的东西，并给售货员一元钱。当售现在有一个小孩买了价值四角的东西，并给售货员一元钱。当售货员找给小孩零钱时，希望她找给小孩的硬币数目最少。货员找给小孩零钱时，希望她找给小孩的硬币数目最少。为使找

3、回的零钱的硬币数目最少，一个很自然的方法是：为使找回的零钱的硬币数目最少，一个很自然的方法是：n首先选出首先选出1个面值不超过六角的最大硬币，即二角五分，然后从六角减去二角五个面值不超过六角的最大硬币，即二角五分，然后从六角减去二角五分，剩下三角五分。分，剩下三角五分。n再选出一个面值不超过三角五分的最大硬币，即二角五分，然后再从三角五分减去二再选出一个面值不超过三角五分的最大硬币，即二角五分，然后再从三角五分减去二角五分，剩下一角角五分，剩下一角n此时，再选一个一角的硬币即可。此时，再选一个一角的硬币即可。n这种简单地从具有最大面值的币种开始，按递减的顺序考虑各种币种的方这种简单地从具有最大

4、面值的币种开始，按递减的顺序考虑各种币种的方法称为法称为贪心法贪心法(Greedy Method)，或称为，或称为启发式搜索法启发式搜索法。第4页，本讲稿共22页8.1.1 问题提出问题提出对于诸如找零钱的类似问题可以描述为：对于诸如找零钱的类似问题可以描述为：n它有它有n个输入，而它的解由这个输入，而它的解由这n个输入的某个子集组成，只有当某个子集满足某些事先给定的条件个输入的某个子集组成，只有当某个子集满足某些事先给定的条件（称为约束条件）时才称此子集为该问题的一个可行解。（称为约束条件）时才称此子集为该问题的一个可行解。n显然，满足约束条件的子集可能有多个。因此，一般来讲，可行解也存在多

5、个。显然，满足约束条件的子集可能有多个。因此，一般来讲，可行解也存在多个。n为了衡量不同可行解的优劣，事先需要给出一定的判断标准。这些标准一般以目标函数的形为了衡量不同可行解的优劣，事先需要给出一定的判断标准。这些标准一般以目标函数的形式出现，只有保证目标函数能获取到极值的可行解才称为最优解。式出现，只有保证目标函数能获取到极值的可行解才称为最优解。由于贪心法的精神是由于贪心法的精神是“今朝有酒今朝醉今朝有酒今朝醉”。因此，每一步面临选择时。因此，每一步面临选择时,贪心法都作对贪心法都作对眼前来讲是最有利的选择眼前来讲是最有利的选择,不考虑该选择对将来是否有不良影响。不考虑该选择对将来是否有不

6、良影响。换言之，换言之，贪心法并不从整体的角度来考虑它做出的选择是否最优，该选择只是在某种意义贪心法并不从整体的角度来考虑它做出的选择是否最优，该选择只是在某种意义上的局部最优就行。即贪心法只希望得到较为满意的解一种方法，而不是一种追求最优解上的局部最优就行。即贪心法只希望得到较为满意的解一种方法，而不是一种追求最优解的方法。的方法。实践表明，贪心法一般可以快速得到满意的解，因为它省去了为寻找最优解需要穷尽所有实践表明，贪心法一般可以快速得到满意的解，因为它省去了为寻找最优解需要穷尽所有可能的操作。另外，贪心法对许多问题也能产生整体最优解可能的操作。另外，贪心法对许多问题也能产生整体最优解n如

7、对单源最短路经、最小生成树等问题的求解。在有些情况下，即使贪心法得不到整体最优如对单源最短路经、最小生成树等问题的求解。在有些情况下，即使贪心法得不到整体最优解，但其最终结果也可能是最优解的近似解。解，但其最终结果也可能是最优解的近似解。第5页，本讲稿共22页8.1.2 贪心法概述贪心法概述（1）贪心法的基本思想）贪心法的基本思想n贪心法的基本思路是从问题的某一个初始解出发逐步逼近给定贪心法的基本思路是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地方法求得更好的解。即当达到算法中的的目标，以尽可能快地方法求得更好的解。即当达到算法中的某一步不能再继续前进时，算法停止，得到问题的一个解

8、。某一步不能再继续前进时，算法停止，得到问题的一个解。显然，该算法有如下特点：显然，该算法有如下特点：n 不能保证求得的最终解是最佳的；不能保证求得的最终解是最佳的；n 不能用来求最大或最小等有极值要求的问题的解；不能用来求最大或最小等有极值要求的问题的解；n 只能求得满足某些约束条件的可行解只能求得满足某些约束条件的可行解。第6页，本讲稿共22页（2）贪心法的使用条件）贪心法的使用条件利用贪心法求解的问题应具备如下利用贪心法求解的问题应具备如下2个特征：个特征：贪心选择性质贪心选择性质n一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选一个问题的整体最优解可通过一系列局部的

9、最优解的选择达到，并且每次的选择可以依赖以前做出的选择，但不依赖于后面要做出的选择。这就是贪心选择择可以依赖以前做出的选择，但不依赖于后面要做出的选择。这就是贪心选择性质。性质。n对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。贪心选择最终导致问题的整体最优解。最优子结构性质最优子结构性质n当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关

10、键所在。问题的最优子结构性质是该问题可用贪心法求解的关键所在。n在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析。体问题具体分析。第7页，本讲稿共22页（3）解决问题的步骤）解决问题的步骤利用贪心法求解问题的过程通常包含如下利用贪心法求解问题的过程通常包含如下3个步骤：个步骤：n 分解分解n将原问题分解为若干个相互独立的阶段。将原问题分解为若干个相互独立的阶段。n 解决解决n对于每个阶段求局部的最优解，即进行贪心选择。在每个阶段，选择对于每个阶段求局部的最优解，即进行贪心选择。在每个阶段，选择

11、一旦做出就不可再更改。做出贪心选择的依据称为一旦做出就不可再更改。做出贪心选择的依据称为贪心准则贪心准则（Greedy Criterion）。n贪心准则的制定是贪心准则的制定是用贪心法解决最优化问题的关键用贪心法解决最优化问题的关键，它关系到问题能，它关系到问题能否得到成功解决及解决质量的高低。否得到成功解决及解决质量的高低。n 合并合并n将各个阶段的解合并为原问题的一个可行解。将各个阶段的解合并为原问题的一个可行解。第8页，本讲稿共22页贪心法的设计模式贪心法的设计模式 Greedy(A，n)nA0:n-1包含包含n个输入；个输入；n将解向量将解向量solution 初始化为空初始化为空;n

12、 for(i=0;in;i+)n x=select(A)；/从问题的某一初始解出发；从问题的某一初始解出发；n if(x 可以包含在可以包含在solutioin)n solution=union(solution,x)；/部分解空间进行部分解空间进行合并合并nn return(解向量解向量solution)第9页，本讲稿共22页8.2 贪心法应用举例贪心法应用举例8.2.1 哈夫曼编码哈夫曼编码n哈夫曼编码是一种被广泛地应用于数据文件和哈夫曼编码是一种被广泛地应用于数据文件和图像压缩的编码方式，其压缩率通常在图像压缩的编码方式，其压缩率通常在20%90%之间。之间。第10页，本讲稿共22页哈夫

13、曼编码哈夫曼编码1.问题描述问题描述n在进行远距离通信时，通常需要将要传送的文字转换为由二进制在进行远距离通信时，通常需要将要传送的文字转换为由二进制字符组成的字符串，并使要传送的电文的总长度尽可能地短。字符组成的字符串，并使要传送的电文的总长度尽可能地短。n显然，只要将电文中出现次数较多的字符采用尽可能短的编显然，只要将电文中出现次数较多的字符采用尽可能短的编码，就可以减少要传送的电文的总长度。码，就可以减少要传送的电文的总长度。n为实现此目标，需要设计一种非等长的编码，且必须保证在所为实现此目标，需要设计一种非等长的编码，且必须保证在所有字符的编码中，任何一个字符都不是另一个字符的前缀，这

14、有字符的编码中，任何一个字符都不是另一个字符的前缀，这种编码称为前缀编码。种编码称为前缀编码。第11页，本讲稿共22页回顾：哈夫曼回顾：哈夫曼编码编码第12页，本讲稿共22页回顾：哈夫曼回顾：哈夫曼编码编码第13页，本讲稿共22页回顾：哈夫曼树回顾：哈夫曼树第14页，本讲稿共22页哈夫曼编码哈夫曼编码由于构造上述编码的方法是由哈夫曼提出的，所以，由此产生的编码方案称由于构造上述编码的方法是由哈夫曼提出的，所以，由此产生的编码方案称为为哈夫曼编码哈夫曼编码。其核心思想是：。其核心思想是：n 每一个字符用一个每一个字符用一个0，1串作为其代码，并要求任意一个字符的代码都不是其串作为其代码，并要求任

15、意一个字符的代码都不是其它字符代码的前缀；它字符代码的前缀；n 用字符在文件中出现的频率表来建立一个用用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表串表示各字符的最优表示方式。即使出现频率高的字符获得较短的编码，出现频率较低的字符获得示方式。即使出现频率高的字符获得较短的编码，出现频率较低的字符获得较长的编码。较长的编码。n 将字符在文件中出现的频度值作为一棵二叉树的叶子结点的权值。并通过构造一将字符在文件中出现的频度值作为一棵二叉树的叶子结点的权值。并通过构造一棵哈夫曼树得到最优前缀码。棵哈夫曼树得到最优前缀码。哈夫曼树哈夫曼树(Huffman Tree)又称为最优二叉树又

16、称为最优二叉树。它是由。它是由n个带权叶子结个带权叶子结点构成的所有二叉树中，带权路径长度（带权路径长度指树中所点构成的所有二叉树中，带权路径长度（带权路径长度指树中所有叶子结点的带权路径长度之和）最小的二叉树。有叶子结点的带权路径长度之和）最小的二叉树。构造这种树的方法是由哈夫曼提出的，因此称这种树为哈夫曼树。显构造这种树的方法是由哈夫曼提出的，因此称这种树为哈夫曼树。显然，寻找哈夫曼编码的过程就是构造哈夫曼树的过程。然，寻找哈夫曼编码的过程就是构造哈夫曼树的过程。第15页，本讲稿共22页哈夫曼编码哈夫曼编码构造哈夫曼树的步骤如下：构造哈夫曼树的步骤如下：n 用给定的用给定的n个权值个权值w

17、1,w2,wn对应的对应的n个结点构成个结点构成n棵二叉树的森林棵二叉树的森林F=T1,T2,Tn，其中每一棵二叉树，其中每一棵二叉树Ti(1in)都只有一个权值为都只有一个权值为wi的根结点，其左、右子树为空。的根结点，其左、右子树为空。n 在森林在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，标记新二叉树的根中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，标记新二叉树的根结点权值为其左右子树的根结点权值之和。结点权值为其左右子树的根结点权值之和。n 从从F中删除被选中的那两棵二叉树，中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林同时把新构

18、成的二叉树加入到森林F中。中。n 重复重复、操作，操作，直到森林中只含有一棵二叉树为止，此时得到的这棵二叉树就直到森林中只含有一棵二叉树为止，此时得到的这棵二叉树就是哈夫曼树。是哈夫曼树。上述算法的核心思想是：上述算法的核心思想是：每一步操作都是将两棵二叉树合并为一棵，直到所有的每一步操作都是将两棵二叉树合并为一棵，直到所有的结点都加入到这棵树中为止。结点都加入到这棵树中为止。算法中所使用的贪心准则为：算法中所使用的贪心准则为：每次均从可用的二叉树中选出权值最小的两棵树。每次均从可用的二叉树中选出权值最小的两棵树。第16页，本讲稿共22页哈夫曼编码的编程哈夫曼编码的编程第17页，本讲稿共22页

19、哈夫曼编码的编程哈夫曼编码的编程由于哈夫曼树中没有度为由于哈夫曼树中没有度为1的结点，且具有的结点，且具有n个字符的哈夫曼树的个字符的哈夫曼树的结点总数为结点总数为2n-1个，个，因此可以使用顺序存储结构来实现哈夫曼算法。将结点信息存储在一个因此可以使用顺序存储结构来实现哈夫曼算法。将结点信息存储在一个2n-1的一维数组中。的一维数组中。当构造完哈夫曼树后，求每一个字符的编码的过程就是走一条从叶子结点当构造完哈夫曼树后，求每一个字符的编码的过程就是走一条从叶子结点到根结点的路径。译码的过程需要走一条从根结点到叶子结点的路径。到根结点的路径。译码的过程需要走一条从根结点到叶子结点的路径。因此，哈

20、夫曼树中的结点结构中应该包含其孩子结点和父结点因此，哈夫曼树中的结点结构中应该包含其孩子结点和父结点的信息。的信息。第18页，本讲稿共22页8.2.4 背包问题背包问题1.问题描述问题描述n给定给定n种物品和一个背包。种物品和一个背包。n物品的重量和价值分别物品的重量和价值分别为为w1，w2，wn和和v1，v2，vn；n背包可以容纳的总重量为背包可以容纳的总重量为c。n如何选择装入背包的物品，使得装入背包中的物品如何选择装入背包的物品，使得装入背包中的物品的总价值最大？的总价值最大？第19页，本讲稿共22页2.算法实现算法实现按照贪心法的思想，解决部分背包问题的算法描述是：按照贪心法的思想，解

21、决部分背包问题的算法描述是：n 计算每种物品单位重量的价值；计算每种物品单位重量的价值；n 将尽可能多的单位重量价值最高的物品装入背包；将尽可能多的单位重量价值最高的物品装入背包；n 如果单位重量价值最高的物品全部装入背包后，背包内的物如果单位重量价值最高的物品全部装入背包后，背包内的物品总重量小于品总重量小于c，则选择单位重量价值次高的物品并尽可能多装，则选择单位重量价值次高的物品并尽可能多装入背包。入背包。n 依次进行下去，直到背包装满为止。依次进行下去，直到背包装满为止。第20页，本讲稿共22页8.2.4 背包问题背包问题物品物品 A B C D F重量重量 1 2 3 4 5价值价值 3 10 6 3 5第21页，本讲稿共22页小结小结 贪心法的基本概念，以及使用贪心法解决贪心法的基本概念，以及使用贪心法解决问题问题：哈夫曼编码哈夫曼编码、单源最短路径、最小生成、单源最短路径、最小生成树、树、背包问题背包问题 动态规划的基本概念，以及使用动态规划动态规划的基本概念，以及使用动态规划解决问题：多源最短路径、背包问题、图像压解决问题：多源最短路径、背包问题、图像压缩和最长公共子序列问题。缩和最长公共子序列问题。第22页，本讲稿共22页