算法分析与设计多媒体课件.ppt

《算法分析与设计多媒体课件.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计多媒体课件.ppt（543页珍藏版）》请在课桌文档上搜索。

1、Algorithm Design and Analysis,2023/3/30,1,目录,Chapter1 绪论Chapter2 算法效率分析基础 Chapter3 分治法 Chapter4 减治法Chapter5 变治法,Chapter6 时空权衡Chapter7 动态规划Chapter8 贪心法Chapter9 回溯与分枝限界,附：实例动画集成,Chapter1 绪论 Introduction,2023/3/30,3,绪论,什么是算法算法的实例算法研究的基本问题为什么要学习算法已有的基础数据结构,返回总目录,2023/3/30,4,什么是算法,算法是为了解决某一问题而设计的无疑义的指令序列

2、，对于合法的输入，能在有限的时间内得出所需要的输出。,problem,algorithm,computer,input,output,2023/3/30,5,算法满足下列性质,输 入：有零个或多个外部量作为算法的输入。输 出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。,2023/3/30,6,算法的实例,排序查找最短路径最小生成树旅行商问题背包问题皇后问题汉诺塔,2023/3/30,7,算法研究的基本问题,如何设计算法如何描述算法证明算法的正确性常用数学归纳法算法效率理论分析实证分析算法优化,2023/3

3、/30,8,为什么要学习算法,理论学习上的重要性计科专业的核心课程计科专业的基础课程实践上的重要性,2023/3/30,9,已有的基础数据结构,典型的问题类型排序查找字符串处理图组合问题几何问题数值问题,2023/3/30,10,已有的基础数据结构,数据结构基础表数组链表字符串栈和队列图树集合和字典,2023/3/30,11,思考,带锁的门走廊上n个带锁的门，从1到n一次编号，最初都关着，我们从门前经过n次，每次都从1号门开始，在第i次经过时，我们改变i的倍数的门所状态，这样，最后一次经过时，那些门开着，那些门关着？有四个人过桥，他们都在桥的一端，17分钟让他们全部通过，必须携带手电筒，必须步

4、行携带，每个人速度不同，甲过桥一分钟，乙过桥2分钟，丙过桥5分钟，丁要10分钟，2个人一起走需要的时间是较慢的人的时间，他们要如何走才能顺利完成？,2023/3/30,12,本章结束，返回总目录,Chapter2 算法效率分析基础 Foundation of Algorithm Analysis,2023/3/30,14,算法效率分析基础,研究的主要问题方法时间效率的理论分析时间效率的实证分析最好、最坏与平均情况增长速度非递归与递归分析过程,返回总目录,2023/3/30,15,研究的主要问题,算法的正确性时间效率空间效率最优性,2023/3/30,16,方法,理论分析实证分析,2023/3/

5、30,17,2.1时间效率的理论分析,输入规模 基本运算 为什么要用基本运算？如何找基本运算？,运行时间,基本运算的执行时间,基本运算的执行次数,输入规模,T(n)copC(n),2023/3/30,18,输入规模与基本操作举例,基本运算,输入规模的度量,问题,对节点或对边的访问,节点数或者边数,典型的图问题,除法,n的大小（经常转化为二进制表示，即为二进制的位数）,对于给定的数n，判断是否为素数,两个数相乘,矩阵的维度或者元素的个数,两个矩阵相乘,关键字比较,列表节点数目，例如 n,在长度为n的列表中按关键字查找,2023/3/30,19,对时间效率的实证分析,选择特别的或者典型的输入统计实

6、际运行时间(e.g.,milliseconds)统计基本操作执行的次数对统计数据进行分析,2023/3/30,20,最好、最坏、平均情况,很多算法的效率都取决于输入的组织最坏情况:Cworst(n)对于规模为n的输入，最大的消耗最好情况:Cbest(n)对于规模为n的输入，最小的消耗平均情况:Cavg(n)对于规模为n的输入，“平均”的消耗基本操作执行的次数体现在典型输入中不是最好最坏情况的平均将规模n的实例划分为几种类型，同种实例所需要的基本操作执行次数一样，然后我们得到或者假设各种输入的概率分布，以推导出我们的平均次数,2023/3/30,21,例：顺序查找,最坏情况：n最好情况：1平均情

