13章贪心算法

1、算法设计与分析,主讲教师：张连芳 天津大学计算机系 L,内容介绍,五种基本的算法设计方法： (1)贪心法; (2)分而治之算法; (3)动态规划; (4)回溯; (5)分枝定界。 NP-难度和NP-完全问题,第13章 贪心法,引论,优化问题:贪心法常用于解优化问题。 应用： （1）货箱装船（Container Loading)问题 （2）背包问题 （3）拓扑排序问题(?) （4）最短路径问题 （5）最小代价生成树,13.1优化问题,一个优化问题可以描述如下: （1）问题的解为一复杂的结构，例如元组形式 （2）约束条件： (结构性的约束条件) 使 为true的元组称为可行解 （feasible）

2、； （3）目标函数 优化解即指使目标函数极大化(或极小化)的可行解，对应的目标函数值称为优化值。 很多优化问题是NP难度问题，迄今找不到它们的多项式算法。所以计算上可行的方法就是求其近似解。贪心法是求近似算法的主要途径。,例13.1Thirsty Baby,有一个聪明的婴儿，她可能得到的饮料包括一桶水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水。假定婴儿可得到n 种不同的饮料。根据以前关于这n 种饮料的不同体验，婴儿知道其中那些饮料更合自己的胃口。因此，婴儿为每一种饮料赋予一个满意度值si：饮用1盎司第i 种饮料，满意度si。 设第i种饮料有ai盎司，婴儿共需喝t盎司饮料

3、,例13.1Thirsty Baby,设xi 为第i种饮料的饮用量，假定满意程度是可加的，则最满意的选择是极大化 该优化问题可表示如下 约束条件 目标函数 ,例13.2loading Problem,一艘船准备用来装载货物,所有货物都放在集装箱中。设第i 个集装箱的重量为wi（1in），船的最大载重量为c，试设计一装载方法使得装入的集装箱数目最多。,例13.2 Loading Problem,令 代表一种装法 约束条件 目标函数 极大化目标函数,例13.3 最小成本通信网络,城市之间的通信网络应是以这些城市为顶点的连通图,图的每条边代表一条通信线路.给每条边赋予一个权值,等于建设这条通信线路所

4、要花费的成本,最小成本通信网络问题就是找这样一个连通图,其总成本最小. 设所有的权值都非负,则最小成本通信网络问题的可行解可限制为连接这些城市的生成树,而最优解是其中具有最小成本的生成树.,例13.3 最小成本通讯网络,n-1 条边的元组 约束条件：这些边构成生成树 目标函数：边权之和 原则上所有上述问题需在很大的范围内搜索 优化解；但这常常导致指数复杂度的算法； 是计算上不可接受的。贪心法退而求其次求 所谓的“次优”解。,13.2贪心法,贪心法指每步(stage)按所谓的“贪心标准(策略)”选择(元组的)一个分量，逐步构造出问题解的方法。 贪心法的主要特点是： （1）不回溯:选定一个分量后,

5、不重试其它可能。 （2）贪心标准指每次选择一个分量时使用的“优化”策略。所选策略可能导致优化解，但更多情形是得到近似解，特别是对NP难度问题。不同的人可能有不同的“优化”策略。 （3）常常采纳使目标函数有最大增量的策略为贪心策略。,例13.4找零钱,一个小孩买了价值少于1美元的糖，并将1美元的钱放入取款机。取款机要用数目最少的硬币将零钱找给小孩。假设取款机内有任意多的面值为25美分、10美分、5美分、及1美分的硬币。 贪心策略为：每次给出不超过应找钱数的面值最大的硬币。 贪心策略得到优化解: 在2025美分之间选2个10美分最好. 25-30之间选一个25最好;在3个10美分不如一个25加一个

6、5美分等等. 硬币面值之间有倍数关系;否则没解:例如,面值 14,12,5和1;则17125,用2枚硬币,而贪心法为14加3个1,共4枚硬币.,例13.5 机器调度,现有n 个任务和足够多台处理这些任务的机器。每个任务的开始时间为si，完成时间为fi，sifi 。si,fi 为处理任务i 的时间区间。两个任务i，j 重叠是指两个任务的时间区间有重叠。例如：区间1,4与区间2,5重叠，而与区间4,7不重叠。 可行的任务分配是指该分配中没有将重叠的任务分配给同一台机器。在可行的分配中每台机器在任何时刻最多只处理一个任务。 最优分配指占用机器数最少的可行分配。,图13-1 任务及三台机器的调度 a)

7、 7个任务b) 调度,例13.5(续),贪心准则：尽可能使用旧机器，即以前使用过的机器。 按任务起始时间排序并安排任务 上述贪心法产生优化解:任何可行解使用的机器数不少于最大重迭任务数;贪心解使用的机器数不超过最大重迭任务数. 实现问题：使用min-堆存放每台旧机器的可用时间,即此时间以后可安排新任务. 算法的时间复杂度为(nlogn).,例题13.6(最短路算法),选择“最近”的且不在路径上的下一节点 贪心解不是优化解:,13.3应用,Container Loading（货箱装船）问题 0/1背包问题 拓扑排序问题 最短路径问题 最小代价生成树,13.3.1 Container loadin

