汇编语言13章贪心算法-2016

1、第第13章章 贪心法贪心法 引论引论n优化问题:贪心法常用于解优化问题。n应用：（1）货箱装船（Container Loading)问题（2）背包问题（3）拓扑排序问题 (4) 哈夫曼编码问题（5）最短路径问题（6）最小代价生成树 (7) 偶图覆盖问题13.113.1优化问题优化问题n一个优化问题可以描述如下:（1）问题的解问题的解为一复杂的结构，例如元组形式 （2）约束条件约束条件： (结构性的约束条件) 使 为true的元组称为可行解 （feasible solution）；（3）目标函数目标函数 n优化解即指使目标函数极大化(或极小化)的可行解，对应的目标函数值称为优化值。iisx ),

2、.,(1nxxB),.,(1nxxB).,(nixxf),.,(21nxxx例例: :货箱装船问题货箱装船问题n设有n个集装箱,集装箱大小一样，第i个集装箱的重量为wi(1in),设船的载重量为c.n试设计一装船的方法使得装入的集装箱数目最多.n令 代表一种装法 n约束条件 n目标函数n极大化目标函数),.,(1nxxcxwniii1niix11 ,0ixn很多优化问题是NP难度问题，迄今找不到它们的多项式算法。所以计算上可行的方法就是求其近似解。n贪心法是求近似解的主要途径。n贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选

3、择。当然，希望贪心算法得到的最终结果也是整体最优的。n贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。n在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。13.213.2贪心算法贪心算法贪心算法的基本要素贪心算法的基本要素n对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。n但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。 n1.贪心选择性质n所谓贪心选择性质是指所求问题的整体最优解可以通过

4、一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。n动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 n对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。n2.最优子结构性质n当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。n问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 13.2贪心法的步骤n贪心法是一种多步(stag

5、e)求解的方法; n每步按一种局部优化的策略选择解(元组)的一个分量;n算法以第n步结束时构造出的对象(元组)作为问题的解. n这种局部优化的策略又称为“贪心标准(greedy criterion).贪心法的主要特点是：n不回溯:选定一个分量后，不重试其它可能。n使用局部优化策略的主要原因是减小计算开销. 但局部优化策略不保证得到精确优化解，可能得到的是近似解。 特别是对NP难度问题。n不同的“贪心”策略得到不同的算法。n常常采纳使目标函数有最大增量的策略为贪心策略，增量是局部性概念。n遗传算法、神经网络等等都是具有这类贪心性质的启发式算法。 例：找零钱问题n假设有四种硬币，它们的面值分别为二

6、角五分、一角、五分和一分。假设有四种硬币，它们的面值分别为二角五分、一角、五分和一分。n现在要找给某顾客六角三分钱。现在要找给某顾客六角三分钱。这时，我们会不假思索地拿出这时，我们会不假思索地拿出2个二角五分的硬个二角五分的硬 币，币，1个一角的硬币个一角的硬币和和3个一分的硬币交给顾客。个一分的硬币交给顾客。这种找硬币方法与其他的找法相比，所拿出的硬币个数是最少的。这这种找硬币方法与其他的找法相比，所拿出的硬币个数是最少的。这里，我们下意识地使用了这样的找硬币算法：里，我们下意识地使用了这样的找硬币算法： 首先选出一个面值不首先选出一个面值不超过六角三分的最大硬币，即二角五分；然后从六角三分

7、中减去二角超过六角三分的最大硬币，即二角五分；然后从六角三分中减去二角五分，剩下三角八分；再选出一个面值不超过三角八分的最大硬币，五分，剩下三角八分；再选出一个面值不超过三角八分的最大硬币，即又一即又一 个二角五分，如此一直做下去。这个找硬币的方法实际上就个二角五分，如此一直做下去。这个找硬币的方法实际上就是贪心算法。是贪心算法。顾名思义，顾名思义，贪心算法总是作出在当前看来是最好的选择。也就是说贪贪心算法总是作出在当前看来是最好的选择。也就是说贪心算法并不从整体最优心算法并不从整体最优 上加以考虑，它所作出的选择只是在某种意上加以考虑，它所作出的选择只是在某种意义上的局部最优选择义上的局部最

8、优选择。例：活动安排问题n活动安排问题活动安排问题要在所给的活动集合中选出最大的相容活动子集合，要在所给的活动集合中选出最大的相容活动子集合，该问题要求高效地安排一系列争用某一公共资源的活动。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单的方法使得尽可能多的活动能兼容地使用公共资源。贪心算法提供了一个简单的方法使得尽可能多的活动能兼容地使用公共资源。n设有设有n个活动的集合个活动的集合E=1,2,n，每个活动都要求使用同一资源，如演讲会场等，每个活动都要求使用同一资源，如演讲会场等，同一时间内只有一个活动能使用这一资源。同一时间内只有一个活动能使用这一资源。每个活动每

9、个活动i都有一个要求使用该资源的起始时间都有一个要求使用该资源的起始时间si和一个结束时间和一个结束时间fi,且且si fi 。如果选择了活动如果选择了活动i，则它在半开时间区间，则它在半开时间区间si, fi)内占用资源。内占用资源。若区间若区间si, fi)与区间与区间sj, fj)不相交，则称活动不相交，则称活动i与活动与活动j是相容的。即当是相容的。即当sifj或或sjfi时，活动时，活动i与活动与活动j相容相容。贪心算法描述n下面所给出活动安排问题的贪心算法greedySelector :public static int greedySelector(int s, int f, b

10、oolean a)int n=s.length-1;a1=true;int j=1;int count=1;for (int i=2;i=fj) ai=true;j=i;count+;else ai=false;return count;各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列 n由于输入的活动以其完成时间的非减序排列非减序排列，所以算法greedySelector每次总是选择具有最早完成时间最早完成时间的相容活动加入集合A中。n直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的使剩余的可安排时间段极大化可安排时

