第九章 贪心法

1、 逐步给出解的各部分，逐步给出解的各部分， 在每一步在每一步“贪婪地贪婪地” 选择最好的部分解，选择最好的部分解，但不顾及这样选择对整体的影响，但不顾及这样选择对整体的影响， 因此一般地得到的不是最好的解。因此一般地得到的不是最好的解。 但对许多问题它能产生整体最优解。但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解，其最终结果却是最优解的很好近最优解的很好近似似。 9.1 Prim算法算法 9.2 贪心法的特点贪心法的特点 9.3

2、 kruskal算法算法 9.4 Dijkstra算法算法 9.5哈夫曼树哈夫曼树设设G =(V,E)G =(V,E)是无向连通带权图。是无向连通带权图。E E中每条边中每条边(v,w)(v,w)的权重为的权重为cvwcvw。如果如果G G的的子图子图GG是一棵是一棵包含包含G G的所有顶点的所有顶点的树，则的树，则称称GG为为G G的生成树。的生成树。在在G G的所有生成树中，的所有生成树中，所有边的权重总和所有边的权重总和最小的生最小的生成树称为成树称为G G的的最小生成树最小生成树。 图的最小生成树在实际中有广泛应用。图的最小生成树在实际中有广泛应用。 例如，在设计通信网络时，用图的顶点

3、表示城市，在设计通信网络时，用图的顶点表示城市，用边用边(v,w)(v,w)的权的权cvwcvw表示建立城市表示建立城市v v和城市和城市w w之之间的通信线路所需的费用，则最小生成树就给出间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。了建立通信网络的最经济的方案。设设G=(V,E)G=(V,E)是连通带权图，是连通带权图，V=1,2,nV=1,2,n。首先置首先置S=1S=1然后，只要然后，只要S S是是V V的真子集，就作如下的的真子集，就作如下的贪心选择：贪心选择：选取满足条件选取满足条件i i S S，j j V-SV-S，且，且cijcij最小的边最小的边将

4、顶点将顶点j j添加到添加到S S中。中。这个过程一直进行到这个过程一直进行到S=VS=V时为止。时为止。在这个过程中选取到的所有边恰好构成在这个过程中选取到的所有边恰好构成G G的一棵的一棵最最小生成树。小生成树。 如何有效地找出满足如何有效地找出满足条件条件i S,j V-S，且，且权权cij最小的边最小的边(i,j) 对每个不在当前树中的顶点，附加两个标记：对每个不在当前树中的顶点，附加两个标记： (树中最近顶点的名称，相应边的权重树中最近顶点的名称，相应边的权重) 求出距离标记最小的点求出距离标记最小的点 当确定了一个加入树中的顶点当确定了一个加入树中的顶点u*后后 把把u*从集合从集

5、合V-S移到树的顶点集合移到树的顶点集合S 更新更新V-S中各顶点的标记中各顶点的标记 用数学归纳法证明：用数学归纳法证明： 用用Ti i=1，,n表示表示Prim算法过程中生成的每算法过程中生成的每一棵子树一棵子树 T1，显然是最小生成树的一部分，显然是最小生成树的一部分 设设Tk-1 是最小生成树是最小生成树T的一部分的一部分 证明通过证明通过Prim算法从算法从Tk-1 生成的生成的Tk也是一棵最小也是一棵最小生成树的一部分生成树的一部分 反证法：反证法： 设没有一棵最小生成树包含设没有一棵最小生成树包含Tk ，用，用T表示最小生表示最小生成树成树 则有则有ek=(v,u)权重最小，权重

6、最小，v属于属于Tk-1 ，u不属于不属于Tk-1 使使Tk-1扩展到扩展到Tk 因为因为ek不属于不属于T 如果把如果把ek加入加入T中，会形成回路。中，会形成回路。(为什么？为什么？) 该回路必定包含另一边该回路必定包含另一边(x,y), x属于属于Tk-1 ，y不属不属于于Tk-1 。（为什么？）。（为什么？） 如果删除该边得到另一棵生成树，权重小于等如果删除该边得到另一棵生成树，权重小于等于于T。（为什么？）。（为什么？） 和假设矛盾。和假设矛盾。 取决于表示图的数据结构取决于表示图的数据结构 以及表示以及表示V-S的优先队列的数据结构的优先队列的数据结构 可用的数据结构：可用的数据结

