贪心法与动态规划

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

第8页，课件共22页，创作于2023年2月贪心法的设计模式

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)}第9页，课件共22页，创作于2023年2月8.2贪心法应用举例8.2.1哈夫曼编码哈夫曼编码是一种被广泛地应用于数据文件和图像压缩的编码方式，其压缩率通常在20%～90%之间。第10页，课件共22页，创作于2023年2月哈夫曼编码1.问题描述在进行远距离通信时，通常需要将要传送的文字转换为由二进制字符组成的字符串，并使要传送的电文的总长度尽可能地短。显然，只要将电文中出现次数较多的字符采用尽可能短的编码，就可以减少要传送的电文的总长度。为实现此目标，需要设计一种非等长的编码，且必须保证在所有字符的编码中，任何一个字符都不是另一个字符的前缀，这种编码称为前缀编码。第11页，课件共22页，创作于2023年2月回顾：哈夫曼编码第12页，课件共22页，创作于2023年2月回顾：哈夫曼编码第13页，课件共22页，创作于2023年2月回顾：哈夫曼树第14页，课件共22页，创作于2023年2月哈夫曼编码由于构造上述编码的方法是由哈夫曼提出的，所以，由此产生的编码方案称为哈夫曼编码。其核心思想是：①每一个字符用一个0，1串作为其代码，并要求任意一个字符的代码都不是其它字符代码的前缀；②用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。即使出现频率高的字符获得较短的编码，出现频率较低的字符获得较长的编码。③将字符在文件中出现的频度值作为一棵二叉树的叶子结点的权值。并通过构造一棵哈夫曼树得到最优前缀码。哈夫曼树(HuffmanTree)又称为最优二叉树。它是由n个带权叶子结点构成的所有二叉树中，带权路径长度（带权路径长度指树中所有叶子结点的带权路径长度之和）最小的二叉树。构造这种树的方法是由哈夫曼提出的，因此称这种树为哈夫曼树。显然，寻找哈夫曼编码的过程就是构造哈夫曼树的过程。第15页，课件共22页，创作于2023年2月哈夫曼编码构造哈夫曼树的步骤如下：①用给定的n个权值{w1,w2,…,wn}对应的n个结点构成n棵二叉树的森林F={T1,T2,…,Tn}，其中每一棵二叉树Ti(1≤i≤n)都只有一个权值为wi的根结点，其左、右子树为空。②在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，标记新二叉树的根结点权值为其左右子树的根结点权值之和。③从F中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林F中。④重复②、③操作，直到森林中只含有一棵二叉树为止，此时得到的这棵二叉树就是哈夫曼树。上述算法的核心思想是：每一步操作都是将两棵二叉树合并为一棵，直到所有的结点都加入到这棵树中为止。算法中所使用的贪心准则为：每次均从可用的二叉树中选出权值最小的两棵树。第16页，课件共22页，创作于2023年2月哈夫曼编码的编程第17页，课件共22页，创作于2023年2月哈夫曼编码的编程由于哈夫曼树中没有度为1的结点，且具有n个字符的哈夫曼树的结点总数为2n-1个，因此可以使用顺序存储结构来实现哈夫曼算法。将结点信息存储在一个2n-1的一维数组中。当构造完哈夫曼树后，求每一个字符的编码的过程就是走一条从叶子结点到根结点的路径。译码的过程需要走一条从根结点到叶子结点的路径。因此，哈夫曼树中的结点结构中应该包含其孩子结点和父结点的信息。

第18页，课件共22页，创作于2023年2月8.2.4背包问题1.问题描述给定n种物品和一个背包。n物品的重量和价值分别为w1，w2，…，wn和v1，v2，…，vn；背包可以容纳的总重量为c。如何选择装入背包的物品，使得装入背包中的物品的总价值最大？第19页，课件共22页，创作于2023年2月2.算法实现按照贪心法的思想，解决部分背包问题的算法描述是：①计算每种物品单位重量的价值；②将尽可能多的单位重量价值最高的物品装入背包；③如果单位重量价值最高的物品全部装入背包后，背包内的物品总重量小于c，则选择单位重量价值次高的物品并尽可能多装入背包。④依次进行下去，直到背包装满为止。

第20页，课件共22页，创作于2023年2月8.2.4背包问题物品ABCDF重量1234