11、间段极大化，以便安排尽可能多的相容活动。n算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。n如果所给出的活动未按非减序排列，可以用min堆重排。n算法复杂度为(nlogn)例：例：机器调度 n现有n个任务和足够多台机器, 假定任何时间一台机器只能执行一个任务.设任务i的开始时间为si, 完成时间为fi, sifi.si, fi 为处理任务i 的时间区间.称两个任务i, j 重叠是指两个任务的时间区间有重叠. 例如：区间1,4与区间2,5重叠, 而与区间4,7不重叠.n可行的任务分配是指该分配

12、中没有将重叠的任务分配给同一台机器.n最优分配指占用机器数最少的可行分配.图13-1 7个任务及使用三台机器的调度a) 7个任务 b) 调度例13.5(续)n按任务起始时间对任务排序并按此顺序安排任务.n贪心准则:尽可能使用旧(old)的机器.n定义每台用过的机器的可用时间为这台机器上最近执行的任务的完成时间.n如果一个新任务的起始时间这些机器的最小可用时间则安排该任务在这台机器上执行; 否则使用一台新机器.n使用min-堆存放每台机器的可用时间,即此时间以后可安排新任务.n算法的时间复杂度为(nlogn)(排序和堆操作).n贪心算法并不总能求得问题的整体最优解。但对于活动安排问题、机器调度问

13、题，上述贪心算法却总能求得整体最优解.n以机器调度问题为例进行证明n证明:n任何可行解使用的机器数最大重迭任务数; 所以优化调度使用的机器数最大重迭任务数.n贪心解使用的机器数不超过最大重迭任务数：任何时候当算法使用一台新机器时, 当前这些机器上的任务一定是彼此重叠的.贪心算法性能例：最短路算法n给定一个有向图G, 一个源节点s,目的节点d; 找从s 到d 的一条最短路径.n从s开始选离s“最近”的下一个节点q; 再从q开始找和q相邻的且不在前面已选择的路径上的下一节点;n重复这一过程直到遇到d节点或该路径无法继续延伸.n贪心解不是优化解: 按贪心法找到的1到5的路径为(1, 3, 4, 2,

14、 5).13.3贪心算法的应用（1）货箱装船（Container Loading)问题（2）背包问题（3）拓扑排序问题 (4) 哈夫曼编码问题（5）最短路径问题（6）最小代价生成树 (7) 偶图覆盖问题13.3.1 Container loadingn目标函数：装载的集装箱数目.n极大化目标函数.n贪心标准：在还没装船的集装箱中选择重量最小的集装箱.n按上述策略,重量最小的集装箱先装,依此类推.n算法：首先按重量从小到大对集装箱排序并依次装入直到超过船的载重量.定理13.1n上述贪心法产生的解是最优解上述贪心法产生的解是最优解, 证明如下证明如下:n设货箱装船问题的最优解为设货箱装船问题的最优

