算法设计与分析5ppt课件

算法设计与分析基础IntroductiontotheDesignandAnalysisofAlgorithms第五章减治法DecreaseandConquer,1,第5章减治法,算法策略插入排序深度优先搜索DFS广度优先搜索BFS拓扑排序生成组合对象减常因子法减可变规模法,概念与算法策略,算法策略减治法：利用给定规模与较小规模问题解之间的关系求解问题的方法。实现自顶向下：规模减小（递归）自底向上：规模增大（非递归）减常量法：常量通常为1（减1法）减常因子法：常因子通常为2（减半法）减可变规模法：每次减去的规模不同,插入排序,插入排序对n个元素A0,.,n-1排序（非降序为例）减一策略分析过程自顶向下（规模减小）减去一个元素An-1,对A0,.,n-2排序（非降序）原问题的解=减一规模的解+An-1对数组递归减一，分解到仅一个元素为止；再合并得到原问题解。插入算法有三种方法插入一个元素，左右扫描称直接插入法左扫描：从左向右扫描有序子数组，遇到第一个An-1元素为止，在该元素前插入An-1.若未找到，则插在最后。右扫描：从右向左扫描有序子数组，遇到第一个An-1元素为止，在该元素后插入An-1.若未找到，则插在最前。常用：右扫描法。问：理由是什么？理由：子数组若有等值元素，右扫描插入时需移动的元素个数少。它插在等值元素后，前面等值元素都不用移动位置,插入排序算法与算例,折半插入法组合利用减一法和减半法子数组有序，用折半查找为插入元素在其中找到一个合适的位置。算法伪码基于递归思想设计，但非递归实现（从底向上）,下划线为待插元素,思考：为什么是右扫描插入V？,插入排序效率分析,插入排序效率分析输入规模：元素个数n基本操作：比较操作AjV效率类别：输入A为升序，每次插入只需比较1次最佳效率输入A为降序最差效率，其他平均效率最佳效率：要插入n-1个元素，共需比较n-1次（线性效率）也可据伪码计算：最差效率对每个元素如第i个元素插入，从j=i-1比较到j=0，共i次比较，即插入元素Ai要与前面的全部元素都比较一次。平均效率：比最差效率快2倍。若遇到基本有序数组，比选择排序和冒泡排序的性能略优。,图的遍历,深度优先搜索DFS(Depth-FirstSearch)随后两节讨论图的一些常用算法，可看作是减一技术的应用。图是一种令人感兴趣的、有着广泛应用的数据结构。许多实际问题的计算模型图结构1.领土问题2.交通网络3.通信网络4.棋局、迷宫图的遍历从起点出发访问所有顶点。可能遇到的问题：1.非连通图：不能访问到某些顶点。2.存在回路：要防止陷入死循环。为每个顶点设置访问标志(mark).开始时：所有顶点的访问标志置零遍历时：已访问顶点的标志被标记，以后不访问它，防止回路循环结束时：检查顶点标志。若有未标记顶点，则重选起点，继续遍历,深度优先搜索DFS,许多图的算法要求对图进行遍历或周游(graphtraversal).主要两种：DFS(Depth-FirstSearch),BFS(Breadth-FirstSearch).DFS深度优先搜索过程简述从任一顶点（问题确定）出发，沿某一路径搜索该路径上所有未访问顶点，到达死端（所有相邻顶点都已访问过），沿原路后退一条边，从那里继续访问未访问过的顶点（回溯）；当回溯到开始顶点，并且它成为死端时，DFS过程结束。顶点选择策略：搜索过程中，若某顶点有多个邻接顶点，可以按顶点编号（或其他策略如优先值大小选择顶点）进行访问，下页图示。DFS搜索的非递归实现栈过程1.当前顶点入栈2.将栈顶顶点的下一个未访问邻接顶点入栈若栈顶顶点无未访问邻接顶点，该顶点退栈（回溯）3.重复2，直到栈空为止，DFS过程结束DFS算法构造出一棵DFS树（或森林）,DFS算法过程图示,DFS算法过程图示（以树为例）,根据访问顺序，用连续整数标记各个顶点，如图。红色箭头表示回溯过程。,DFS算法的栈过程图示,DFS栈过程图示,顶点选择策略未访问邻接顶点有多个，按顶点编号的字母序访问。栈空时，DFS遍历结束。DFS可产生进栈、退栈两种顶点线性序列，可按实际情况的需要选用。,顶点进栈的线性序列：ACBFDE,顶点退栈的线性序列：DEFBCA,DFS树与森林,DFS树与森林DFS可构造出一棵深度优先搜索树（可转换为有根树）或森林树边：图中当前顶点到未访问儿子顶点的边，如CB,FE回边：图中当前顶点到已访问祖父顶点的边，如EA,DCDFS树：不含回边的树（无环图）（只有树边）DFS森林：包含回边的图（有环图）（含有回边）右图实际上不是森林（不连通的多棵树），而是一种类森林的表示。若将其转换为DFS树，不同的顶点选择策略如选择C顶点的下一个邻接顶点为D或者B，可以得到不同的DFS树，这些树组成森林。,A,E,B,C,D,F,DFS树,A,E,B,C,D,F,DFS森林,DFS递归算法,DFS递归版,DFS非递归算法,DFS非递归版,DFS的时间效率,DFS时间效率分析输入规模：顶点数n基本操作：顶点访问判断Markw=0，简称：访问顶点效率类别：对于给定图，无最佳、最差、平均效率增长函数基本操作数与顶点数n的关系：T(n)=?它与给定图的表示法（邻接矩阵、邻接链表）有关一、图的邻接矩阵表示访问下一个邻接顶点，要检查余下所有顶点，判断是不是邻接顶点。起点开始，从余下n-1个顶点选择一个；再访问下一顶点，从n-2个顶点中选一个；如此继续，每次余下的顶点数序列：n-1,n-2,.,1访问的顶点总数（基本操作数）：T(n)=(n-1)+(n-2)+.+1=n(n-1)/2(n2)思考：这与给定图G=是稠密图或稀疏图有关吗？无关：当前顶点并不知道下一个相邻顶点，需要在剩余顶点中寻找，与连接形式无关。,图的邻接链表表示,DFS的时间效率：邻接链表表示图,二、图的邻接链表表示：下一个邻接顶点在链表中是确定的,访问顶点数与n的关系：1.每个表头顶点需要访问，以找到该顶点开始的邻接顶点链2.每个链表的剩余顶点需要访问剩余顶点数等于该链表的边数访问顶点总数等于上述两项之和：T(n)(|V|+|E|)|V|=n,|E|0,n(n-1)/2|E|min=0：一个顶点|E|max=n(n-1)/2：完全图结论：稠密图邻接矩阵表示较好无链表的额外开销稀疏图邻接链表表示较好,DFS简单应用,DFS简单应用DFS检查图的连通性从任意顶点开始DFS遍历，当遍历算法停止以后，检查是否全部顶点都已访问过。若都访问过，此图是连通的。否则，此图不连通。因为遍历算法不能到达的顶点，说明它与图的其他顶点没有路径可通。DFS检查图的无环性如果从某个顶点到它的祖先顶点之间有一条回边，则该图存在回路，以此检查给定图的环。若不存在这样的回边，则为无环。DFS其他应用例如：求图的关节点（从图中移走某个顶点及其与它相连的边以后，图被分为若干个不相交的部分，该顶点称为关节点）等更复杂应用。,BFS算法过程图示（以树为例）,BFS算法过程图示（以树为例）,根据访问顺序，用连续整数标记各个顶点，如图。,BFS搜索的队列过程图示,BFS队列过程图示,顶点出、入队线性序列ACEBDF,BFS树或森林森林解释见DFS,BFS非递归算法,BFS非递归算法,BFS相关讨论,BFS相关讨论时间效率：同DFS效率一样。前面讨论DFS的效率时，仅与图的存储结构（邻接矩阵、邻接链表）有关，与DFS或BFS无关应用1：检查图的连通性和无环性，本质上与DFS一样应用2：求给定两个顶点的最短路径（边数最少，非带权图）从两个给定的顶点之一开始BFS，当访问到另一个顶点，BFS结束从BFS算法过程看，其正确性不言而喻，但数学上的证明并不简单说明：这样的最短路径可能不只一条（考虑去掉BG边的图）,BFS树的一部分，确定了从A到G的最短路径（边数最少）,拓扑排序,拓扑排序(TopologicalSort)概述问题提出假设要安排一系列任务，如教学计划中的安排各门课程的学习顺序，项目中各子课题的研究顺序，建筑项目，等等。每个任务只有当前提条件具备时，才能去完成这个任务。举例如下：只有当学完某课程的全部前修课程后，才能安排该课程的教学拓扑排序找到在满足前提条件情况下，各个任务如何安排的一个线性序列计算模型图（顶点：一个任务，边：该任务的前提条件）1.有向图：任务之间有先后关系边有方向2.无环图：若有环，回路中就会存在彼此矛盾的条件。（想一想）不可能在不违反前提条件情况下，为这些任务安排一个合理的顺序，问题无解（存在矛盾条件）综合1、2，若拓扑排序问题有解，必须是有向无环图,拓扑排序：有向无环图,有向无环图无向图：仅有2种类型的边树边、回边有向图：可有4种类型的边1.树边：ABBCDE2.回边：BA（无回边:无环图）3.前向边（祖孙边）当前顶点到孙子顶点的边AC4.交叉边（横跨边）上述3种类型以外的边DC,有向无环图,去掉BA边则为有向无环图,拓扑排序算法：DFS法例1,拓扑排序算法拓扑排序DFS算法【例1】5门课程的安排，问题模型如图,C有两门前修课AB，E有两门前修课CD,必须先安排前修课程。因此，正确次序是：先安排AB，然后安排C；接下来安排D，最后安排E.即正确的线性序列序列为：ABCDE或BACDE（非唯一解）任选一个源顶点开始DFS过程：源顶点：没有入边，即无前提条件的边我们选A开始DFSA到E搜索完后，尚有未访问顶点B，将B入栈，从B重新开始DFS.进栈序列：ACDEB进栈逆序：BEDCA出栈序列：EDCAB出栈逆序：BACDE,问题模型图,拓扑排序算法：DFS例2,DFS解拓扑排序【例2】7个任务的安排,2,1,6,3,7,5,4,问题模型图,退栈线性序列：7546231（或7543621）退栈线性逆序：1326457（或1263457）解不是唯一的，与顶点选择策略即路径选择有关,拓扑排序的源删除算法,拓扑排序的源删除算法（减一法）每次减去一个源顶点若算法结束（无源顶点），尚有未访问顶点时，问题无解！存在矛盾条件顶点的删除顺序即拓扑排序的一个解（不唯一），本例ABCDE源删除算法与数据结构1.找出全部源顶点并入队。若无源顶点，算法停止。有未访问顶点？Yes无解；No输出解（记录的顶点序列）2.队头顶点出队并记录，删除与该顶点连接的所有边，返回1,E,生成组合对象算法：生成排列,生成组合对象组合对象：满足一定约束条件的集合组合数学：指出组合对象有多少个组合数（通常呈指数级增长）如何生成：本节内容生成排列（前面讲过蛮力法）生成集合元素的全排列，可解释为：生成集合元素下标1,2,.,n的全排列，排列数=n!个减一策略：设规模减一1,2,.,n-1的全排列已解决，有(n-1)!个把n插入到这(n-1)!个排列中去，就解决了规模n的问题，即得1,.,n全排列。在每个1,.,n-1排列中，插入n的位置有(n-1)+1=n个，排列数=(n-1)!n=n!问：这样得到的排列是唯一的吗？答：是。(n-1)!个排列是唯一的，在其不同位置插入一个新元素n，结果当然唯一,生成组合对象算法：生成排列（2）,减一算法（实现从底向上，规模增加）在1,.,n-1排列中，可以从左向右或从右向左插入n较好的插入法：（有什么好处？）1.开始时，从右向左插入n到1,.,n-1子排列的n个位置上2.每次插入完一个子排列，换方向插入n到下一个子排列，如下：开始1插入21221()插入3123132312(3)321231213(3)插入4(4!=24个)最小变化：仅交换排列的相邻两个元素，可得直接后继排列。例如：交换312的12两元素可得直接后继排列321.即相邻两个排列，交换一次元素的位置可以变成另一个。非最小变化情况，下例：123和312：元素交换一次不能变成另一个，当然它们不是相邻的好处：满足最小变化提高算法效率，便于相关应用选用提高效率：可只插入一个元素，然后交换元素位置可得后续排列,生成幂集,生成幂集幂集n元集合A=a1,a2,.,an的全部子集组成的集合子集个数：2n（数学）应用举例0-1背包问题找出n个物品中的最有价值子集，装入一个承重有限的背包中。解背包问题的蛮力法要求：生成n个物品的全部组合减一策略（用元素的下标表示）设1,2,.,n-1问题已解决（规模-1），把n插入到每一个子集，即得规模n的全部子集。与前述排列问题的减一策略的不同处：排列问题在每个1,.,n-1子集中插入元素n的位置有n个，组合问题仅1个插入位置。（为什么？）解释：排列问题与元素在排列中的顺序有关，组合问题与顺序无关，全部元素相同的集合就是同一个集合。,生成幂集：减一算法,减一算法（实现自底向上，规模加一）从空集开始，每次向已生成的每个子集中加入一个元素，如此继续，直到所有n个元素都加入为止。例：生成A=a1,a2,a3全部子集,生成幂集：小规模算法,子集的比特串表示每个比特（二进制位）表示有、无两种状态：1有，0无例如：集合A=a1,a2,a3，3个比特表示23=8个子集比特串000001010011100101110111子集a3a2a2,a3a1a1,a3a1,a2a1,a2,a3十进制数01234567生成幂集的简洁算法一个n元集合，产生0,1,.,2n-1的十进制数序列，其二进制序列即该n元集合的全部子集。最小变化比特串与前述最小变化定义不同生成的相邻两个比特串仅一个比特不同。例如：001与010不是最小变化比特串，二位不同。注：不是一次交换格雷码：最小变化比特串，生成算法见相关文献（ACM考题）000001011010110111101100,减常因子算法,减常因子法减治法的第2种变化。折半查找常因子=2，注意与分治法区别这类算法效率常常是对数型，速度非常快，不要指望有很多此类算法，常因子2的情况更是少之又少。常因子=3，每次规模减2/3.假币问题有n枚外观相同的硬币，其中有一枚假币。设假币较轻，用一架天平将这枚假币检测出来减常因子策略（多种方法，这里仅用减治策略）把n枚硬币等分为两堆n为奇数：留下一枚硬币，把两堆放天平上。若两堆硬币重量相同，留下这枚即为假币n为偶数：较轻的一堆含假币，继续分解它，丢弃较重的那一堆常因子=2，减半法,假币问题（续）,时间效率分析输入规模：硬币数n基本操作：称重（比较操作）效率类别：有最佳、最差、平均效率情况增长函数：称重次数与硬币数n的函数关系T(n)=?1.最佳效率T(n)=1(n为奇数)2.最差效率解此递推式，得本算法并非最高效的算法！更高效的策略是：每次把n个硬币分为3堆，常因子=3，每次减去问题规模的2/3.称重次数约为log3n,比log2n更小。,需要作1次称重将问题规模减半,减常因子法俄式乘法,减常因子法算例俄式乘法（俄国农夫法）问题：两个正整数相乘。十九世纪，俄国农民广泛采用该算法，不需使用九九乘法表。文献介绍，埃及数学家早在公元前1650年就使用了该算法思想。算法策略n和m为两个正整数，计算它们的乘积。问题规模选择n，采用减治策略，可得递推式：（规模减半，常因子=2）n为偶数：n为奇数：算法停止：n=1时停止：1m=m算法实现：递归法、非递归法,减常因子法俄式乘法过程举例,俄式乘法过程举例计算5065nm50652513012260+13065203104012080+1040结果：2080+130+1040=3250简评：硬件实现速度非常快！（理由？）用移位操作完成十进制数折半（右移1位）和加倍（左移1位）移位属于机器的基本操作，执行速度非常快。,减可变规模算法,减可变规模法减治法的第3个主要变种，每次减小的问题规模不一样譬如，求最大公约数的欧氏算法：gcd(m,n)=gcd(n,mmodn),第k轮除数nkmk-1modnk-1、被除数mknk-1取决于前一轮m和n值大小。各轮m、n值比较前一轮，减小的幅度是变化的查找问题例查找中值（中位值）找出n元列表中第k个最小元素（第k个顺序统计量）A=1,2,1,3,4,3,5,5的第k=4最小元素为3，记为A4=3理解：非降序排序后的位置1,1,2,3,3,4,5,5k=1：找最小元素A1=1=Amink=n：找最大元素A8=5=Amax：中值有序列表的中位值，不是均值！,选择问题特例查找中值（续1）,中值查找算法1.蛮力策略对列表排序后选中值。时间效率取决于排序算法的效率。若用合并排序算法，即为O(nlogn)型。2.减治策略更高效（效率分析类似于快速排序，略）s=k：As=中值停止条件sk：分裂点在中位点右边，左子区继续分解sk：分裂点在中位点左边，右子区继续分解,减治法查找中值过程示例,减治法查找中值过程例求列表A=4,1,10,9,7,12,8,2,15的中值，n=9【解】中值下标k=9/2=5（向上取整），即求A5=?选择中轴p=A1，左右扫描法得分裂点（回顾快速排序）：p=A1=4411097128215(左右未交叉)412971281015(左右已交叉)214971281015(得到分裂点)s=3k=5,中值在左子区p=A4=8214(87)9121015(左右相等=7)214789121015(得到分裂点)s=5=k，中值A5=8,减治法查找中值的算法效率,插值查找减可变规模法算例算法目的：对某些查找问题，进一步提高折半查找的效率算法要求：有序列表折半查找的改进优化拆分点：折半查找时每次列表减半（中点拆分）。对某些问题，有更好的拆分点插值点，把有解区域缩得更小，比一半还小，提高了查找算法的效率。插值查找实例查字典（以英文词典为例）问题描述：在英文词典中查找某一个单词字典格式：按字母序安排单词已排序查找策略我们采用的是折半查找吗？首先，翻到尽量靠近待查单词首字母附近如word，不会翻到字典中间开始查，而是翻到尽量靠后的地方开始查，这与查baby不同；然后，该页字母与待查单词首字母比较，决定下次查找方向和增量，多次查找后即可找到。,插值查找算法原理,插值查找算法原理,元素下标x,元素值Ax,插值直线,真实曲线(未知),AxtK，搜索左子树；反之，搜索右子树,二叉查找树的插入算法,BST插入算法（生成BST）给定n个节点，生成一棵BST.如下例：,37244272404232120顺序插入各节点，已生成一棵BST.现在，插入值为35的节点,生成的BST拓扑结构与节点插入顺序有关吗？树高越小越好？查找节点数越少最坏的BST是何形状？整个树变成一条链它是如何形成的？已按节点值大小顺序，并按此顺序插入生成,插入算法：用BST查找算法找到待插入节点位置，然后执行插入。,二叉查找树的删除算法,BST删除算法在BST中，删除一个指定值的节点（值=K）删除算法：先用BST查找算法找到指定的节点，然后删除它。这个要删除的节点有三种情况：1.叶节点：直