8、g,船可以分步装载，每步装一个集装箱，且需要考虑装载哪一个集装箱。 目标函数：装载的集装箱数目。 极大化目标函数。 贪心标准：在剩下的集装箱中选择有最小重量的集装箱 为此算法首先按重量对物品排序,程序13.1,程序13.1（续）,定理13.1,上述贪心法产生的解是优化解: 优化解(y1,yn)可经有限次替换得到贪心解,而且每次替换箱子数不变. 如该优化解不会箱子1,将其替换其中一个箱子,仍是优化解.(必须替换,否则不是优化解)反复替换将得到一个优化解,它就是贪心法得到的解.,13.2.2 0/1背包问题,0/1背包问题：设有容量c的背包，和n件物品，物品i的重量为wi，假定装入物品i获得的效益

9、值为pi,试给出一装入物品的方法，使得获得的总效益值最大。 集装箱装载问题是0/1背包问题的特例。 0/1背包问题是NP难度问题。所以贪心法产生的解是近似解。,13.2.2 0/1背包问题,约束条件： ， 目标函数：装入物品效益值 极大化目标函数： 在这个表达式中，需求出xi的值。xi = 1表示物品i 装入背包中，xi =0 表示物品i 不装入背包。,0/1背包问题,0/1背包问题有多种贪心策略 （1）从未装入的物品中，选出效益值最大的物品装入。利用这种规则，效益值最大的物品首先被装入（假设有足够容量），然后是下一个效益值最大的物品，如此继续下去。这种策略不能保证得到最优解。 n=3,c=1

10、05,w=100,10,10,p=20,15,15 贪心解为：1,0,0，效益值为：20 但优化解为：0,1,1，效益值为30,(续),(2)从尚未装入的物品中选择重量最小的物品。虽然这一贪心法对于上述例子能产生最优解，但在一般情况下不一定能得到最优解。n=2,c=25,w=10,20,p=5,100 (3)按密度pi/wi，从剩余物品中选择可装入背包的密度值最大的物品，这种策略也不能保证得到最优解: n=3,c=30,w=20,15,15,p=40,25,25 贪心解为1,0,0,但优化解为0,1,1,(续),密度贪心法的伪代码: (1)将物品按密度从大到小排序 (2)for (i=1;in

11、;i+) if (物品i 可装入到背包内) xi=1(装入) else xi=0(舍弃); 例如:c=11,w=(2,4,6,5),p=(6,10,12,9) x=(1,1,0,1).恰是优化解 算法的时间复杂度为O(nlogn),(续),贪心法往往不能得到精确解，贪心解与最优解的误差用以下比值的百分比来度量: (优化值-贪心解值)/优化值 n=2,c=y, w=1,y,p=10,9y 贪心解值10；当y10/9时,优化值9y. 误差为(9y-10)/9y.对任意大的y 误差可达到百分之百.即优化值如为m贪心法可能算出近似0的值.,例13.9k-优化算法,k-优化算法是上述密度贪心算法的改进，