15、解为(y1,yn).n如最优解不含箱子如最优解不含箱子1(y1=0), 将箱子将箱子1替换优化解中某一个替换优化解中某一个箱子得到一个新的解箱子得到一个新的解.n替换是必须的替换是必须的: 因为如果箱子因为如果箱子1还能装入船中还能装入船中, 则则(y1,yn)不是优不是优化的化的.n因为箱子因为箱子1是最轻的是最轻的,替换后的解仍是可行的替换后的解仍是可行的.n替换后的解装入的箱子数等于优化的装箱数替换后的解装入的箱子数等于优化的装箱数, 所以它仍是优化解所以它仍是优化解.n替换后新的优化解和贪心解都包含箱子替换后新的优化解和贪心解都包含箱子1.n反复替换将得到一个优化解反复替换将得到一个优

16、化解,它等于贪心解它等于贪心解.n替换次数是有穷的替换次数是有穷的.13.2.2 0/1背包问题n0/1背包问题：设有背包问题：设有容量容量c的背包和的背包和n件物品件物品, 物品物品i 的重量的重量为为wi ;假定装入物品假定装入物品i 获得的效益值为获得的效益值为pi, 试给出一装入物试给出一装入物品的方法品的方法,使获得的总效益值最大使获得的总效益值最大.n集装箱装载问题是集装箱装载问题是0/1背包问题的特例：背包问题的特例： pi=1n0/1背包问题是背包问题是NP难度问题难度问题, ,所以任何有多项式复杂所以任何有多项式复杂度的算法产生的解都是近似解度的算法产生的解都是近似解. .1

17、3.2.2 0/1背包问题n背包问题可形式化描述如下:n使用0/1数组(x1,xn)表示一个装法: xi=1表示装物品i, 否则不装.n约束条件： n目标函数： ,等于装入物品的总效益值n极大化目标函数cxwniii1iniixp10/1背包问题n0/1背包问题有多种贪心策略（1）从未装入的物品中,选出效益值最大的物品装入.利用这种规则，效益值最大的物品首先被装入(假设有足够容量),然后是下一个效益值最大的物品,如此进行下去. 注：这种策略不一定能保证得到最优解nn=3,c=105,w=100,10,10,p=20,15,15 贪心解为：1,0,0，效益值为：20但优化解为：0,1,1，效益值

18、为30 (续)n(2)从尚未装入的物品中选择重量最小的物品.虽然这一贪心法对于货箱装船问题能产生最优解,但在一般情况下不一定能得到最优解n例：n=2,c=25,w=10,20,p=5,100n(3)(3)按按密度pi/wi,从未装的物品中选择可装入背包 (装入后不超过背包容量),且密度值最大的物品. 贪心解为1,0,0,但优化解为0,1,1n例：c=11,w=(2,4,6,5),p=(6,10,12,9)优化解为：x=(1,1,0,1).n注：这种策略也不能保证得到最优解n例：n=3,c=30,w=20,15,15,p=40,25,25(续)n密度贪心法的伪代码: (1)将物品按密度从大到小排

