《算法设计与分析》课件 chp5贪心算法

贪心算法截至目前,我们已经学习了三种主要的算法设计策略:枚举法、分治法和动态规划。本章将介绍第四种算法设计策略——贪心算法(GreedyAlgorithm),也称为贪心策略。通过详细的案例讲解,读者将能够理解贪心策略的适用条件,并掌握如何利用贪心算法设计高效的算法来解决实际问题。基本思想:兑零钱问题问题描述给定硬币面值数组和目标金额n,每种硬币可重复使用且数量不限,求使用最少数量的硬币凑出金额n。例如:硬币面值为[1,2,5],兑换11元需要多少枚硬币?贪心策略每次选择当前可兑换的最大面额硬币。兑换11元:先选5元(剩6元),再选5元(剩1元),最后选1元。方案为{5,5,1},共3枚硬币。贪心策略的核心特征局部最优选择每次决策时仅考虑当前状态下的最优选择,不关注之前或之后的决策影响构造全局解试图通过一系列局部最优的选择构造出整体最优解直观易懂贪心算法通常直观且易于理解,只需尝试几个小规模示例即可发现求解方式旅行商问题的贪心策略旅行商问题(TSP)需要找到一条从某个城市出发、遍历所有城市且仅访问一次、最终回到起始城市的最短路径。01起始城市从起始城市开始,选择距离最近的未访问城市02迭代选择到达新城市后,在未访问的城市中再次选择距离最近的城市03完成遍历依此类推,直到遍历所有城市,最后回到起始城市TSP问题贪心解法贪心算法的求解步骤定义最优解结构明确问题目标及解的形式,确保问题适用于贪心策略构建贪心选择规则确定在当前状态下如何选择局部最优且可行的选项更新问题状态每次贪心选择后,更新当前状态以便继续应用贪心策略构建最终解不断重复贪心选择,逐步构造出最终的解背包问题:0-1背包

1定义最优解结构

2贪心选择规则

3更新状态每选择一个物品后,更新背包剩余容量W4构建解反复应用贪心选择规则,逐步构建物品选择序列0-1背包问题示例4个物品的重量和价值:重量w=[2,3,4,5]价值v=[3,4,5,6]背包容量W=8单位价值分别为:1.5,1.3,1.25,1.2按单位价值排序:物品1,2,3,4贪心算法求解选择物品1(重量2),剩余容量6选择物品2(重量3),剩余容量3物品3和4无法装入贪心解:{物品1,物品2},总价值7最优解:{物品2,物品4},总价值100-1背包的时间复杂度分析预处理阶段时间复杂度Θ(nlogn)物品选择阶段时间复杂度Θ(n)总体复杂度Θ(nlogn)+Θ(n)=Θ(nlogn)贪心算法的优点简单直观每一步都做出当前看起来最优的选择,易于理解和实现高效性通常具有较低的时间复杂度,适合处理大规模问题占用空间少不需要维护复杂的数据结构或记录大量中间状态适用于特定问题在某些情况下能够保证找到全局最优解提供近似解即使无法保证最优解,通常也能提供较为接近最优解的近似解贪心算法的缺点依赖问题特性适用性高度依赖于问题本身的结构,只有在特定类型的问题中才能有效工作局部最优导致全局次优每一步只关注局部最优选择,忽略整体影响,可能导致最终解在全局范围内并非最优局部最优与全局最优《庄子·齐物论》记载:养猴人每天早晨给猴子们发三颗栗子,傍晚发四颗。猴子们觉得早晨的栗子太少,不满意。于是,养猴人改为早晨发四颗,傍晚发三颗。猴子们立刻高兴起来。实际上,无论"朝三暮四"还是"朝四暮三",每天猴子们得到的栗子总数都是七颗,并未发生任何变化。这个故事反映了猴子们只关注眼前得失,被表面的数量变化所迷惑,忽略了整体利益并没有变化的事实。这种行为正是局部最优与全局最优之间的区别。贪心算法的必要条件贪心算法并不能保证一定找到全局最优解。只有在特定条件下,贪心算法才能确保其所得解为最优解。最优子结构性质问题的最优解包含其子问题的最优解。如果一个问题的最优解包含了某个子问题的最优解,那么整个问题就具有最优子结构性质。此性质也是动态规划的核心。贪心选择性质通过局部最优的选择,可以直接构造出全局最优解。换句话说,最优解可以通过一系列局部最优的选择逐步构建,而不需要回溯或调整之前的决策。部分背包问题部分背包问题与0-1背包问题类似,但存在关键区别:允许将物品拆分成任意比例后装入背包。问题描述

