算法设计与分析5

《算法设计与分析5》由会员分享，可在线阅读，更多相关《算法设计与分析5（45页珍藏版）》请在金锄头文库上搜索。

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

2、 对 n 个元素 A 0, . , n-1 排序（非降序为例） 减一策略 分析过程自顶向下（规模减小） 减去一个元素 An-1 , 对 A 0,.,n-2 排序（非降序） 原问题的解 = 减一规模的解 + An-1 对数组递归减一，分解到仅一个元素为止；再合并得到原问题解。 插入算法 有三种方法插入一个元素，左右扫描称 直接插入法 左扫描：从左向右扫描有序子数组，遇到第一个An-1 元素为止， 在该元素前插入An-1 . 若未找到，则插在最后。 右扫描：从右向左扫描有序子数组，遇到第一个An-1 元素为止， 在该元素后插入An-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-First Search) 随后两节讨论图的一些常用算法，可看作是 减一技术 的应用。 图是一种令人感兴趣的、有着广泛应用的数据结构。 许多实际问题的计算模型 图结构 1. 领土问题 2. 交通网络 3. 通信网络 4. 棋局、迷宫 图的遍历 从起点出发访问所有顶点。可能遇到的问题： 1. 非连通图：不能访问到某些

5、顶点。 2. 存在回路：要防止陷入死循环。 为每个顶点设置 访问标志 (mark) . 开始时：所有顶点的访问标志置零 遍历时：已访问顶点的标志被标记，以后不访问它，防止回路循环 结束时：检查顶点标志。若有未标记顶点，则重选起点，继续遍历,深度优先搜索DFS,许多图的算法要求对图进行遍历或周游(graph traversal). 主要两种： DFS (Depth-First Search) , BFS (Breadth-First Search) . DFS 深度优先搜索过程简述 从任一顶点（问题确定）出发，沿某一路径搜索该路径上所有未访问顶点，到达 死端（所有相邻顶点都已访问过），沿原路后退

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

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

8、林（不连通的多棵树），而是一种类森林的表示。 若将其转换为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) = ? 它与给定图的表示法（邻接矩阵、邻接链表）有关 一

9、、图的邻接矩阵表示 访问下一个邻接顶点，要检查余下所有顶点，判断是不是邻接顶点。起点开始，从余下 n-1 个顶点选择一个；再访问下一顶点，从 n-2 个顶点中选一个；如此继续，每次余下的顶点数序列：n-1, n-2, . , 1 访问的顶点总数（基本操作数）： T(n) = (n-1) + (n-2) + . + 1 = n(n-1)/2 (n2) 思考：这与给定图 G = 是稠密图或稀疏图有关吗？ 无关：当前顶点并不知道下一个相邻顶点，需要在剩余顶点中寻找， 与连接形式无关。,图的邻接链表表示,DFS的时间效率：邻接链表表示图,二、图的邻接链表表示：下一个邻接顶点在链表中是 确定的,访问顶点

10、数与 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遍历，当遍历算法停止以后，检查是否全部顶点 都已访问过。若都访问过，此图是连通的。否则，此图不

11、连通。因为 遍历算法不能到达的顶点，说明它与图的其他顶点没有路径可通。 DFS 检查图的无环性 如果从某个顶点到它的祖先顶点之间有一条回边，则该图存在回路，以此检查给定图的环。若不存在这样的回边，则为无环。 DFS 其他应用 例如：求图的关节点（从图中移走某个顶点及其与它相连的边以后， 图被分为若干个不相交的部分，该顶点称为关节点）等更复杂应用。,BFS 算法过程图示（以树为例）,BFS 算法过程图示（以树为例）,根据访问顺序，用连续整数 标记各个顶点，如图。,BFS搜索的队列过程图示,BFS 队列过程图示,顶点出、入队线性序列 ACEBDF,BFS 树或森林 森林解释见DFS,BFS 非递归

