算法设计与分析5

算法设计与分析基础IntroductiontotheDesignandAnalysisofAlgorithms第五章减治法DecreaseandConquer第5章减治法★算法策略★插入排序★深度优先搜索DFS★广度优先搜索BFS★拓扑排序★生成组合对象★减常因子法★减可变规模法概念与算法策略★算法策略减治法：利用给定规模与较小规模问题解之间的关系求解问题的方法。实现——自顶向下：规模减小（递归）自底向上：规模增大（非递归）减常量法：常量通常为1（减1法）减常因子法：常因子通常为2（减半法）减可变规模法：每次减去的规模不同原问题(规模n)子问题(规模n-1)子问题解原问题解子问题(规模n/2)子问题解原问题解原问题(规模n)插入排序★插入排序对n个元素A[0,...,n-1]排序（非降序为例）减一策略——分析过程自顶向下（规模减小）减去一个元素A[n-1],对A[0,...,n-2]排序（非降序）原问题的解=减一规模的解+A[n-1]对数组递归减一，分解到仅一个元素为止；再合并得到原问题解。插入算法——有三种方法插入一个元素，左右扫描称直接插入法左扫描：从左向右扫描有序子数组，遇到第一个≥A[n-1]元素为止，在该元素前插入A[n-1].若未找到，则插在最后。右扫描：从右向左扫描有序子数组，遇到第一个≤A[n-1]元素为止，在该元素后插入A[n-1].若未找到，则插在最前。常用：右扫描法。问：理由是什么？理由：子数组若有等值元素，右扫描插入时需移动的元素个数少。——它插在等值元素后，前面等值元素都不用移动位置插入排序算法与算例折半插入法——组合利用减一法和减半法子数组有序，用折半查找为插入元素在其中找到一个合适的位置。算法伪码基于递归思想设计，但非递归实现（从底向上）89689029341745899029341745688929341745688990293417456884569901729344568899017293445689029341889907jjjjjVVVVVVj下划线为待插元素0...1([])////{(1)1,(0[])[11[]//[]]0[1}:]1nVAiInsertionSortAinjijAjVAjAjAjVVfortodowhienjladjj插入元素后移限位思考：为什么是右扫描插入V？插入排序效率分析插入排序效率分析输入规模：元素个数n基本操作：比较操作A[j]V效率类别：输入A为升序，每次插入只需比较1次——最佳效率输入A为降序——最差效率，其他——平均效率最佳效率：要插入n-1个元素，共需比较n-1次（线性效率）也可据伪码计算：最差效率对每个元素如第i个元素插入，从j=i-1比较到j=0，共i次比较，即插入元素A[i]要与前面的全部元素都比较一次。平均效率：比最差效率快2倍。若遇到基本有序数组，比选择排序和冒泡排序的性能略优。11()11()nbestiTnnn11121011()112...(1)(1)()2ninworstijiTninnnn22()/4()avgTnnn图的遍历★深度优先搜索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算法过程图示（以树为例）12345678910111213141516171819202122根据访问顺序，用连续整数标记各个顶点，如图。红色箭头表示回溯过程。DFS算法的栈过程图示DFS栈过程图示AEBCDF从顶点A开始DFSACABCAFBCADFBCAEFBCAFBCABCACAAFBCA顶点选择策略——未访问邻接顶点有多个，按顶点编号的字母序访问。栈空时，DFS遍历结束。DFS可产生进栈、退栈两种顶点线性序列，可按实际情况的需要选用。顶点进栈的线性序列：ACBFDE顶点退栈的线性序列：DEFBCADFS树与森林DFS树与森林DFS可构造出一棵深度优先搜索树（可转换为有根树）或森林树边：图中当前顶点到未访问儿子顶点的边，如CB,FE回边：图中当前顶点到已访问祖父顶点的边，如EA,DCDFS树：不含回边的树（无环图）（只有树边）DFS森林：包含回边的图（有环图）（含有回边）右图实际上不是森林（不连通的多棵树），而是一种类森林的表示。若将其转换为DFS树，不同的顶点选择策略如选择C顶点的下一个邻接顶点为D或者B，可以得到不同的DFS树，这些树组成森林。AEBCDFDFS树AEBCDFDFS森林DFS递归算法DFS递归版(){1[]////0/[()/)]0}(DFSRecursionvertexcountcountMarkvcounteachvertexadjacenttvwvDFSRfordoiftecursionwhvoMarkisitvctwenoun全局变量，初始化为0:已访问按访问序标记顶点////////0GvcouGntV输入:给定图的一个起始顶点输出:图顶点，按访问顺序用连续整数标记中标记为的顶点，表示未访问(,){0()()(())[]0(),1,[///////()()]/DFSGraphVertexcountvirstvInitializeSisEmptySFALSExeachvertexadjacenttoMarkwhilefordGvPushvPopSwvirstwcountcountMarkwcoifthewxPounptonSvt顶点标号栈初始化为空起始顶点入栈栈顶顶点出栈(})ushwDFS非递归算法DFS非递归版vtopSPush(v)DFS的时间效率DFS时间效率分析输入规模：顶点数n基本操作：顶点访问判断Mark[w]=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=V,E是稠密图或稀疏图有关吗？无关：当前顶点并不知道下一个相邻顶点，需要在剩余顶点中寻找，与连接形式无关。(2)(2)(3)(2)(3)(2)abcdecdcfabeaecdfbef表头顶点边数图的邻接链表表示DFS的时间效率：邻接链表表示图二、图的邻接链表表示：下一个邻接顶点在链表中是确定的acbdef访问顶点数与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算法过程图示（以树为例）12581216212213179143671015181920114根据访问顺序，用连续整数标记各个顶点，如图。BFS搜索的队列过程图示BFS队列过程图示AEBCDF从顶点A开始BFSA头A入队，开始BFSCEA出队，A的邻接顶点C,E入队FD出队，D无未访问邻接顶点入队DFB出队，B无未访问的邻接顶点入队EBDFC出队，C的邻接顶点B,D,F入队BDFE出队，E无未访问的邻接顶点入队F出队，F无未访问的邻接顶点入队此时队列空，BFS过程结束顶点出、入队线性序列ACEBDFBFS树或森林森林解释见DFSAEBCDF交叉边BFS非递归算法BFS非递归算法(,){0()()(())[]0(),()()////,[]////BFSGraphVertexcountvirstvInitializeQisEmptyQFGvEnqueuevvDequeueQwALSExeachvertexadjacenttoMarkwvirstwcounwtMarkwcouQhilnefordoifthetxnEn顶点标号队列初始化为空起始顶点入队队头顶点出队)}(queuew//,//////0GVcouGVnvtE输入:图和起始顶点输出:图顶点，按访问顺序用连续整数标记中标记为的顶点:未访问BFS相关讨论BFS相关讨论时间效率：同DFS效率一样。前面讨论DFS的效率时，仅与图的存储结构（邻接矩阵、邻接链表）有关，与DFS或BFS无关应用1：检查图的连通性和无环性，本质上与DFS一样应用2：求给定两个顶点的最短路径（边数最少，非带权图）从两个给定的顶点之一开始BFS，当访问到另一个顶点，BFS结束从BFS算法过程看，其正确性不言而喻，但数学上的证明并不简单说明：这样的最短路径可能不只一条（考虑去掉BG边的图）BFS树的一部分，确定了从A到G的最短路径（边数最少）AEBCDFGHAEBCFG拓扑排序★拓扑排序(TopologicalSort)概述问题提出假设要安排一系列任务，如教学计划中的安排各门课程的学习顺序，项目中各子课题的研究顺序，建筑项目，……等等。每个任务只有当前提条件具备时，才能去完成这个任务。举例如下：——只有当学完某课程的全部前修课程后，才能安排该课程的教学拓扑排序找到在满足前提条件情况下，各个任务如何安排的一个线性序列计算模型——图（顶点：一个任务，边：该任务的前提条件）1.有向图：任务之间有先后关系——边有方向2.