目标是找到一种装包方案,使得背包内物品的总价值最大化。贪心策略

直到背包无法容纳更多物品为止。部分背包问题示例背包最大承重W=50,有4个物品:物品编号重量价值单位价值11060622010053301204425753部分背包求解过程选择物品1单位价值6,重量10,剩余容量40,背包价值60选择物品2单位价值5,重量20,剩余容量20,背包价值160部分选择物品3单位价值4,部分装入20,剩余容量0,背包价值240最终选择:物品1、物品2和物品3的一部分,背包总价值为240。贪心选择性质的证明

因此，贪心算法的选择不会低于最优解的选择。这表明，通过每一步选择单位价值最高的物品部分，贪心算法的选择能够逐步构建出最优解，满足贪心选择性质。最优子结构性质的证明假设我们有一个最优解S选择了部分背包问题中的若干物品，其中按照单位价值从高到低的顺序依次选择。设第一个被选择的物品为物品i，其单位价值最高。

由此可见，部分背包问题满足最优子结构性质。部分背包问题的结论贪心算法保证最优解部分背包问题同时满足最优子结构性质和贪心选择性质。因此,贪心算法能够保证在该问题中找到全局最优解。0-1背包贪心算法不能保证最优解部分背包贪心算法能够保证最优解兑零钱问题的深入分析在某些硬币面额体系下,贪心算法能够保证找到最优解。例如,当硬币的面额为1元、2元和5元时,贪心算法始终能够找到兑换目标金额的最优解。反例:面额[1,3,4]目标金额:6元贪心策略:选择4元(剩2元),选择1元两次贪心解:3枚硬币最优解:两枚3元硬币,仅需2枚充分条件硬币面额满足递增倍数关系:

其中a是整数且a≥2这种情况下,使用最大面额的硬币总是最优的活动安排问题

活动安排问题示例1选择活动b结束时间最早,加入解集合2选择活动e从剩余活动中选择结束时间最早的3选择活动h继续选择,直到剩余活动集合为空最终,贪心算法求得的活动集合为{b,e,h},共3个活动。1定义最优解结构构建一个不冲突的最大活动集合2贪心选择规则选择结束时间最早的活动3更新状态更新当前时间,筛选剩余活动4构建最终解重复直到没有符合条件的活动活动安排的贪心策略对比选择结束时间最早的活动贪心算法得到:{b,e,h}活动数量:3个(最优)选择开始时间最早的活动贪心算法得到:{a,g}活动数量:2个(非最优)选择占用时间最少的活动贪心算法得到:{c,h}活动数量:2个(非最优)活动安排算法的时间复杂度O(nlogn)排序阶段对所有活动按照结束时间进行排序O(n)遍历阶段对活动进行遍历,需要执行n-1次循环O(nlogn)总体复杂度最小生成树问题一家电力公司计划在某个地区建立新的输电网络,以连接若干个城市和乡镇,确保电力能够输送到每个地方。由于建设输电线路的成本非常高,公司希望总的建设成本尽可能低。问题建模将此问题建模为一个带权无向图。图的顶点代表城市和乡镇,顶点之间的边代表可能建设的输电线路,边的权重代表建设成本。最优方案最优的输电线路是连接所有顶点的边集合,并且这些边的总权重(即总建设成本)最小。这对应一棵生成树。最小生成树的定义在一个带权连通无向图G=(V,E)中,V表示顶点集合,E表示边集合,每条边都赋予了一个权重(或称成本)。生成树包含图G中的所有顶点的无环的连通子图,即任意两个顶点之间只有唯一的一条路径最小生成树(MST)在所有可能的生成树中,边权重之和最小的那颗生成树

