算法设计与分析5.ppt

《算法设计与分析5.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析基础IntroductiontotheDesignandAnalysisofAlgorithms第五章减治法DecreaseandConquer第5章减治法算法策略插入排序深度优先搜索DFS广度优先搜索BFS拓扑排序生成组合对象减常因子法减可变规模法概念与算法策略算法策略减治法：利用给定规模与较小规模问题解之间的关系求解问题的方法。实现——自顶向下：规模减小（递归）自底向上：规模增大（非递归）减常量法：常量通常为1（减1法）减常因子法：常因子通常为2（减半法）减可变规模法：每次减去的规模不同原问题(规模n)子问题(规模n-1)子问题解原问题解减一技术子问题(规模n/2)子问题解

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].若未找到，则插在最前。常用：

3、右扫描法。问：理由是什么？理由：子数组若有等值元素，右扫描插入时需移动的元素个数少。——它插在等值元素后，前面等值元素都不用移动位置插入排序算法与算例折半插入法——组合利用减一法和减半法子数组有序，用折半查找为插入元素在其中找到一个合适的位置。算法伪码基于递归思想设计，但非递归实现（从底向上）下划线为待插元素思考：为什么是右扫描插入V？插入排序效率分析插入排序效率分析输入规模：元素个数n基本操作：比较操作A[j]>V效率类别：输入A为升序，每次插入只需比较1次——最佳效率输入A为降序——最差效率，其他——平均效率最佳效率：要插入n-1个元素，共需比较n-1次（线性效率）也可据伪码计算：最差效

4、率对每个元素如第i个元素插入，从j=i-1比较到j=0，共i次比较，即插入元素A[i]要与前面的全部元素都比较一次。平均效率：比最差效率快2倍。若遇到基本有序数组，比选择排序和冒泡排序的性能略优。图的遍历深度优先搜索DFS(Depth-FirstSearch)随后两节讨论图的一些常用算法，可看作是减一技术的应用。图是一种令人感兴趣的、有着广泛应用的数据结构。许多实际问题的计算模型——图结构1.领土问题2.交通网络3.通信网络4.棋局、迷宫……图的遍历——从起点出发访问所有顶点。可能遇到的问题：1.非连通图：不能访问到某些顶点。2.存在回路：要防止陷入死循环。——为每个顶点设置访问标志(mar

5、k).开始时：所有顶点的访问标志置零遍历时：已访问顶点的标志被标记，以后不访问它，防止回路循环结束时：检查顶点标志。若有未标记顶点，则重选起点，继续遍历深度优先搜索DFS许多图的算法要求对图进行遍历或周游(graphtraversal).主要两种：DFS(Depth-FirstSearch),BFS(Breadth-FirstSearch).DFS深度优先搜索过程简述从任一顶点（问题确定）出发，沿某一路径搜索该路径上所有未访问顶点，到达死端（所有相邻顶点都已访问过），沿原路后退一条边，从那里继续访问未访问过的顶点（回溯）；当回溯到开始顶点，并且它成为死端时，DFS过程结束。顶点选择策略：搜索

6、过程中，若某顶点有多个邻接顶点，可以按顶点编号（或其他策略如优先值大小选择顶点）进行访问，下页图示。DFS搜索的非递归实现——栈过程1.当前顶点入栈2.将栈顶顶点的下一个未访问邻接顶点入栈若栈顶顶点无未访问邻接顶点，该顶点退栈（回溯）3.重复2，直到栈空为止，DFS过程结束DFS算法构造出一棵DFS树（或森林）DFS算法过程图示DFS算法过程图示（以树为例）12345678910111213141516171819202122根据访问顺序，用连续整数标记各个顶点，如图。红色箭头表示回溯过程。DFS算法的栈过程图示DFS栈过程图示AEBCDF从顶点A开始DFSACABCAFBCADFBCAEF

7、BCAFBCABCACAAFBCA顶点选择策略——未访问邻接顶点有多个，按顶点编号的字母序访问。栈空时，DFS遍历结束。DFS可产生进栈、退栈两种顶点线性序列，可按实际情况的需要选用。顶点进栈的线性序列：ACBFDE顶点退栈的线性序列：DEFBCADFS树与森林DFS树与森林DFS可构造出一棵深度优先搜索树（可转换为有根树）或森林树边：图中当前顶点到未访问儿子顶点的边，如CB,FE回边：图中当前顶点到已访问祖