7、构： 图图-权重矩阵；优先队列权重矩阵；优先队列无序数组无序数组 运行时间属于运行时间属于(|V|2) 图图邻接链表；优先队列邻接链表；优先队列最小堆最小堆 运行时间运行时间O(|E|log|V|) 逐步给出解的各部分，逐步给出解的各部分， 在每一步在每一步“贪婪地贪婪地” 选择最好的部分解选择最好的部分解 最优子结构性质当一个问题的最优解包含其子问题的最优解时，当一个问题的最优解包含其子问题的最优解时，称此问题具有称此问题具有最优子结构性质最优子结构性质。问题的最优子结。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求构性质是该问题可用动态规划算法或贪心算法求解的关键特征。解的关键特

8、征。 贪心算法与动态规划算法的差异贪心算法与动态规划算法的差异但是，对于具有但是，对于具有最优子结构最优子结构的问题应该选用贪心的问题应该选用贪心算法还是动态规划算法求解算法还是动态规划算法求解? ?是否能用动态规划算法求解的问题也能用贪心算是否能用动态规划算法求解的问题也能用贪心算法求解法求解? ?动态规划算法通常以动态规划算法通常以自底向上自底向上的方式解各子问题的方式解各子问题而贪心算法则通常以而贪心算法则通常以自顶向下自顶向下的方式进行的方式进行以迭代的方式作出相继的贪心选择，每作一次贪以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。心选择就将所求问

9、题简化为规模更小的子问题。下面研究下面研究2 2个经典的个经典的组合优化问题组合优化问题，并以此说明贪，并以此说明贪心算法与动态规划算法的主要差别。心算法与动态规划算法的主要差别。 0-1背包问题： 给定给定n n种物品和一个背包。物品种物品和一个背包。物品i i的重量是的重量是WiWi，其价值为其价值为ViVi，背包的容量为，背包的容量为C C。应如何选择装入。应如何选择装入背包的物品，使得装入背包中物品的总价值最大背包的物品，使得装入背包中物品的总价值最大? ?背包问题： 与与0-10-1背包问题类似，所不同的是在选择物品背包问题类似，所不同的是在选择物品i i装入背包时，装入背包时，可以

10、选择物品可以选择物品i i的一部分，的一部分，而不一而不一定要全部装入背包，定要全部装入背包，1in1in。 在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i i只有只有2 2种种选择，即装入背包或不装入背包。不能将物品选择，即装入背包或不装入背包。不能将物品i i装入装入背包多次，也不能只装入部分的物品背包多次，也不能只装入部分的物品i i。这这2类问题都具有类问题都具有最优子结构最优子结构性质，极为相似，但性质，极为相似，但背包问题可以用贪心算法求解，而背包问题可以用贪心算法求解，而0-1背包问题背包问题却不能用贪心算法求解。却不能用贪心算法求解。 贪心法要求每次在构

11、造部分解的时候都挑一个贪心法要求每次在构造部分解的时候都挑一个最好的部分解。最好的部分解。 背包问题中什么是最好的部分解背包问题中什么是最好的部分解 单位价值单位价值最大的物品即为最好的部分解最大的物品即为最好的部分解 因此在背包问题中因此在背包问题中每次都挑当前单位价值最大的每次都挑当前单位价值最大的物品，并尽可能多的放入包中物品，并尽可能多的放入包中。 n=3 w=10,20,30 v=60,100,120 c=50 单位价值单位价值V/w=6,5,4 因此第一次挑一号物品，全部装入因此第一次挑一号物品，全部装入r=40,pv=60 第二次挑第二次挑2号，全部装入号，全部装入r=20,pv

12、=160 第三次挑第三次挑3号，部分装入号，部分装入r=20,pv=160+80=240 对于对于0-10-1背包问题背包问题，贪心选择不一定得到，贪心选择不一定得到最优解。最优解。 如：如：n=3 w=10,20,30 v=60,100,120 c=30按贪心法：选择最有价值的放入按贪心法：选择最有价值的放入 全部放入第全部放入第3个物品，价值个物品，价值120，但这并不是最好的，但这并不是最好的1，2 物品的放入，总价值物品的放入，总价值160因为物品要么选，要么不选，尽管每次选最有价值的物品，因为物品要么选，要么不选，尽管每次选最有价值的物品，却无法保证背包单位重量的价值最高，所以总重量