12、算法,BFS 非递归算法,BFS 相关讨论,BFS 相关讨论 时间效率：同DFS 效率一样。前面讨论DFS的效率时，仅与图的存储 结构（邻接矩阵、邻接链表）有关，与 DFS 或 BFS 无关 应用1：检查图的连通性和无环性，本质上与DFS一样 应用2：求给定两个顶点的最短路径（边数最少，非带权图） 从两个给定的顶点之一开始BFS，当访问到另一个顶点，BFS 结束 从BFS 算法过程看，其正确性不言而喻，但数学上的证明并不简单 说明：这样的最短路径可能不只一条（考虑去掉BG边的图）,BFS 树的一部分，确定了从 A 到 G 的最短路径（边数最少）,拓扑排序,拓扑排序 ( Topological

13、Sort ) 概述 问题提出 假设要安排一系列任务，如教学计划中的安排各门课程的学习顺序， 项目中各子课题的研究顺序，建筑项目，等等。每个任务只有 当 前提条件 具备时，才能去完成这个任务。举例如下： 只有当学完某课程的全部前修课程后，才能安排该课程的教学 拓扑排序 找到在满足前提条件情况下，各个任务如何安排的一个 线性序列 计算模型 图（顶点：一个任务，边：该任务的前提条件） 1. 有向图：任务之间有先后关系 边有方向 2. 无环图：若有环，回路中就会存在彼此矛盾的条件。（想一想） 不可能在不违反前提条件情况下，为这些任务安排一个 合理的顺序，问题无解（存在矛盾条件） 综合1、2，若拓扑排序

14、问题有解，必须是 有向无环图,拓扑排序：有向无环图,有向无环图 无向图：仅有 2 种类型的边 树边、回边 有向图：可有 4 种类型的边 1. 树边：AB BC DE 2. 回边：BA（无回边: 无环图） 3. 前向边（祖孙边） 当前顶点到孙子顶点的边 AC 4. 交叉边（横跨边） 上述 3 种类型以外的边 DC,有向无环图,去掉BA边则为 有向无环图,拓扑排序算法：DFS法 例1,拓扑排序算法 拓扑排序 DFS 算法 【例1】5 门课程的安排，问题模型如图,C 有两门前修课 A B，E 有两门前修课 C D , 必须先安排前修课程。因此，正确次序是： 先安排 A B，然后安排 C ；接下来安排

15、 D， 最后安排 E . 即正确的线性序列序列为： ABCDE 或 BACDE （非唯一解） 任选一个 源顶点 开始 DFS 过程： 源顶点：没有入边，即无前提条件的边 我们选 A 开始 DFS A 到 E 搜索完后，尚有未访问顶点 B，将 B 入栈，从 B 重新开始 DFS . 进栈序列：ACDEB 进栈逆序：BEDCA 出栈序列：EDCAB 出栈逆序：BACDE,问题模型图,拓扑排序算法：DFS 例2,DFS解拓扑排序 【例2】7 个任务的安排,2,1,6,3,7,5,4,问题模型图,退栈线性序列：7 5 4 6 2 3 1 （或 7 5 4 3 6 2 1） 退栈线性逆序：1 3 2 6

16、 4 5 7 （或 1 2 6 3 4 5 7） 解不是唯一的，与顶点选择策略即路径选择有关,拓扑排序的源删除算法,拓扑排序的源删除算法（减一法） 每次减去一个源顶点 若算法结束（无源顶点），尚有未访问顶点时，问题无解！ 存在矛盾条件 顶点的删除顺序即拓扑排序的一个解（不唯一），本例 A B C D E 源删除算法与数据结构 1. 找出全部源顶点并入队。若无源顶点，算法停止。有未访问顶点？ Yes 无解； No 输出解（记录的顶点序列） 2. 队头顶点出队并记录，删除与该顶点连接的所有边，返回 1,E,生成组合对象算法：生成排列,生成组合对象 组合对象：满足一定约束条件的集合 组合数学：指出组合对象有多少个 组合数（通常呈指数级增长） 如何生成：本节内容 生成排列 （前面讲过蛮力法） 生成集合元素 的