Kruskal算法的贪心策略Kruskal算法使用贪心策略来构造最小生成树:定义最优解结构找到一棵包含所有顶点的树,使得所有边的权重之和最小贪心选择规则每次选择权重最小且不会形成环路的边加入到树中更新状态将选择的边和相应的顶点加入到当前的树中构建最终解当树中包含了n个顶点和n-1条边时,生成树构建完成Kruskal算法示例以4个顶点的图为例,边的权重分别为:(A,D):1(B,C):2(A,C):3(A,B):4(C,D):5(B,D):601排序边按权重升序排序所有边02选择边(A,D)权重1,不形成环路,加入MST03选择边(B,C)权重2,不形成环路,加入MST04选择边(A,C)权重3,不形成环路,加入MSTMST构建完成,总建设成本为6(1+2+3=6)。假设使用基于比较的排序算法（如快速排序或归并排序），排序的时间复杂度为Θ(|E|log|E|)，其中|E|表示图中边的数量。算法的主体结构是第3-10行的循环，该循环遍历图中的每一条边。最坏情况下，需要遍历所有|E|条边。对每一条边都要进行环路检测，也就是时间复杂度为|E|Θ(环路检测)。算法总体时间复杂度为Θ(|E|log|E|)+|E|Θ(环路检测)。时间复杂度分析环路检测:深度优先遍历在遍历时,如果访问一个邻接顶点时发现该顶点已经被访问过,并且它不是当前顶点的父顶点,则说明存在环路。从顶点A开始进行深度优先遍历，将A标记为正在访问。深度优先遍历A的第一个邻接点B，将B标记为正在访问，B的相邻顶点是A,C，A已访问并且是B的父顶点，符合父子关系，不构成环。访问B的邻接点C，将C标记为正在访问。C的邻接点有A，B，D。发现A顶点已访问过，且不是C的父顶点，发现环路。上述算法在最坏情况下需要遍历图中的所有顶点和边，其时间复杂度为Θ(|V|+|E|)。并查集:更高效的环路检测并查集是一种用于管理不相交集合的数据结构,支持以下基本操作:初始化每个顶点自成一个集合查找操作find(x)查找元素x所对应集合的代表元素(根顶点)合并操作union(x,y)将包含x的集合和包含y的集合合并当处理一条边(u,v)时,如果find(u)=find(v),说明u和v已经属于同一个集合,此时再连接u与v会形成环路。基于并查集的Kruskal算法基于并查集的Kruskal算法：示例Kruskal算法的时间复杂度O(|E|log|E|)排序阶段对所有边按照权重进行升序排序O(|E|α(V))环路检测使用并查集,α(V)增长极其缓慢,可视为常数O(|E|log|E|)总体复杂度算法总体时间复杂度为Θ(|E|log|E|)Prim算法的核心思想Prim算法体现了"从内向外扩张"的思想。与Kruskal算法不同,Prim算法从图中的任意一个顶点出发,在每一步中选择一条将该子树与尚未加入树的顶点连接起来的最短边。从单个顶点开始最初只有一个顶点的"树"逐步扩张每次迭代子树中增加一个顶点完成构建直到所有顶点都加入树中Prim算法示例

Prim算法时间复杂度分析基于优先队列的Prim算法