13、价值却无法保证背包单位重量的价值最高，所以总重量价值最高。最高。事实上，在考虑事实上，在考虑0-10-1背包问题时，应比较选择该物品和不背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多由此就导出许多互相重叠的子问题互相重叠的子问题。这正是该问题可用。这正是该问题可用动动态规划算法态规划算法求解的另一重要特征。求解的另一重要特征。实际上也是如此，动态规划算法的确可以有效地解实际上也是如此，动态规划算法的确可以有效地解0-10-1背包问题。背包问题。 贪心算法以贪心算法以自顶向下自顶向下的方式进行，以迭代

14、的方式的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。求问题简化为规模更小的子问题。 如：如：0-10-1背包问题背包问题 max(i,j)max(i,j)表示在表示在i i个物品中挑个物品中挑选物品放入容量为选物品放入容量为j j的背包的最大物品价值。假的背包的最大物品价值。假设有设有n n个物品个物品 max(n,j)-maxValue(n)+ max(n-1,k)- max(n,j)-maxValue(n)+ max(n-1,k)- maxValue(n)+ maxValue(n-1)+ max(n

15、-2,q)maxValue(n)+ maxValue(n-1)+ max(n-2,q) n=3 w=30,20,10 v=120, 100,60 c=50 动态规划解动态规划解0-1背包：背包：m(i，j)是背包容量为是背包容量为j，可，可选择物品为选择物品为1, 2,i时的最优值时的最优值 注意：分析是从顶向下分析，但写程序时是从底注意：分析是从顶向下分析，但写程序时是从底向上进行。向上进行。m(3,50)m(2,50)m(2,40)+60m(1,50)m(1,30)+100m(1,40)+60m(1,20)+60+100给图的所有结点着色，限制为给图的所有结点着色，限制为一条边的两个端点不

16、能用同样一条边的两个端点不能用同样的颜色，的颜色，要求所使用的不同颜色的数目要求所使用的不同颜色的数目最小。最小。12345 有有5个结点的图。将结点任意编号为个结点的图。将结点任意编号为1至至5然然后按编号给结点着色，后按编号给结点着色， 从贪婪法观点考虑，每次给尽可能多的结点着从贪婪法观点考虑，每次给尽可能多的结点着色。色。 首先用颜色首先用颜色1，可给节点，可给节点1和和2着色。着色。 现在必须更换颜色，颜色现在必须更换颜色，颜色2可给结点可给结点3和和4着色。着色。 这时又不得不换颜色，颜色这时又不得不换颜色，颜色3给结点给结点5着色。着色。 但很显然，更好的办法只要两种颜色，一种给但

17、很显然，更好的办法只要两种颜色，一种给结点结点1、3、4着色，另一种给结点着色，另一种给结点2、5着色。着色。 (1)明确目标函数和约束条件明确目标函数和约束条件 (2)制定部分解结构。制定部分解结构。 确定如何将待解问题分解成若干步骤确定如何将待解问题分解成若干步骤 Prim算法：最小生成树的子树算法：最小生成树的子树 背包问题：一部分一部分装入背包问题：一部分一部分装入 (3)确定贪心策略确定贪心策略 扩大部分解的方法，一般涉及极值选择扩大部分解的方法，一般涉及极值选择 (4)确定候选集确定候选集 明确贪心的选择范围明确贪心的选择范围 (5)调整候选集调整候选集 (6)正确性证明正确性证明

18、 (1)明确目标函数和约束条件明确目标函数和约束条件 求最小生成树求最小生成树 (2)制定部分解结构。制定部分解结构。 确定如何将待解问题分解成若干步骤确定如何将待解问题分解成若干步骤 该树由一个一个的边所组成，该树由一个一个的边所组成， 考虑依次选边考虑依次选边 (3)确定贪心策略确定贪心策略 扩大部分解的方法，一般涉及极值选择扩大部分解的方法，一般涉及极值选择 选择一条最短的选择一条最短的且将之加入到部分解且将之加入到部分解不形成回路不形成回路的边。的边。 (4)确定候选集确定候选集 明确贪心的选择范围明确贪心的选择范围 剩下的边剩下的边 (5)调整候选集调整候选集 (6)正确性证明正确性