19、序 (2)for (i=1;i1,y1,贪心解的效益值贪心解的效益值1010；n当当y10/9y10/9时时, ,优化效益值优化效益值9y.9y.n不管优化值多大不管优化值多大, ,贪心解的值总是贪心解的值总是10.10.n误差为误差为(9y-10)/9y=1-(10/9y).(9y-10)/9y=1-(10/9y).对足够大的对足够大的y,y,误差可达到百分之百误差可达到百分之百. .例13.9 k-优化算法nk-k-优化算法是上述密度贪心算法的改进，改进后其优化算法是上述密度贪心算法的改进，改进后其误差可控制在误差可控制在 1/(k+1)*100之内之内. 例如例如3-3-优化算法的误差为

20、优化算法的误差为2525. .nk-优化算法也要先对物品按密度从大到小排序优化算法也要先对物品按密度从大到小排序;n先将一些物品装入背包先将一些物品装入背包, 然后对其余物品用贪心法然后对其余物品用贪心法; n预先装入的物品数不超过预先装入的物品数不超过k.n对所有物品数不超过对所有物品数不超过k的物品子集执行上述过程的物品子集执行上述过程,并从中找到有最大效并从中找到有最大效益值的解作为益值的解作为k-优化算法的解优化算法的解.n考虑考虑n=4,w=2,4,6,7,p=6,10,12,13,c=11.n=4,w=2,4,6,7,p=6,10,12,13,c=11.n使用使用2-2-优化算法如

21、下：优化算法如下： 当当k=0k=0时时, ,同于前述的密度贪心法同于前述的密度贪心法. .因此解为因此解为x=1,1,0,0,x=1,1,0,0,效益值为效益值为1616. .例13.9(续1）nk =1时,最初的子集为1,2,3,4.n子集1,2产生与k=0时相同的结果n考虑子集3,置x3为1,此时背包剩余容量为5，未装的物 品为1,2,4.使用贪心法,得到的解为 x=1,0,1,0，效益值为18.n从子集4开始,产生的解为x=1,0,0,1，效益值为19.n因此，k=0,1时获得的最优解为1,0,0,1. 例13.9（续2）n若k=2, 除了考虑k0)得到的解误差不超过得到的解误差不超过

22、 (1/(k+1)*100n当当k=1时时,为为50%以内以内,即如优化值为即如优化值为100,贪心法算出的值贪心法算出的值不低于不低于50;n当当k=2时时,为为33.33%以内以内.n算法的时间复杂度随算法的时间复杂度随k 的增大而增加的增大而增加:n需要测试的子集数目为需要测试的子集数目为O(nk );n每一个子集做贪心法需时间每一个子集做贪心法需时间O(n);n因此当因此当k 0时总的时间开销为时总的时间开销为O(nk+1 ).6 0 0种随机测试的统计结果13.3.1 哈夫曼编码问题n哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其哈夫曼编码是广泛地用于数据文件压缩的十分有

23、效的编码方法。其压缩压缩率通常在率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用表来建立一个用0，1串表示各字符的最优表示方式。串表示各字符的最优表示方式。n给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。可以大大缩短总码长。n例如一个包含例如一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。个字符的文件，各字符出现频率不同，如下表所示。定定长编码长编码需要需要300,000位，而按表中变长编码方案，文件的总

24、码长为：位，而按表中变长编码方案，文件的总码长为：（451+133+123+163+94+54）1000=224,000。abcdef频率(千次)4513121695定长码000001010011100101变长码010110011111011100前缀码n对每一个字符规定一个对每一个字符规定一个0,1串作为其代码，并要求任串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀，这种编一字符的代码都不是其它字符代码的前缀，这种编码称为码称为前缀码前缀码。n编码的前缀性质可以使译码方法非常简单。编码的前缀性质可以使译码方法非常简单。n平均码长定义为：平均码长定义为：n使平均码长达到最小的前缀

25、码编码方案称为给定编使平均码长达到最小的前缀码编码方案称为给定编码字符集码字符集C的最优前缀码。的最优前缀码。)()()(cdcfTBTCc构造哈夫曼编码n哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。编码。n具体算法为：具体算法为： （1）根据）根据n个权值个权值w1，w2，wn构成构成n棵二叉树的集合棵二叉树的集合F=T1，T2，Tn，其中每棵二叉树其中每棵二叉树Ti中只有一个带权为中只有一个带权为wi的根结点，其左右子树均为空的根结点，其左右子树均为空 （2）在）在F中选取两棵根结点的权值最小的树作为

26、左右子树来构造一棵新的二叉树，中选取两棵根结点的权值最小的树作为左右子树来构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树结点的根结点的权值之和。且置新的二叉树的根结点的权值为其左、右子树结点的根结点的权值之和。 （3）在）在F中删除这两棵树，同时将新得到的二叉树加入中删除这两棵树，同时将新得到的二叉树加入F中。中。 （4）重复（）重复（2）和（）和（3），直到），直到F中只含一棵树时为止。称这棵树为最优二叉树（或中只含一棵树时为止。称这棵树为最优二叉树（或哈夫曼树）。哈夫曼树）。如果约定将每个结点的左分支表示字符如果约定将每个结点的左分支表示字符“0”，右分支表示字符，右分支表

27、示字符“1”，则可以把从，则可以把从根结点到某叶子结点的路径上分支字符组成的字符串作为该叶子结点的编码。根结点到某叶子结点的路径上分支字符组成的字符串作为该叶子结点的编码。 n哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。n算法以算法以|C|个叶结点开始，执行个叶结点开始，执行|C|1次的次的“合并合并”运算后产生最终所运算后产生最终所要求的树要求的树T。算法说明n统计编码字符集中每一字符统计编码字符集中每一字符c的频率的频率f(c)。以。以f为键值的优先为键值的优先队列队列Q用在贪心选择时有效地确定算法当前要合并的用在贪心选择时有

28、效地确定算法当前要合并的2棵具棵具有最小频率的树。一旦有最小频率的树。一旦2棵具有最小频率的树合并后，产生棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的一棵新的树，其频率为合并的2棵树的频率之和，并将新树棵树的频率之和，并将新树插入优先队列插入优先队列Q。经过。经过n1次的合并后，优先队列中只剩次的合并后，优先队列中只剩下一棵树，即所要求的树下一棵树，即所要求的树T。n算法可以用最小堆实现优先队列算法可以用最小堆实现优先队列Q。初始化优先队列需要。初始化优先队列需要O(nlogn)计算时间，由于最小堆的插入和删除运算均需计算时间，由于最小堆的插入和删除运算均需O(logn)时间，时间

29、，n1次的合并总共需要次的合并总共需要O(nlogn)计算时间。计算时间。因此，关于因此，关于n个字符的哈夫曼算法的计算时间为个字符的哈夫曼算法的计算时间为O(nlogn) 。图论（Graph）相关的应用问题n图的基本知识图的基本知识n定义：一个有向图定义：一个有向图G=(V, E)是由包含顶点和边的是由包含顶点和边的有序点对组成，其中有序点对组成，其中V是顶点集合，是顶点集合，E是边的集是边的集合合.n在无向图中，在无向图中，G=(V, E),边集合边集合E由无序点对组成由无序点对组成.n在有向图和无向图中，在有向图和无向图中，|E|=O(V2)n若若G是连通图，则是连通图，则|E|=|V|

30、-1,即即lg(E)=(lgV)邻接矩阵(adjacency matrix)邻接表(adjacency list)邻接表的存储复杂度为(V+E), 边稀疏时适用。 13.3.2 拓扑排序拓扑排序定义：n任务的先后顺序可用有向图表示任务的先后顺序可用有向图表示,称为称为AOV网络网络(Activity On Vertex).有向图的顶点代表任务有向图的顶点代表任务,有向边有向边(i,j)表示先后表示先后关系关系:任务任务i完成后才能开始任务完成后才能开始任务j .n根据上述根据上述AOV网络我们要对任务进行排序使得排序序列网络我们要对任务进行排序使得排序序列的先后关系与的先后关系与AOV网定义的

31、先后关系一致网定义的先后关系一致.n根据任务的有向图建立拓扑序列的过程称为拓扑排序根据任务的有向图建立拓扑序列的过程称为拓扑排序.13.3.2拓扑排序n对有向图的所有顶点的所有排列逐个检验的方法是不足对有向图的所有顶点的所有排列逐个检验的方法是不足取的取的: :O(n!)的时间复杂度的时间复杂度.n贪心法从空集开始，每步产生拓扑排序序列中的一个顶贪心法从空集开始，每步产生拓扑排序序列中的一个顶点点w,w,怎样选择顶点怎样选择顶点w？ngreedy策略策略:从当前尚不在拓扑排序序列的顶点中选从当前尚不在拓扑排序序列的顶点中选择一顶点择一顶点w,其其所有先行节点所有先行节点v都在已产生的拓扑序列都

32、在已产生的拓扑序列中中(或无先行顶点或无先行顶点)并将其加入到并将其加入到拓扑序列中拓扑序列中. n用减节点入度的方法确定用减节点入度的方法确定w:入度变成入度变成0的顶点为要加的顶点为要加到到拓扑序列中的拓扑序列中的顶点顶点.使用栈的伪代码n(1)计算每个顶点的入度计算每个顶点的入度n(2)将入度为将入度为0的顶点入栈的顶点入栈n(3)While(栈不空栈不空)n 任取一入度为任取一入度为0的顶点放入拓扑序列中的顶点放入拓扑序列中; 将与其相邻的顶点的入度减将与其相邻的顶点的入度减1; 如有新的入度为如有新的入度为0的顶点出现的顶点出现,将其放入将其放入 栈中栈中; n(4)如有剩余的顶点则

33、该图有环路如有剩余的顶点则该图有环路引理13.1n如果上述伪代码表示的算法失败如果上述伪代码表示的算法失败,则有向图含有环路则有向图含有环路.n设设V为算法结束时算法输出的节点构成的集合为算法结束时算法输出的节点构成的集合n证明：当失败时证明：当失败时|V|n, 且剩下的顶点不能加入已排好的序且剩下的顶点不能加入已排好的序列列V中中.n至少有一节点至少有一节点q1不在不在V中中,和一条边和一条边(q2,q1)且且q2不在不在V中中, 否则否则q1可加入可加入V中中.n同理同理,有边有边(q3,q2）且且q3不在不在V中中. 若若q3=q1 则则q1q2q3 是有向图中是有向图中的一个环路的一个

34、环路,若若q3q1，则必存在则必存在q4,（q4,q3）是有向图的边且是有向图的边且q4不在不在V中中. 否则否则q3应在应在V中中.若若q4为为q1,q2,q3 中的任何一个中的任何一个,则则该有向图含有环该有向图含有环.n因为有向图有有限个节点因为有向图有有限个节点,重复上述步骤重复上述步骤,一定能找到一个环一定能找到一个环路路. 程序13.2拓扑排序程序13.2拓扑排序（续1）程序13.2拓扑排序（续2）算法13.2的时间复杂度n(n2 ):使用邻接矩阵;n(n+e):使用邻接表;n第一个第一个for循环，初始化入度数组需循环，初始化入度数组需O(n)时间时间n计算入度计算入度:若使用邻

35、接矩阵，所用时间为若使用邻接矩阵，所用时间为O(n2),若使若使用邻接表，所用时间为用邻接表，所用时间为O(n+e);n进出栈次数进出栈次数:O(n);n使用邻接矩阵每步修改入度时间为使用邻接矩阵每步修改入度时间为O(n);使用邻接表使用邻接表每步修改入度时间为每步修改入度时间为O(节点的出度节点的出度);n总的修改入度时间为总的修改入度时间为O(n2)或或O(n+e):有向图的所有有向图的所有节点出度之和等于图的边数节点出度之和等于图的边数.13.3.3 单源最短路径n任给一有向图任给一有向图G,它的每条边都有一个非负的权值它的每条边都有一个非负的权值aij, 路径的长度定义为路径上边的权值

36、之和路径的长度定义为路径上边的权值之和.n单源最短路问题单源最短路问题:给定源节点给定源节点s,找出从找出从s到图中所有其他节到图中所有其他节点点(称为目的称为目的)的最短路径的最短路径(优化解优化解)及其长度及其长度(优化值优化值)n例：网络中传输数据流时例：网络中传输数据流时, 要耗费网络的带宽和存储资源要耗费网络的带宽和存储资源,使用跳数少的路径节省网络资源使用跳数少的路径节省网络资源.nIP路由使用最短路算法路由使用最短路算法(OSPF), 因为因为IP路由表按目的节路由表按目的节点索引点索引(查找查找), 所以所以, OSPF协议使用该算法求出网络中目协议使用该算法求出网络中目的节点

37、到任一节点的最短路的节点到任一节点的最短路. Dijkstras 最短路算法n如果链路权值非负如果链路权值非负, 则最短路的子路径也是最短路则最短路的子路径也是最短路,其长其长度小于原来路径的长度度小于原来路径的长度. 所以所以, 长度较小的最短路容易找长度较小的最短路容易找到到.n贪心策略贪心策略:按最短路长度从小到大依次求解按最短路长度从小到大依次求解.nDijkstras 最短路算法使用上述贪心策略最短路算法使用上述贪心策略,是图论算法中是图论算法中应用最为广泛的算法应用最为广泛的算法, 主要原因是其计算复杂度低且容易主要原因是其计算复杂度低且容易实现实现.n1.维护一个集合维护一个集合

38、S，该集合中源节点到其他节点的最短路已知，该集合中源节点到其他节点的最短路已知，初始时该集合为空初始时该集合为空n2.从从V-S集合中找一节点集合中找一节点v，满足源节点到该节点距离最小，满足源节点到该节点距离最小n3.更新更新v的邻节点的到源节点的距离值的邻节点的到源节点的距离值Dijkstras 最短路算法基本步骤Dijkstras 算法Dijkstras 算法分析每个Extract-min操作的平摊代价无权图（Unweighted graphs）n 假定，对所有点对假定，对所有点对(u,v)E, w(u,v)=1, Dijkstra 算法能否进算法能否进一步改进？一步改进？n可使用可使用

39、FIFO队列代替优先队列队列代替优先队列n广度优先算法如下：广度优先算法如下：广度优先算法例题源节点到其它所有节点的最短路n若图G=(V,E)包含负权回路，则最短路径可能不存在。n例nBellman-Ford 算法：找出源节点到其它任意节点的最短路，或确定图中包含负值环路负权环图(Negative-weight cycles)n单源最短路径n非负权重nDijkstra 算法复杂度：O(E+VlgV)n一般情况下：nBellman-Ford算法复杂度O(VE)n多源最短路径n非负权值， nDijkstra算法复杂度O(VE+V2lgV)n一般情况（权值可能为负）nBellman-Ford算法为O

40、(V2E)或O(V4)最短路径问题小结13.3.6最小生成树n具有具有n n 个顶点的连通的无向图个顶点的连通的无向图G ,G ,图的每条边图的每条边e e有一非负有一非负权值权值c(e),c(e),也称为成本也称为成本, ,求有最小成本的生成树求有最小成本的生成树. .n每个生成树刚好具有每个生成树刚好具有n-1n-1条边，所以问题是用某种方法选条边，所以问题是用某种方法选择择n-1n-1条边使它们形成条边使它们形成G G的最小生成树。的最小生成树。n我们采用以下二种不同的贪心策略来选择这我们采用以下二种不同的贪心策略来选择这n-1n-1条边。条边。这二种贪心策略对应求解最小生成树的二个算法

41、：这二种贪心策略对应求解最小生成树的二个算法：KruskalsKruskals算法，算法，PrimsPrims算法。算法。Kruskals算法n贪心策略:每次选择权值c(e)最小且与以前选择的边不构成cycle的边e.n上述策略要求按权值从小到大对边排序.图13.12构造最小生成树图13.12构造最小生成树（续1）图13.12构造最小生成树（续2）图13.13 Kruskals算法的伪代码算法正确性证明n定理定理: Kruskals算法产生一棵最小生成树算法产生一棵最小生成树.n设设T是贪心法产生的解，是贪心法产生的解，U是优化解是优化解n设设e是属于是属于T但不属于但不属于U的成本最小的边的

42、成本最小的边;换言之换言之,T中成本小于中成本小于c(e)的的边都在边都在U中中.n设设f是是e+U产生的环路上不在产生的环路上不在T中的一条边中的一条边,这样的这样的f一定存在一定存在,否则否则T将包含一个环路将包含一个环路.n下面用反证法证明下面用反证法证明c(f)c(e):nT中成本小于中成本小于c(e)的边都在的边都在U中中,所以所以f与这些边不构成环路与这些边不构成环路(这这些边都在些边都在U里里);n如果如果f的成本小于的成本小于e的成本的成本,贪心法会先于贪心法会先于e将将f加入到加入到T中中,矛盾矛盾. （说明（说明c(f)不小于不小于c(e)）n从从U中删除中删除f并加入并加

43、入e,得到的树得到的树U仍是优化的仍是优化的.算法实现数据结构n算法执行过程中动态产生的子树算法执行过程中动态产生的子树, 反复进行反复进行union和和find操作操作,使用下面的数据结构很有效使用下面的数据结构很有效.nUNINFIND数据结构数据结构n初始为单个顶点的集合初始为单个顶点的集合n对每条边做对每条边做2次次FIND找到边的端点所在的集合找到边的端点所在的集合;如果在同如果在同一集合中则舍弃该条边一集合中则舍弃该条边,否则将否则将2个集合合并个集合合并(UNION)n算法可在算法可在O(n+eloge)找出最小生成树找出最小生成树: 边排序边排序: O(eloge) initi

44、alizing:O(n) union-find:O(e) Prims算法n设设A为算法执行过程中产生的生成树中的节点集合为算法执行过程中产生的生成树中的节点集合. 初始化初始化A包含图包含图中任一节点中任一节点;n定义定义V-A中节点中节点u到到A的距离的距离key(u)为为 minc(u,v)|vA, (u,v)En取取V-A中中key(u)最小的节点最小的节点u, 并将其加入到并将其加入到A; n更新更新V-A中的节点到中的节点到A的距离的距离(key值值). n重复执行上述步骤重复执行上述步骤.n算法实现时将V-A中的节点按key值做成一个优先级队列(堆)Q.n每次从V-A中抽取距离最小

45、的节点u, 并修改Q中与u相邻的节点的key值(decrease key).n该算法不要求对边排序.n算法的伪代码如下:Prims 算法图13.5图13.15 Prims 算法举例Prims算法举例（续）Prims 算法复杂度分析复杂度分析 13.3.7偶图覆盖问题（二分覆盖）n偶偶图是一个无向图，它的图是一个无向图，它的n 个顶点分为集合个顶点分为集合A和集合和集合B，且同一集合中的任意两个顶点无边相连。且同一集合中的任意两个顶点无边相连。nA的一个子集的一个子集 A 覆盖集合覆盖集合B iff B中每一顶点至少和中每一顶点至少和 A 中中一顶点相连。覆盖一顶点相连。覆盖 A 的大小指的大小

46、指 A中的顶点数目。中的顶点数目。n在偶图中寻找最小覆盖的问题称为偶图覆盖在偶图中寻找最小覆盖的问题称为偶图覆盖(bipartite-cover)问题。问题。 A例13.10n考察如图13.6所示的具有17个顶点的二分图，nA=1, 2, 3, 16, 17和B=4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15，n子集A= 1 , 1 6 , 17是B的最小覆盖：1覆盖4,6,7,8,9,13;16覆盖5,6,8,12,14,15; 17覆盖4,9,10,11图13.6 例13.10所使用的图集合覆盖问题n偶图覆盖等价于集合覆盖问题。集合覆盖问题是NP难度问题。n

47、集合覆盖问题：n个集合的族F 满足 ，设 为F的子族且 则称其为U的一个覆盖 n集合覆盖问题是指找包含的集合数目最小的覆盖。 ,1nSS USini1,1ikiSSUSijnj1例13.11n 令F= S1, ,S5 ，U= 4,5,.,15， S1=4,6,7,8,9,13，S2=4,5,6,8， S3=8,10,12,14,15，S4=5,6,8,12, 14,15，S5= 4,9,10,11。nS= S1,S4,S5是一个大小为3的覆盖，没有更小的覆盖， S 即为最小覆盖。n这个集合覆盖问题可变换为图13.6的偶图，即用顶点1，2，3，16和17分别表示集合S1，S2，S3，S4 和S5，顶点j 表示集合U中的元素j，4j15。n两个问题等价，都是NP难度问题偶图覆盖问题的贪心解n贪心策略：选择覆盖B中那些尚未被覆盖的顶点数最多的A的节点n对图13.6应用上述贪心法，得到 A1,16,17，算法描述见图13.7图13.7贪心启发式算法的伪代码实现问题n设 , 为i覆盖的B 中尚未被覆盖的顶点数。 为动态变化的量。需设计数据结构对其进行