7、况：(1+n)p/2+n(1-p),/在一个指定的数组中顺序查找指定元素/输入：A0.n-1,k/输出：指定查找元素在数组中的下标，没有返回-1,2023/3/30,22,思考,对于下面每种算法，1.指出输入规模的合理度量，2.它的基本操作，对相同规模的输入来说，3.基本操作的执行次数是否有所不同？a、计算n个数的和 b、计算n！c、找出包含n个数字的列表的最大元素 c、两个十进制正整数相乘的笔算算法 d、欧几里得法求公约数,2023/3/30,23,选择手套一个抽屉里有22只手套，5双红色的，4双黄色的，2双绿色的，黑暗中挑选，最优情况下就最少选几只能找到一对匹配的手套？最坏情况下呢？丢失的

8、袜子 假设洗了5双不同的袜子后，发现两只找不到了，当然希望留下数量最多的完整的袜子，在最好的情况下，你会留下4双袜子，最坏情况下只有3双，假设10只袜子每只丢失的概率相同，请找出最好与最坏的发生概率，平均情况下能指望有几双？,2023/3/30,24,增长次数,最重要的:考虑n时，效率的乘积增长速度例如：当计算机的速度增加两倍时，算法运行的速度会有多快当在两倍的输入规模下解决某问题时，时间会增加多少,T(n)copC(n),2023/3/30,25,n时的重要增长值,比较一下logn与n2的区别,2023/3/30,26,分析框架概要,算法的效率用输入规模函数进行度量基本操作的执行次数输入规模