19、证明 把边按照长短排序把边按照长短排序1342610530204 看上去似乎很简单看上去似乎很简单 但每次迭代时，必须要检查新边加入后是否会形但每次迭代时，必须要检查新边加入后是否会形成回路成回路 换一个解释换一个解释(从森林的角度从森林的角度)： 初始时，有初始时，有|V|个树构成的森林个树构成的森林 最终的森林由单独的树构成最终的森林由单独的树构成 每次迭代中新边的加入等价于从图中找到一条边每次迭代中新边的加入等价于从图中找到一条边,当顶点分别属于不同的树时当顶点分别属于不同的树时，选取该边，使两棵，选取该边，使两棵树变为一棵更大的树。树变为一棵更大的树。 通过通过union-find(并

20、查并查)算法实现，对两个顶点是算法实现，对两个顶点是否属于同棵树否属于同棵树(集合集合)的考察的考察 许多应用要求把一个许多应用要求把一个n个元素集合个元素集合S动态划分为动态划分为一系列不相交的子集。一系列不相交的子集。 对不相交子集求并集和查找的混合操作对不相交子集求并集和查找的混合操作 用用makeset(x):生成一个单元素集合生成一个单元素集合x。设该操。设该操作对集合作对集合S的每个元素只能应用一次。的每个元素只能应用一次。 Find(x)：返回一个包含：返回一个包含x的子集的子集 Union(x,y)：构造分别包含：构造分别包含x和和y的不相交子集的的不相交子集的并集并把它添加到

21、子集的集合中，取代原来的两并集并把它添加到子集的集合中，取代原来的两个子集。个子集。 两个数据结构：两个数据结构： 使用一个数组，用数组的下标表示使用一个数组，用数组的下标表示S中的元素，数组中中的元素，数组中的值指出包含这些元素的的值指出包含这些元素的子集代表子集代表。 每一个子集用链表表示，表头包含指向表头和表尾元素每一个子集用链表表示，表头包含指向表头和表尾元素的指针和大小以及表中的元素个数的指针和大小以及表中的元素个数 对于初始集合对于初始集合S=1,2,3,4,5,6下标下标 123456值值 初始集合初始集合S=1,2,3,4,5,6 通过通过6次次makeset(i)产生产生6个

22、单元素子集个单元素子集 1, 2,3, 4, 5, 6 对于上述数据结构的操作对于上述数据结构的操作 把数组中的值设为相应子集的代表元素把数组中的值设为相应子集的代表元素 链表为链表为6个单节点链表个单节点链表 List1 Makeset(i)的时间效率是多少？的时间效率是多少？下标下标 123456值值12345611null 假设执行假设执行union(1,4)下标下标123456值值12345611null14null下标下标123456值值12315621null40nullnull一次一次union操作的时间操作的时间效率效率 N次次union的时间效率？的时间效率？ 一系列按大小求

23、并的操作，可证明最差效率是一系列按大小求并的操作，可证明最差效率是 O(nlogn) 用树表示每个子集用树表示每个子集 根元素作为子集代表根元素作为子集代表 树中的边从子女指向他们的父母树中的边从子女指向他们的父母 维护一个从集合元素到树中节点的映射维护一个从集合元素到树中节点的映射 如对于如对于S1=1,4,5,2 S2=3,6 union(5,6)145236145236 Makeset(x)的时间效率的时间效率(1) Union(x,y)的时间效率是的时间效率是(1) Find(x)从包含从包含x的节点开始找到根，考虑最差情的节点开始找到根，考虑最差情况，退化为一个况，退化为一个n节点的

24、链表节点的链表O(n) 运行时间：运行时间： 若采用高效的并查算法若采用高效的并查算法 则则kruskal算法的运行时间取决于对图中边的权算法的运行时间取决于对图中边的权重排序的时间重排序的时间 O(|E|log|E|)给定带权有向图给定带权有向图G =(V,E)G =(V,E)，其中每条边的权，其中每条边的权是非负实数。是非负实数。给定给定V V中的一个顶点，称为中的一个顶点，称为源源。计算从源到所有其他各顶点的计算从源到所有其他各顶点的最短路径长度最短路径长度。这里路径的长度是指路径上各边权之和。这里路径的长度是指路径上各边权之和。这个问题通常称为这个问题通常称为单源最短路径问题单源最短路