12、改进后其误差可控值在100/(k+1)之内. k-优化算法预先将不超过k种物品的子集装入背包，对其余物品用密度贪心法。对所有k物品子集执行上述过程，并从中找到有最大效益值的解。 考虑n=4, w=2,4,6,7, p=6,10,12,13, c=11。k2： 当k=0时，同于前述的密度贪心法。因此解为x=1,1,0,0，效益值为16。,例13.9(续1）,k =1时。最初的子集为1 , 2 , 3 , 4。子集1 , 2产生与k=0时相同的结果，考虑子集3，置x3 为1。此时还剩5个单位的容量，按价值密度非递增顺序来考虑如何利用这5个单位的容量。首先考虑物品1，它适合，因此取x1为1，这时仅剩

13、下3个单位容量了，且剩余物品没有能够加入背包中的物品。通过子集3开始求解得结果为x=1,0,1,0，获得的价值为18。若从子集4开始，产生的解为x=1,0,0,1，获得的价值为19。k=0,1时获得的最优解为1,0,0,1。,例13.9（续2）,若k=2，除了考虑k2的子集，还必需考虑子集1,2 , 1,3 , 1,4 , 2,3 , 2,4和3,4。首先从最后一个子集开始，它是不可行的，故将其抛弃，剩下的子集经求解分别得到如下结果：1,1,0,0 , 1,0,1,0 , 1,0,0,1 , 0,1,1,0和0,1,0,1，这些结果中最后一个价值为23。 K-优化解即为0,1,0,1,值为23

14、,例13.9结论,k-优化方法（k0)得到的解误差不超过 (100/(k+1) 当k=1时,为50%以内,即如优化值为100,贪心法算出的值不低于50;当k=2时,为33.33%以内. 算法的时间复杂度随k 的增大而增加,需要测试的子集数目为O(nk ),每一个子集所需时间为O(n),因此当k 0时总的时间开销为O(nk+1 )。,13.3拓扑排序,拓扑排序定义：,任务的先后顺序可用有向图表示,称为AOV网络(Activity On Vertex).有向图的顶点代表任务,有向边(i,j)表示先后关系:任务i完成后才能开始任务j . 根据上述AOV网络我们要对任务进行排序使得排序序列的先后关系与

15、AOV网定义的先后关系一致.根据任务的有向图建立拓扑序列的过程称为拓扑排序.,13.3拓扑排序,对所有顶点的排列逐个检验的方法是不足取的:O(n!)的时间复杂度. 假设从空集开始，每步产生拓扑排序序列中的一个顶点w,怎样选择顶点w？ greedy策略:从不在拓扑序列的顶点中选择一顶点w,其所有先行节点v都在已产生的拓扑序列中(或无先行顶点). 用减入度的方法确定w:入度变成0的顶点,使用栈的伪代码,(1)计算每个顶点的入度 (2)将入度为0的顶点入栈 (3)While(栈不空) 任取一入度为0的顶点放入拓扑序列中; 将与其相邻的顶点的入度减1; 如有新的入度为0的顶点出现,将其放入 栈中; (

16、4)如有剩余的顶点则该图有环路,引理13.1,如果程序13.5失败，则有向图含有环路。 证明：当失败时|V|n,且剩下的顶点不能加入已排好的序列V中，因此至少有一顶点q1不在V中，和一条边(q2,q1)且q2不在V中；否则q1可加入V中。同样，有边(q3,q2）且q3不在V中。若q3=q1 则q1q2q3 是有向图中的一个环路；若q3q1，则必存在q4，（q4,q3）是有向图的边且q4不在V中，否则，q3已在V中。若q4为q1,q2,q3 中的任何一个，则该有向图含有环；因为有向图有有限个顶点，重复上述步骤，一定能找到一个环路。,程序13.2拓扑排序,程序13.2拓扑排序（续1）,程序13.2

17、拓扑排序（续2）,算法的时间复杂度,(n2 ):使用邻接矩阵; (n+e):使用邻接表; 初始入度数组O(n); 计算入度:遍历邻接表O(e)(访问链表的下一节点,入度数组对应项加1合起来视为一步,时间O(1); 进出栈次数:O(n); 每步修改入度时间为O(相邻的边数); 总的修改入度时间为O(e).,13.3.5 单源最短路径,任给一有向图G,它的每条边都有一个非负的权值aij, 路径的长度即为此路径上边的权值之和. 对于给定的源顶点s,需找出从它到图中其他任意顶点（称为目的）的最短路径. IP路由使用最短路算法(OSPF).,OSPF Routing Weight,OSPF Routin

18、g Weight,OSPF Routing Weight,Dijkstras 最短路算法,Dijkstras 最短路算法是图论算法中应用最为广泛的算法. 算法反复使用label update方法. 算法的正确性证明-有普遍意义. 算法的时间复杂度分析-有普遍性.,图13.10最短路径举例,13.3.6最小生成树,具有n 个顶点的连通的无向图G ,图的每条边e有一非负权值c(e),也称为成本,求有最小成本的生成树. 每个生成树刚好具有n-1条边，所以问题是用某种方法选择n-1条边使它们形成G的最小生成树。 我们采用以下二种不同的贪心策略来选择这n-1条边。 这二种贪心策略对应求解最小生成树的二个

19、算法：Kruskals算法，Prims算法。,Kruskals算法,贪心策略:每次选择权值c(e)最小且与以前选择的边不构成cycle的边e. 上述策略要求按权值从小到大对边排序.,图13.12构造最小生成树,图13.12构造最小生成树（续1）,图13.12构造最小生成树（续2）,图13.13 Kruskals算法的伪代码,正确性证明,利用类似装载问题所用的变换技术可以证明图13.13的贪心法总能建立一棵最小生成树. 需要证明： 只要图是连通的, Kruskals算法总能产生一棵生成树; 产生的生成树具有最小成本.,证明,设T是贪心法产生的解，U是优化解 设e是属于T但不属于U的成本最小的边;

20、换言之,T中成本小于c(e)的边都在U中. 设f是e+U产生的环路上不在T中的一条边,这样的f一定在,否则T将包含一个环路. c(f)的不小于c(e): 因T中比e成本小的边都在U中,所以f与T中成本小于e的成本的边(这些边都在U里)不构成环路;如果f的成本小于e的成本,贪心法会先于e将f加入到T中,矛盾. 从U中删除f并加入e,得到的树U仍是优化的.,数据结构,使用UNINFIND数据结构 初始为单个顶点的集合 对每条边做2次FIND找到边的端点所在的集合;如果在同一集合中则舍弃该条边,否则将2个集合合并(UNION) 算法可在O(n+eloge)找出最小生成树: 边排序: O(eloge) initializing:O(n) union-find:O(e),Prims算法,设A为算法执行过程中产生的生成树中的顶点.