优先队列的作用存储未加入MST的顶点按照顶点到子树的距离排序快速提取距离最小的顶点关键操作pop():提取距离最小的顶点decrease_key():更新顶点的距离parent[]:记录每个顶点的父顶点基于优先队列的Prim算法Prim算法的时间复杂度使用最小堆实现优先队列,算法时间复杂度分析如下:O(|V|)初始化将所有顶点加入优先队列O(|V|log|V|)pop操作while循环执行|V|次pop操作O(|E|log|V|)decrease_key操作对每条边最多执行一次decrease_keyO(|E|log|V|)总体复杂度由于连通图中|E|≥|V|-1,化简为O(|E|log|V|)最短路径问题一家物流公司计划为其货车车队确定从配送中心到各个客户网点的运输路线,目标是在满足配送需求的前提下,尽可能减少卡车在路上的行驶距离和时间。问题建模将问题建模为一个带权有向图。顶点代表配送中心或客户网点,有向边表示可行驶的道路,边的权重代表成本(路程、时间或油耗)求解目标从特定的起始点(配送中心)出发,求解到其他各个网点的最短路径,以便在运输过程中尽可能降低成本。最短路径问题的定义在一个带权有向图G=(V,E)中,给定起点s∈V,希望找到从s到其他任意顶点v∈V的最小权重路径,其中边的权重表示通过该边所消耗的代价。最短路径问题即为求出起点s与任意目标顶点v之间的代价最低的路径。随着顶点和边数的增加,一张图中的路径数量会迅速增长,因此尝试枚举所有路径并从中选出最优解的方法并不可行。观察从A出发有两条边：边AB的权重为2，边AC的权重为3，则从A到B的最短路径肯定是边AB？同时利用顶点A和B的信息，则可以确定A→C的最短路径为直接边AC？Dijkstra算法的贪心策略Dijkstra算法使用贪心思想求解最短路径问题(假设边权重非负):1定义最优解结构将顶点分为已确定最短路径的集合D和未确定的集合V\D2贪心选择规则在未确定顶点中,选择距离起点s最近的顶点u3更新状态根据顶点u的邻接边,更新其他顶点的距离估计值4构建最终解不断重复,直至D包含所有顶点Dijkstra算法示例Dijkstra算法的时间复杂度假设优先队列使用二叉堆实现:初始化初始化d[]和π[]数组,时间复杂度O(|V|)extract_min单次O(log|V|),共执行|V|次decrease_key单次O(log|V|),最多执行|E|次总体复杂度O((|E|+|V|)log|V|)=O(|E|log|V|)哈夫曼编码哈夫曼编码是一种用于无损数据压缩的贪心算法,其核心思想是构建哈夫曼树,为不同频率的字符分配不同长度的编码,从而使得整体编码长度达到最小。定长编码字符集合{A,B,C},A出现990次,B和C各出现5次每个字符使用2位编码总编码长度:2×990+2×5+2×5=2000位变长编码A用0表示,B用11表示,C用10表示总编码长度:1×990+2×5+2×5=1010位节省近50%的空间哈夫曼编码的前缀码性质哈夫曼编码需要确保编码方案满足前缀码的性质,即任何一个字符的编码都不是另一个字符编码的前缀,从而保证解码的唯一性。反例如果A、B、C分别用0、00、10来表示,那么对000的解码就会出现歧义,因为它可能代表AAA、AB或者BA。哈夫曼编码的保证哈夫曼编码通过构建哈夫曼树,确保每个字符对应一个叶子节点,从根节点到任意叶子节点的路径都是唯一的,因此必然是一种前缀码。哈夫曼算法的核心操作哈夫曼算法的核心操作是每次从优先队列中提取两个频率最小的节点,创建一个新的内部节点,其频率为这两个节点频率之和。提取最小节点从优先队列中提取两个频率最小的节点创建新节点创建新的内部节点频率为两节点之和插入队列将新节点重新插入优先队列重复迭代直到队列中只剩下一个节点(根节点)哈夫曼编码示例6个字符及其频率:A:5,B:9,C:12,D:13,E:16,F:45

哈夫曼算法的时间复杂度O(n)初始化将n个字符插入优先队列O(nlogn)构造哈夫曼树循环执行n-1次,每次两次extract_min操作O(n)生成编码遍历哈夫曼树,为每个字符分配编码O(nlogn)总体复杂度算法总体时间复杂度为O(nlogn