25、径问题。1.1.算法基本思想算法基本思想DijkstraDijkstra算法是解单源最短路径问题的贪心算法。算法是解单源最短路径问题的贪心算法。对右图中的有向图，对右图中的有向图，如何考虑用贪心法获如何考虑用贪心法获得从源顶点得从源顶点1 1到其他顶到其他顶点间最短路径点间最短路径设置顶点集合设置顶点集合S S并不断地作并不断地作贪心选择贪心选择来扩充这个集合。来扩充这个集合。一个顶点属于集合一个顶点属于集合S S当且仅当从源到该顶点的最短路径长当且仅当从源到该顶点的最短路径长度已知。度已知。初始时，初始时，S S中仅含有源。中仅含有源。设设u u是是G G的某一个顶点，把从源到的某一个顶点，

26、把从源到u u且中间只经过且中间只经过S S中顶点的中顶点的路称为从源到路称为从源到u u的特殊路径，并用数组的特殊路径，并用数组distdist记录当前每记录当前每个顶点所对应的最短特殊路径长度。个顶点所对应的最短特殊路径长度。DijkstraDijkstra算法每次从算法每次从V-SV-S中取出具有最短特殊路长度的顶中取出具有最短特殊路长度的顶点点u u，将，将u u添加到添加到S S中，同时对数组中，同时对数组distdist作必要的修改。作必要的修改。一旦一旦S S包含了所有包含了所有V V中顶点，中顶点，distdist就记录了从源到所有其就记录了从源到所有其他顶点之间的最短路径长度

27、。他顶点之间的最短路径长度。迭代Sudist2 dist3 dist4 dist5初始11- -1010maxintmaxint303010010011,21,22 210106060303010010021,2,41,2,44 4101050503030909031,2,4,31,2,4,33 3101050503030606041,2,4,3,51,2,4,3,55 51010505030306060Dijkstra算法的迭代过程： 编码：文本中的字符赋予一串比特位编码：文本中的字符赋予一串比特位 定长编码定长编码 变长编码：较短的比特串给常用字符变长编码：较短的比特串给常用字符 较长比特

28、串给不常用字符较长比特串给不常用字符 前缀码：所有的比特串都不是另一个字符比特串前缀码：所有的比特串都不是另一个字符比特串的前缀的前缀 考虑将字符和二叉树的叶子联系起来形成前缀码考虑将字符和二叉树的叶子联系起来形成前缀码哈夫曼编码哈夫曼编码是广泛地用于是广泛地用于数据文件压缩数据文件压缩的十分有效的编的十分有效的编码方法。其压缩率通常在码方法。其压缩率通常在20%20%90%90%之间之间 哈夫曼编码算法用字符在文件中出现的哈夫曼编码算法用字符在文件中出现的频率频率表来建立一表来建立一个用个用0 0，1 1串表示各字符的最优表示方式。串表示各字符的最优表示方式。自己考虑用贪心法如何以二叉树的组

29、织形式，自己考虑用贪心法如何以二叉树的组织形式，关键字位于叶子节点，且关键字具有出现频率关键字位于叶子节点，且关键字具有出现频率使对这些关键字编码后的平均长度最小使对这些关键字编码后的平均长度最小 编码过程：编码过程： 初始化初始化n个字符单节点的树，每个字符具有概率，个字符单节点的树，每个字符具有概率，记为权重记为权重 重复下面的步骤直到剩下一棵单独的树。重复下面的步骤直到剩下一棵单独的树。 找到两个树权重最小，把他们作为新树中的左右找到两个树权重最小，把他们作为新树中的左右子树。并把其权重之和作为新的权重记录在新树子树。并把其权重之和作为新的权重记录在新树的根中。的根中。 如如a 0.35 b 0.1 c 0.2 d 0.2 _ 0.15 建树后平均字长是多少？建树后平均字长是多少？ 压缩率压缩率 如何获得字符频率？如何获得字符频率？ 扫描给定的文本统计每个字符的出现次数扫描给定的文本统计每个字符的出现次数 逐步给出解的各部分，逐步给出解的各部分， 在每一步在每一步“贪婪地贪婪地” 选