9、相同情况下，有时候需要区分最好、最差和平均效率算法输入规模趋向无穷大时，它的运行时间函数的增长次数,2023/3/30,27,2.2增长率渐进表示,我们关心的是算法的基本操作次数的增长次数，并把它作为算法效率分析的主要指标，为了进行比较归类，引入下列3个符号：O(g(n):增长不会超过g(n)的一类函数f(n)(g(n):增长率与g(n)相同的一类函数f(n)(g(n):增长至少与g(n)相同的一类函数f(n),2023/3/30,28,Big-oh,成立的条件是对于足够大的nn0，存在大于0的常数c，使得以上图形满足,后面符号的两个条件相同,P41例,2023/3/30,29,Big-ome

10、ga,2023/3/30,30,Big-theta,2023/3/30,31,证明,2023/3/30,32,渐进增长的相关属性,f(n)O(f(n)f(n)O(g(n)if g(n)(f(n)If f(n)O(g(n)and g(n)O(h(n),then f(n)O(h(n)If f1(n)O(g1(n)and f2(n)O(g2(n),then f1(n)+f2(n)O(maxg1(n),g2(n),2023/3/30,33,使用极限比较增长次数,lim T(n)/g(n)=,0 order of growth of T(n)order of growth of g(n),c 0 ord

11、er of growth of T(n)=order of growth of g(n),order of growth of T(n)order of growth of g(n),Examples:10n vs.n2 n(n+1)/2 vs.n2,n,2023/3/30,34,基本的渐进效率分类：,2023/3/30,35,P46 1选择合适的符号来指出顺序查找算法时间效率类型最优最差平均情况作业 2、5,2023/3/30,36,2.3非递归算法时间效率分析过程,使用变量n来描述输入规模定义算法的基本操作在输入规模为n的情况下，区分最坏、平均和最好情况对基本操作执行的次数求和使用相关公式

12、和规则对和进行化简,2023/3/30,37,示例1：求最大元素,2023/3/30,38,示例2：元素的唯一性问题,2023/3/30,39,示例3：矩阵的乘法,2023/3/30,40,示例4.十进制数转化成二进制数后的位数,2023/3/30,41,练习 p51 1 e、g 其余作业,2023/3/30,42,2.4递归算法的时间效率分析过程,递归算法：函数调用自身的情况称为递归。递归的条件：子问题与原问题是同样的问题，且更为简单不能无限制调用，必须有出口条件,2023/3/30,43,确定一个变量来描述输入规模确定算法的基本操作对于相同规模的不同输入，在执行时是否有不同的基本操作次数，

13、如果有，那么最坏、平均和最好情况应该分别考虑建立与适当初始条件的递归联系，表示基本操作的执行次数使用反向迭代方法和初始条件解出递归式，至少要建立递归解的增长率,2023/3/30,44,N!,定义:n!=1 2(n-1)n for n 1 and 0!=1递归的定义 n!:F(n)=F(n-1)n for n1 and F(0)=1问题规模？基本操作？运算时间的递推式？初始条件？,2023/3/30,45,实例2：汉诺塔问题实例3：十进制正整数在二进制表示中的数字个数 递归方法 练习p58页（1）a b、c、d、e做作业P64页 习题2.5（4）,2023/3/30,46,本章结束，返回总目录

14、,Chapter3 分治法 Divid and Conquer,2023/3/30,48,分治法,分治法通用分治递推式分治法实例,返回总目录,2023/3/30,49,分治法,通用算法设计技术将问题的实例划分为同一个问题的几个较小实例对这些较小的实例求解合并这些较小问题的解，已得到原始问题的解分治算法很适合用递归来解决,2023/3/30,50,分治法,子问题2的规模是n/2,子问题1的规模是n/2,子问题1的解,原始问题的解,子问题2的解,原始问题规模是n,2023/3/30,51,通用分治递推式,T(n)=aT(n/b)+f(n)其中，f(n)(nd),d 0主定理:当 a bd,T(n)

15、(nlog b a)注意：对 O 和符号来说类似的结论也是成立的。例如:T(n)=4T(n/2)+n T(n)?T(n)=4T(n/2)+n2 T(n)?T(n)=4T(n/2)+n3 T(n)?,2023/3/30,52,分治法实例,归并排序和快速排序二叉树遍历二分查找大整数乘法Strassen矩阵乘法凸包问题,2023/3/30,53,归并排序,将数组A0.n-1 分成两个相等数组，并分别用数组B和数组C备份分别对B,C进行排序按照如下方法合并B,C到数组A：重复如下步骤，直到数组中没有元素为止：比较两个待合并数组的第一个元素将较小的元素添加到一个新创建的数组中，被复制数组中下标后移。在未

16、处理完的数组中，剩下的元素被复制到新创建数组的尾部。,2023/3/30,54,8 3 2 9 7 1 5 4,8 3 2 9,7 1 5 4,8 3,2 9,7 1,5 4,8,3,2,9,7,1,5,4,3 8,2 9,1 7,4 5,2 3 8 9,1 4 5 7,1 2 3 4 5 7 8 9,2023/3/30,55,两个列表归并成一个有序列表的算法,2023/3/30,56,归并排序算法,2023/3/30,57,归并排序效率分析,所有实例都有同一个效率:(n log n)最坏情况下的键值比较次数十分接近于任何基于比较的排序算法在理论上所能达到的最少次数.当n=2k时 c(n)=n

17、log2n-n+1空间需求:(n)可以不用递归(自底而上）,2023/3/30,58,快速排序,选择一个中轴 元素，我们这里选择第一个元素对数组进行排序，使得小于或等于中轴的元素位于子数组的第一部分，剩下的元素都大于或等于中轴元素的值。将中轴子与第一个子数组中的元素进行交换-此时，中轴在最后的位置对两个子数组进行递归排序,2023/3/30,59,0 1 2 3 4 5 6 7,5 3 1 4 8 2 9 7,5 3 1 9 8 2 4 7,3 1 9 8 2 4 7,5 3 1 4 8 2 9 7,5 3 1 4 2 8 9 7,5 3 1 4 2 8 9 7,2 3 1 4 5 8 9 7

18、,i,j,l=0,r=7,5,i,j,i,j,i,j,i,j,j,i,S=4,2 3 1 4,i,j,l=0,r=3,2 3 1 4,i,j,2 1 3 4,i,j,2 1 3 4,i,j,1 2 3 4,S=1,1,l=5,r=7,3 4,i,j,3 4,i,j,4,l=0,r=0,l=2,r=3,S=2,l=2,r=1,l=3,r=3,8 9 7,i,j,8 7 9,i,j,8 7 9,i,j,7 8 9,l=5,r=5,7,9,l=7,r=7,S=6,快速排序操作的一个例子。(a)数组的变化，其中中轴用粗体表示；(b)快速排序的递归调用树，调用的输入值是子数组的边界l和r，以及分区的分裂

19、点位置s,(a),(b),2023/3/30,60,快排效率分析,最好情况:从中间拆分(n log n)最坏情况:已经是排好序的数组(n2)平均情况:无序数组(n log n)对该算法的改进:更好的选择中轴:三平均分区法 当子数组足够小时改用更简单的排序方法递归消去法可将该算法的运行时间削减20%-25%考虑用该种方法来对大文件（n10000)来进行内部排序,2023/3/30,61,二分查找,对于有序数组的查找的一种高速算法 K vsA0.Am.An-1如果 K=Am,停止查找;否则当K Am 时，在 Am+1.n-1中查找。,2023/3/30,62,二分查找效率分析,时间效率最坏情况下递

20、推式：Cw(n)=1+Cw(n/2),Cw(1)=1 经过调整后：Cw(n)=log2(n+1)这是非常快的，例如：Cw(106)=20最适合用于查找已排序数组限制：必须是一个排序数组（不是链接数组）折半查找并不是分治法典型的特例,2023/3/30,63,二叉树遍历,二叉树时分治法的较好的结构例1:遍历(前序,中序,后序)Algorithm Inorder(T)if T Inorder(Tleft)print(root of T)Inorder(Tright)效率:(n),2023/3/30,64,二叉树遍历,例 2:计算二叉树的高度,h(T)=maxh(TL),h(TR)+1 if T 并

21、且 h()=-1效率:(n),2023/3/30,65,大整数乘法,两位整数相乘可以用数组表示如：,a1 a2 anb1 b2 bn,A=12345678901357986429,B=87654321284820912836,(d10)d11d12 d1n,(d20)d21d22 d2n,(dn0)dn1dn2 dnn,效率：O(n2),2023/3/30,66,大整数乘法,两位数A=2135 和B=4014可以这样表示：将每个数字从中间一分为二,它们的积可以用这个公式计算：,A B=A1 B110n+(A1 B2+A2 B1)10n/2+A2 B2,A=(21102+35),B=(40 10

22、2+14),A B=(21 102+35)(40 102+14)=21 40 104+(21 14+35 40)102+35 14,效率：M(n)=4M(n/2),M(1)=1 M(n)=n2,2023/3/30,67,大整数乘法,(A1 B2+A2 B1)=(A1+A2)(B1+B2)-A1 B1-A2 B2,A B=A1 B110n+(A1 B2+A2 B1)10n/2+A2 B2,可以这样做减少乘法：,A B=A1 B1+(A1 B2+A2 B1)+A2 B2,因为上述中只有三个乘法所以乘法次数M(n)的递推式是：,当n1时 M(n)=3M(n/2),M(1)=1,当n=2k时 M(2k

23、)=3M(2 k-1)=.=3k,因为：k=log2n M(n)=nlog23=n1.585,2023/3/30,68,大整数乘法,A=21 35 B=40 14,A1,A2,B1,B2,A B=21*35+（21*14+35*40）+35*14,（21*14+35*40）=（21+35）*（40+24）-21*35-35*14,例如：计算 2135 4014,2023/3/30,69,Strassen矩阵乘法,A和B的乘积矩阵C中的元素Ci,j定义为:,若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素Cij，需要做n次乘法和n-1次加法。因此，算出矩阵C的 个元素所需的计算时间为O(

24、n3),传统方法：O(n3),2023/3/30,70,Strassen矩阵乘法,使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：,传统方法：O(n3)分治法:,由此可得：,由此可见，单纯采用分治法，没有改进,2023/3/30,71,Strassen矩阵乘法,为了降低时间复杂度，必须减少乘法的次数。,2023/3/30,72,复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进,2023/3/30,73,Strassen矩阵乘法,传统方法：O(n3)分治法:O(n2.81)更快的方法?,Hopcroft和Kerr已经证明(

25、1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)的算法？目前为止还没有结果。,2023/3/30,74,凸包问题（相关定义p84）,什么是凸集合？对于平面的一个点集合（有限或无限），如果以集合中任意两点p和q为端点的线段都属于该集合，则称集合为凸的。定义：凸包：一个点集合s的凸包是包含s的最小凸集合。定理任意包含n2个点（不共线的点）的集合s的凸

26、包是以s中的某些点为顶点的多边形（如果所有的的店都位于一条直线上，多边形退化为一条线段，但它的2个端点让人包含在s中）,2023/3/30,75,假设点按照x轴排序找出最左和 最右的极点(leftmost and rightmost)递归的求凸包的上包:发现点 Pmax 是离直线 P1P2直线最远的点计算在直线 P1Pmax左侧的上包计算在直线 PmaxP2左侧的上包递归的计算下包,2023/3/30,76,p1,p2,凸包问题,1、最左边的点p1和最右边的p2一定是该集合凸包顶点。,2023/3/30,77,p1,p2,凸包问题,2、找到上包的顶点，它是距离直线最远的点，如果用两条连接线的话

27、，这个确定了最大的三角形pmaxp1p2。,pmax,2023/3/30,78,p1,p2,凸包问题,p1max,3、找出距离p1pmax左边最远的点p3。如此进行下去，直到对应的包左边没有点,p3,2023/3/30,79,p1,p2,凸包问题,p1max,p2max,4、找出PmaxP2左边最远的点p4。，按照改方法进行，直到左边没有点,p4,2023/3/30,80,p1,p2,凸包问题,p1max,p2max,连接所得到的这些点,2023/3/30,81,p1,p2,凸包问题,p1max,p2max,利用上述求上包的方法求出下包。,2023/3/30,82,如何判断离线段p1p2最远的

28、点？假设p3为任意点X1 y1 1X2 y2 1X3 y3 1,该行列式的绝对值表示以这3点构成的三角形面积，值为正，表示该点位于直线先左侧,2023/3/30,83,本章结束，返回总目录,Chapter 4 减治法,Decrease-and-Conquer,2023/3/30,85,减治法,减治法减治法的类型减治法与其它方法的区别,返回总目录,2023/3/30,86,减治法,基本思路：将原问题的实例转化为规模较小的实例对规模较小的实例的求解将较小的实例的解扩展到原实例能够使用自顶向下或者是自底向上经常被称为归纳法或者是增量法,2023/3/30,87,减治法的类型,减去一个常量（一般是）插

29、入排序 图形遍历算法（深度优先查找和广度优先查找）拓扑排序减去一个常量因子（一般是一半）折半查找和二分法矩阵的幂运算俄式乘法减可变规模欧几里得问题部分选择,2023/3/30,88,减去常量,在这种减治法中，每次减去一个常量因子1。例如：插入排序 图形遍历算法（深度优先查找和广度优先查找）拓扑排序,2023/3/30,89,插入排序,对数组A0.n-1，数组A0.n-2已经排好序，然后在数组中A0.n-2中找一个合适的位置将An-1插入经常使用自底向上（非递归）例如:对 6,4,1,8,5进行排序 6|4 1 8 5 4 6|1 8 5 1 4 6|8 5 1 4 6 8|5 1 4 5 6

30、8,2023/3/30,90,插入排序,2023/3/30,91,插入排序,89,45,68,90,29,34,17,45,比较45与89的大小,2023/3/30,92,插入排序,89,45,68,90,29,34,17,45,4589，插入到89前面,2023/3/30,93,插入排序,89,68,90,29,34,17,45,比较68与前面的数的大小,2023/3/30,94,插入排序,89,68,90,29,34,17,45,68,6889,2023/3/30,95,插入排序,89,68,90,29,34,17,45,68,89后移一个位置,2023/3/30,96,插入排序,89,6

31、8,90,29,34,17,45,68,比较45与68的大小,2023/3/30,97,插入排序,89,68,90,29,34,17,45,68,将68插入到45后面,2023/3/30,98,插入排序,89,90,29,34,17,45,68,比较90与前面的数的大小,2023/3/30,99,插入排序,89,90,29,34,17,45,68,8990,2023/3/30,100,插入排序,89,90,29,34,17,45,68,将90插入到89后面的位置,2023/3/30,101,插入排序,89,90,29,34,17,45,68,比较29与前面的数的大小,2023/3/30,102

32、,插入排序,2023/3/30,103,插入排序,34,45,68,89,90,17,29,排好序后的数组,2023/3/30,104,插入排序效率分析,时间效率Cworst(n)=n(n-1)/2(n2)Cavg(n)n2/4(n2)Cbest(n)=n-1(n)空间效率稳定的最好排序方法 二分法插入排序,2023/3/30,105,图遍历,许多问题要求自动系统地遍历图所有的节点：Depth-first search(DFS)深度优先查找Breadth-first search(BFS)广度优先查找,2023/3/30,106,深度优先遍历(DFS),从任意顶点开始访问图的顶点，然后把改顶点

33、标记已访问，在每次迭代的的时候，紧接着访问与当前顶点邻接的未访问顶点，直到遇到一个死端。用一个堆栈第一次访问时入栈当该顶点变成一个死端时出栈,2023/3/30,107,深度优先遍历(DFS),2023/3/30,108,DFS,DFS traversal stack:,DFS tree:,a,a入栈,2023/3/30,109,DFS traversal stack:,DFS tree:,a,b,b入栈,DFS,2023/3/30,110,DFS traversal stack:,DFS tree:,a,b,f,f入栈,DFS,2023/3/30,111,DFS traversal stac

34、k:,DFS tree:,a,b,f,e,e入栈,DFS,2023/3/30,112,DFS traversal stack:,DFS tree:,a,b,f,e,e出栈,DFS,2023/3/30,113,DFS traversal stack:,DFS tree:,a,b,f,e,f出栈,DFS,2023/3/30,114,DFS traversal stack:,DFS tree:,a,b,f,e,b出栈,DFS,2023/3/30,115,DFS traversal stack:,DFS tree:,a,b,f,e,b,g,g入栈,DFS,2023/3/30,116,DFS trave

35、rsal stack:,DFS tree:,a,b,f,e,b,g,c,c入栈,DFS,2023/3/30,117,DFS traversal stack:,DFS tree:,a,b,f,e,b,g,c,d,d入栈,DFS,2023/3/30,118,DFS traversal stack:,DFS tree:,a,b,f,e,g,c,d,h,h入栈,DFS,2023/3/30,119,DFS traversal stack:,DFS tree:,a,b,f,e,g,c,d,h,h出栈,DFS,2023/3/30,120,DFS traversal stack:,DFS tree:,a,b,

36、f,e,g,c,d,h,d出栈,DFS,2023/3/30,121,DFS traversal stack:,DFS tree:,a,b,f,e,g,c,d,h,c出栈,DFS,2023/3/30,122,DFS traversal stack:,DFS tree:,a,b,f,e,g,c,d,h,g出栈,DFS,2023/3/30,123,DFS,DFS traversal stack:,DFS tree:,a,b,f,e,g,c,d,h,b出栈,2023/3/30,124,DFS,DFS traversal stack:,DFS tree:,a,b,f,e,g,c,d,h,a出栈,2023

37、/3/30,125,DFS,DFS traversal stack:,DFS tree:,a,b,f,e,g,c,d,h,DFS完成,2023/3/30,126,深度优先遍历(DFS),DFS 能够在两种表示方式下实现：(V2)邻接矩阵(|V|+|E|)邻接表产生两种节点序列：第一次访问的顶点（入栈）的次序顶点成为死端（出栈）的次序应用：检查图的连通性和找出图的连通分量量 检查图的无环性查找关节点和重连通分量搜索状态空间的问题解决方案（人工智能）,2023/3/30,127,广度优先遍历(BFS),访问所有和初始顶点邻接的顶点使用队列而不是堆栈类似于层次遍历,2023/3/30,128,广度优

38、先遍历(BFS),2023/3/30,129,BFS,BFS traversal stack:,BFS tree:,a,a入队,a,2023/3/30,130,BFS,BFS traversal stack:,BFS tree:,a,b,f,e,a出队，b、e、f入队,a,2023/3/30,131,BFS,BFS traversal stack:,BFS tree:,a,g,b出队，g入队,b,f,e,2023/3/30,132,BFS,BFS traversal stack:,BFS tree:,a,e出队,g,f,e,2023/3/30,133,BFS,BFS traversal sta

39、ck:,BFS tree:,a,f出队,g,f,2023/3/30,134,BFS,BFS traversal stack:,BFS tree:,a,c,h,g出队，c、h入队,g,2023/3/30,135,BFS,BFS traversal stack:,BFS tree:,a,d,c出队，d入队,c,h,2023/3/30,136,BFS,BFS traversal stack:,BFS tree:,a,d,h出队,h,2023/3/30,137,BFS,BFS traversal stack:,BFS tree:,a,d出队，BFS完成,d,2023/3/30,138,广度优先遍历(B

40、FS),BFS 和 DFS具有相同的效率，也并且能够使用其他的图来表示：邻接矩阵:(V2)邻接表:(|V|+|E|)只产生一种顶点序列(入队和出队的次序时一样的)应用:和 DFS一样,但是BFS还能够用来查找从一个顶点到其他所有顶点间边的数量最少的路径。,2023/3/30,139,无环有向图和拓扑排序,无环有向图:有向图没有回边,许多牵扯到先决条件的问题都可以通过建立一个图形模型来解决(施工项目,文档版本控制)对于图中的每一条边来说，边的起始顶点总是排在 边的顶点结束之前.为了使拓扑排序成为可能，图必须是一个无环有向图,2023/3/30,140,拓扑排序举例,将下列食物链按顺序排列,fis

41、h,human,shrimp,sheep,wheat,plankton,tiger,2023/3/30,141,基于DFS的算法,基于DFS算法的拓扑排序执行一次DFS遍历，并记住顶点变成死端（退出遍历栈）的顺序将该次序反过来得到拓扑排序的一个解遇到回边?不是无环有向图!,a,b,e,f,c,d,g,h,2023/3/30,142,源删除算法,源删除算法 不断的做一件事，再余下的有向图中求一个源，他是一个没有输入边的顶点，然后把它和所有从他出发的边都删除（如果有多个源，任意删掉一个，如果不存在，算法就停止）。,a,b,e,f,c,d,g,h,2023/3/30,143,拓扑排序,fish,20

42、23/3/30,144,拓扑排序,fish,human,shrimp,sheep,wheat,tiger,2023/3/30,145,拓扑排序,fish,human,shrimp,sheep,tiger,2023/3/30,146,拓扑排序,fish,human,sheep,tiger,2023/3/30,147,拓扑排序,human,sheep,tiger,2023/3/30,148,拓扑排序,human,tiger,2023/3/30,149,拓扑排序,tiger,2023/3/30,150,拓扑排序,求得的解是 plankton，wheat，shrimp，fish，sheep，human

43、，tiger,2023/3/30,151,生成组合对象的算法,1.生成排列对于n个元素，如何生成其排列呢？可以想像已经生成了n-1个元素的排列，我们可以将第n个元素插入到n-1个元素所产生的全部排列中去开始时将n从右往左插入到前面n-1生成的排列中去,然后每处理一个新的排列时，再调换方向。,开始：1,开从右往左将2插入：12 21,开从右往左将3插入：123 132 312,开从左往右将3插入：321 231 213,2023/3/30,152,用该方法生成排列有什么优点呢？满足最小变化的要求,2023/3/30,153,Johnson-Trotter算法生成排列,该算法是一种有效的生成排列的

44、算法将每个元素赋予一个方向，如果箭头指向一个相邻的较小元素，我们说它在这个箭头标记的排列中是移动的元素。例如,3 2 4 1,2023/3/30,154,应用该算法生成3个元素的所有排列过程如下将所有元素初始化为1 2 3，以后重复执行2-5步骤如果存在移动元素，则找到最大的移动元素k把k和它所指向的相邻元素互换跳转所有大于k的元素的方向将排列加到列表中,2023/3/30,155,生成字典序排列的算法,Johnson-Trotter算法生成的是最小变化的序该算法生成的不是字典顺序的序列字典序列 123，132，213，231，312，312如何生成字典序列呢？从右往左寻找到第一对升序序的数字

45、ai,ai+1，然后在ai+1到an中找到最小的大于ai的数字，将其与ai交换，然后将ai与后面的其他数字进行升序排列 四个数的字典序列 1234 1243 1324 1342,2023/3/30,156,生成子集,利用减1思想，集合分成2个部分，一个部分包含an，一个部分是其他n-1个元素的所有集合，通过把ai+1加入到每一个子集中来获得全部n个元素的子集利用n个元素的2n个子集和长度为n的所有2n个比特串之间的对象关系，二进制比特串的第i位为1表示n个元素中的第i个元素在该集合中，为o表示不在该集合中，如3位的比特串010，表示该子集中只有第2个元素。如3个元素的a1a2a3所有子集000

46、 001 010 011 100 101 110 111 空集 a3 a2 a2a3 a1 a1a3 a1a2 a1a2a3,2023/3/30,157,格雷码,格雷码是一个数列集合，相邻两数间只有一个位元改变，为无权数码，且格雷码的顺序不是唯一的。某些情况，例如从十进制的3转换成4时二进制码的每一位都要变，使数字电路产生很大的尖峰电流脉冲。而格雷码则没有这一缺点，它是一种数字排序系统，其中的所有相邻整数在它们的数字表示中只有一个数字不同。它在任意两个相邻的数之间转换时，只有一个数位发生变化。它大大地减少了由一个状态到下一个状态时逻辑的混淆。,2023/3/30,158,如何生成格雷码方法1：

47、以二进制为0值的格雷码为第零项，第一项改变最右边的位元，第二项改变右起第一个为1的位元的左边位元，第三、四项方法同第一、二项，如此反覆，即可排列出n个位元的格雷码。方法2：先生成n-1的二进制格雷码序列a，然后复制一份该代码序列b，将0加在a序列的最左边，将1加在序列b的最左边，然后将修改后的b序列反序连接在修改后a序列后,2023/3/30,159,减常量因子,在这种减治法中，每次减去一个相同的常量因子。例如：假币问题俄式乘法,2023/3/30,160,假币问题（简单版本）,在n枚外观相同的硬币中寻找一枚假币.有一架没有刻度的天平但是能够显示两边的重量是否相等,如果相等，天平就不会倾斜，如

48、果不相等，重的一边就会倾斜 设计一个有效的算法来找出这枚假币。假设这枚假币比真币要轻。,2023/3/30,161,俄式乘法,问题:两个正整数相乘该问题能够使用下面的公式进行减半的运算:,对于每一个 n:,如果 n是奇数:,n*m=*2m,n*m=*2m+m if n 1 and m if n=1,n 2,n 1 2,2023/3/30,162,俄式乘法,Compute 20*26 n m 20 26 10 52 5 104 104 2 208+1 416 416,520,Note:把所有n列中包含基数的m列元素进行相加,2023/3/30,163,约瑟夫斯问题,问题的提出,2023/3/30

49、,164,减可变因子,在这种减治法当中，每次迭代都减小规模不同的 因子。例如:欧几里得算法查找问题计算中值和选择问题,2023/3/30,165,欧几里得求最大公约数算法,欧几里得算法重复使用公式：gcd(m,n)=gcd(n,m mod n)例如:gcd(80,44)=gcd(44,36)=gcd(36,8)=gcd(8,4)余数为0结束，取次数被除数作为最大公约数T(n)O(log n),2023/3/30,166,查找问题,在n个数中查找第k小的元素k=1 or k=n中值:k=n/2 例如:4,1,10,9,7,12,8,2,15 中值=?中值是数理统计中用来求平均值的一个很好的方法事

50、实上，它比其他类似合并排序的算法要优秀很多。,2023/3/30,167,如果有一个数组an，现要求出其中第k小元素,A:以数组第一个元素为标准，利用快速排序得到此数值在数组中的位置是第j个,Kj-1,K=j-1,K=j,继续步骤A,aj-1即为所求,求第K小元素,2023/3/30,168,4,1,10,9,7,12,8,2,15,K=9/2=5,中值问题,2023/3/30,169,4,1,10,9,7,12,8,2,15,2,1,4,9,7,12,8,10,15,K=9/2=5,中值问题,2023/3/30,170,4,1,10,9,7,12,8,2,15,2,1,4,9,7,12,8,