中南大学减治法课件

1、算法设计与分析 计算机与信息学院,2,使用教材,使用教材,作者：（美）Anany Levitin 译者：潘彦 出版社：清华大学 丛书名：国外经典教材 计算机 科学与技术,第5章 减治法,算法策略 插入排序 深度优先搜索DFS与 广度优先搜索BFS 拓扑排序 减常因子法 减可变规模法,4,概念与算法策略,算法策略 减治法：利用给定规模与较小规模问题解之间的关系，从顶至下(递归) 或从底至上(非递归)求解问题的一种方法。 减治法通常分为3种： 减常量法：常量通常为1即减1法，也有减2的（如奇偶数分别处理） 减常因子法：常因子通常为2（减半技术）。 减可变规模法。,5,插入排序,插入排序 （非降序）

2、 设计策略：用减治技术对一个 n元素数组A0,.,n-1排序。考虑减一 技术，假设对较小数组A0,.,n-2排序问题已解决，得到 n-1个元素 有序数组A0A1An-2。现在问题：如何把这个较小规模的解 与原问题第An-1元素合并考虑，得到原问题的解。显然，要做的是 把An-1这个元素插入到减一后的有序数组A0,.,n-2的恰当位置。 这样，就利用了减一技术。递归的对较小的数组继续减一，即可得到 一个递归算法。递归减一，直到子数组仅有一个元素为止。 插入算法：有3种方法实现一个元素插入，左右扫描称为直接插入法 左扫描：从左向右扫描有序子数组，当遇到第一个大于等于An-1 元素为止，在该元素前面

3、插入An-1。若未找到(Max)，插在最后。 右扫描：从右向左扫描有序子数组，当遇到第一个小于等于An-1 元素为止，在该元素后面插入An-1。若未找到(Min)，插在最前。 左右扫描比较：实践中，常采用右扫描法。【理由？】 理由：若子数组中有多个等值元素，右扫描法在插入前需移动的元素 个数较少。（前面等值元素都无需作位置的移动）,6,插入排序算法与算例,折半插入法：因为子数组是有序的，因此可使用折半查找，为插入元素 An-1在子数组中找到一个恰当的位置：AkAn-1 Ak+1。这是 组合利用了减一技术和减半技术的一个算例。 算法实现（伪码） 至顶向下的递归思考方法，非递归的实现 虽然本算法明

4、显基于递归思想，但由底向上来实现插入排序（非递归） 效率更高。,7,插入排序效率分析,插入排序效率分析 输入规模：待排序数组的元素个数 n； 基本操作：键值比较操作 AjV； 效率类别：显然有最佳、最差、平均效率。若输入数组本身为升序，每次插入只需比较1次。 最佳效率：有n-1个元素要插入，显然共比较 n-1次。线性效率。 也可根据伪码计算： 最差效率： 对于每个如第 i 个元素插入，从 j= i-1 比较到 j=0，共 i 次键值比较， 即插入元素Ai与包括Ai-1的前面全部元素都比较一次（这种情况 出现在输入数组A本身是降序）。 平均效率：比最差效率快2倍。若遇到基本有序数组，比选择排序和

5、 冒泡排序的性能优异。,8,图的遍历,深度优先搜索DFS 与广度优先搜索BFS 随后两节讨论图问题的一些重要算法，可看作是减一技术的应用。 图是一种令人感兴趣的数据结构，具有各种广泛应用。特别是AI程序 设计中的许多问题用图建模。如领土问题：许多国家中某些国家两两 邻接，要求从某个国家（顶点）出发，通过国家之间的连接（边）， 从一国到达另一国，最后到达一个指定的终点国。 图的遍历算法典型的是从一个起点出发，试探性访问其余顶点。它还 必须处理若干棘手情况。首先，从起点出发可能到达不了其他顶点， 非连通图就会发生此种情况。其次，某些图存在回路，我们必须确定 算法不会因回路而陷入死循环。为避免发生这

6、些情况，遍历算法通常 为图的每个顶点设置一个访问标志(mark)。算法开始时，所有的顶点 访问标志清零。遍历中，被访问过的顶点标志被标记。遇到被标记的 顶点，则不再访问它。这样，可避免回路问题。遍历算法结束时检查 标志数组，查看算法是否处理了所有顶点。若还有未被标记的顶点， 我们可以从未被标记的顶点出发，继续遍历。,9,深度优先搜索DFS,许多图算法要求对图进行遍历或称周游(graph traversal)。主要有两种 遍历算法：DFS(depth-first search) 和BFS(breadth-first search). DFS: 从任一顶点（可由问题确定）开始，沿着一条路径搜索这条

7、路径 上的所有未访问顶点，当搜索到这条路径的死端（末端）即该顶点的 所有相邻顶点都已访问过时，沿原路后退一条边，并从那里继续访问 未访问过的顶点（回溯）。当后退到开始顶点，并且开始顶点是一个 死端时，该算法停止。访问过程中，若某顶点有多个邻接顶点，那么 可以按顶点编号或其他策略（如权值大小）进行访问。见下页图示。 图的描述（存储）：邻接矩阵，邻接链表。前面讲过。 DFS 的非递归实现：（栈：每个元素为一个顶点） 1. 把当前顶点入栈；（开始顶点） 2. 从图描述中取栈顶元素的下一个未访问的邻接顶点，该顶点入栈。 若栈顶顶点没有未访问的邻接顶点，则该顶点退栈。 3. 重复第2步，直到栈中全部元素

8、处理完毕（栈空）为止。 DFS可构造出一个深度优先搜索树或森林。,10,DFS 算法过程图示,DFS 算法过程图示（以树为例）,输出：图的各个顶点。按访问顺序 用连续整数标记各顶点。,11,DFS 算法的栈过程图示,DFS 算法的栈过程图示,本例：当未访问邻接顶点 有多个时，按顶点编号的 字母序访问。 图示了DFS非递归算法的 栈的进出情况。栈空时， 遍历结束。DFS可以产生 两种顶点序列，不同应用 按需利用。,顶点进栈的线性序列：ACBFDE,顶点退栈的线性序列：EDFBCA,12,DFS树与森林,DFS树与森林 DFS 可构造出一个深度优先搜索树（图转换为有根树）或森林。 树边：当前顶点到

9、未访问邻接儿子顶点的边。 回边：当前顶点到已访问邻接祖/父顶点的边。 深度优先搜索树： 不含回边的树（无环图）。（树边） 深度优先搜索森林：包含回边的图（有环图）。（树边+回边） 实际上，它不是森林（不连通的多棵树），而是一种类森林表示。 若将其转换为DFS树，不同的顶点选择策略（如选择C顶点的下一个 邻接顶点为D或B），可生成不同的DFS树，这些树组成一个森林。,13,DFS 递归算法,DFS 递归算法,14,DFS 非递归算法,DFS 非递归算法,15,DFS的时间效率,DFS的时间效率 输入规模：一个图的顶点数 n ； 基本操作：访问顶点； 效率类别：图一定时，DFS算法没有最佳、最差、

10、平均效率之分。 增长函数即基本操作数（访问顶点的个数）与顶点数 n 的关系，它与 给定图的结构（连接方法）和表示法（邻接矩阵、邻接链表）有关。 邻接矩阵：访问下一个邻接顶点时，需检查剩下的所有顶点，判断它 是否邻接顶点，即需要访问全部 可能的 剩余顶点。从起始顶点开始， 余下有 n-1个可能顶点，判断后选择一个顶点，继续访问下一个顶点， 有n-2 个可能顶点，如此下去，每次剩余的顶点数：n-1, n-2, . , 1。 总的访问顶点数：（图G = ） T(n) = (n-1)+(n-2)+.+1 = n(n-1)/2(n2), |V|=n2 注意，这与给定图是稠密图（包括全连接的完全图）或稀疏

11、图无关。 因为，当前顶点并不知道它的下一个相邻顶点是谁，须在剩余顶点中 一个个去寻找（访问矩阵元素值），把它们都找出来，然后选择。,16,DFS的时间效率：邻接链表表示图,邻接链表：下一个邻接顶点在链表中是确定的，即实际存在的。,现讨论访问顶点数与规模n的关系： 1. 每个表头顶点需要访问，以找到 该顶点开始的邻接顶点链； 2. 每个链表的剩余顶点数正好等于 该顶点链表的边数，剩余顶点是 需要访问的。 以每个顶点开始的全部链表都需要 访问，完成图的遍历。遍历结束， 访问顶点总数等于1、2 顶点之和： T(n) ( |V|+|E| ), |V| = n |E|max = nn = n2 , |E

12、| 0, |V|2 |E|=n2 ：完全图。|E|=0: 孤立顶点 结论：对于稠密图，邻接矩阵表示 效率较高（无链表的额外开销）； 对于稀疏图，邻接链表表示更好。,图的邻接链表表示,17,DFS简单应用,DFS 简单应用 DFS 检查图的连通性： 从任意顶点开始DFS遍历，当遍历算法停止以后，检查是否全部顶点 都已访问过。若都访问过，此图是连通的。否则，此图不连通。因为 遍历算法不能到达的顶点，说明它与图的其他顶点没有路径可通。 DFS 检查图的无环性： 如果从某个顶点到它的祖先顶点（非父顶点）之间有一条回边，则该 图存在一个回路，以此可检查给定图的环，这是DFS森林。若不存在 这样的回边，则

13、为DFS树，是无环的。 DFS 其他应用： 例如：求图的关节点（从图中移走某个顶点及其与它相连的边以后， 图被分为若干个不相交的部分，该顶点称为关节点）这样一些更复杂 的应用。,18,BFS 算法过程图示（以树为例）,BFS 算法过程图示（以树为例）,广度优先搜索BFS如图所示。 输出：图的各个顶点。按访问顺序 用连续整数标记各顶点。 跟踪BFS搜索的数据结构：队列， 其余实现与DFS相似。,19,BFS搜索的队列过程图示,BFS搜索的队列过程图示,顶点的出入队线性序列 ACEBDF,20,BFS 非递归算法,BFS 非递归算法,21,BFS 相关讨论,BFS 相关讨论 时间效率：同DFS效率

14、一样。前面讨论DFS的效率时，仅与图的存储 结构（邻接矩阵、邻接链表）有关，与DFS或BFS无关。 应用1：检查图的连通性和无环性，本质上与DFS一样。 应用2： 可求给定两个顶点间的最短路径（边数最少）。 从两个给定的顶点之一开始BFS，当访问到另一个顶点就结束BFS。 从起始顶点开始到另一个顶点之间的简单路径就是所求最短路径。 从BFS操作过程看，正确性不言而喻，但数学上的证明并不简单。 说明：这样的最短路径可能不只一条（考虑去掉BG边的图）。,BFS树的一部分，确定了从A到G的最短路径（边数最少）,22,拓扑排序,拓扑排序 ( Topological Sort ) 概述 问题提出：假设我

15、们要安排一系列任务，如任务分工，教学计划中的 各门课程的安排顺序，项目中各子课题的研究顺序，建筑项目等等。 每个任务只有其当先决条件具备时，才能着手安排这个任务去完成。 例如：不能随意安排课程，只有当修完某门课程所有的前修课程后， 才能安排这门课程。要求找到在满足先决条件情况下，各个任务如何 安排的一个线性序列。这就是拓扑排序问题。 建模：用图来建模。顶点：一个任务，边：某个任务的先决条件。 1. 有向图：因为任务之间有先后关系，因此，边是有方向的。 2. 无环图：若为有环图，回路中就存在相互矛盾的条件。【想一想】 这不可能在不违反任何先决条件的情况下，为这些任务 安排出一个合理的顺序，本问题

16、无解。 结论：综合1、2，拓扑排序有解的图，必然是有向无环图。,23,拓扑排序的源删除算法,拓扑排序的源删除算法（减一算法）：每次减去一个源顶点 若算法结束（已没有源顶点），尚有未访问顶点，该问题无解，说明 问题中存在矛盾的先决条件。顶点被删除的次序就是拓扑排序的一个 可行解（不唯一）。本例为：ABCDE 源删除算法的实现： 队列 1. 在图中找出所有无先决条件的源顶点，将它们全部入队。若无源， 算法停止，输出记录的顶点序列，得到解（无未访问顶点）。 2. 队头顶点出队（实现删除操作），且按出队顺序记录顶点，并同时 删除从这个顶点出发的所有的边。（队列的出入队顺序相同） 3. 返回1步执行。,

17、问题模型图,E,24,生成组合对象问题 5.4.1 生成排列 最小变化要求 Johnson-Trotter算法 字典序 5.4.2 生成子集 子集 挤压序 Grey Code,25,减常因子算法,减常因子算法 减治法的第二种变化。前面讲过的折半查找（常因子为2）就是这种算法 设计技术，注意它与分治法的区别。这类算法效率常常是对数型，速度 非常快，不要指望有很多此类算法，常因子不是2的情况更是少之又少。 常因子为2，每次规模减半；常因子为3，每次规模减去2/3。 假币问题 问题描述：有n枚外观相同的硬币，其中一枚是假币。假设假币较轻， 用一架天平将这枚假币检测出来。 减常因子策略：（有多种方法，

18、这里仅考虑应用减治法策略） 把 n 枚硬币分成两堆，每堆有 枚。若 n 为奇数，就留下一枚 额外的硬币，然后把两堆放天平上，若两堆硬币重量相同，那么放旁边 的就是假币；否则，对较轻的一堆（含假币）用同样方法处理，即继续 分解这堆（n 为偶数即如此处理）。较重的另一堆因为不含有假币，即 无需对它作任何处理（抛弃），这就是减半技术（k = 2）。,26,假币问题（续）,时间效率分析： 输入规模：硬币总数 n； 基本操作：称重操作（比较）； 效率类别：显然，有最佳、最差、平均情况。 增长次数：增长函数（称重次数与n的函数关系）的增长快慢（类型）； 1. 最佳效率： T(n) = 1 (n=2k-1,

19、 k0) 2. 最差效率： 解此递推式，得 其他讨论： 本算法并非最高效的算法！更高效策略是：每次把 n 个硬币分为 3 堆即 常因子为3，每次减去问题规模的2/3。可以期望称重次数大约为log3n， 它比log2n更小。,问题规模减半后， 需要作1次称重。,27,减常因子法俄式乘法,俄式乘法（俄国农夫法） 问题：两个正整数相乘。十九世纪，俄国农民广泛采用该算法，不需 使用九九乘法表。有文献介绍，埃及数学家早在公元前1650年 就使用了该算法思想。 算法： n 和 m 为两个正整数，计算它们的乘积。问题规模选择 n ，采用减治 策略，显然可以得到如下递推式：（规模减半） 1) n为偶数： 2)

20、 n为奇数： 算法停止条件： 当 n = 1 时停止递推即：1m = m 算法实现方法：递归法、迭代法（非递归的循环算法，不断修正或者 改写迭代有关变量）,28,减常因子法俄式乘法过程举例,俄式乘法过程举例： 计算 5065 n m 50 65 25 130 12 260 +130 6 520 3 1040 1 2080 +1040 (停止) 结果：2080 + 130 + 1040 = 3250 简评： 该算法硬件实现速度非常快！理由：采用移位操作即可完成二进制数的 折半（右移1位）和加倍（左移1位），移位操作属于机器层面上最基本 的操作。十进制数在机器内部是二进制表示的。,29,约瑟夫斯问

21、题,30,减可变规模算法,减可变规模算法 如前所述，它是减治法的第三个主要变种。每次递推（或迭代）时， 问题规模减小的大小不一样。譬如，求最大公约数的欧氏算法： gcd(m, n) = gcd(n, m mod n) , 第 k 轮除数 nk mk-1 mod nk-1 和 被除数 mknk-1 取决于前一轮（k-1轮）的 m 和 n 值大小，显然， 各轮迭代时，本轮的 m、n 值相比前一轮，其减小的幅度是变化的， 区别于减常量和减常因子。本节介绍另外几种算法实例。 选择问题特例查找中值（中位值），中值应用广泛 选择问题：找出 n 元列表的第 k 个最小元素（第k个顺序统计量）。 例如：A=1

22、,2,1,3,4,3,5,5 的第 k = 4 个最小元素为 3，记为A4 = 3。 理解为非降序排序后的位置：A=1,1,2,3,3,4,5,5 k=1：找最小元素。 A1 = 1 = Amin k=n：找最大元素。 A8 = 5 = Amax 中值：它比列表中一半元素值小，比另外一半元素值大，如上 k = 4。 注意，它不是全部元素的均值。,31,选择问题特例查找中值（续1）,中值查找算法： 1. 蛮力策略： 直接基于问题本身而设计算法 先对列表按非降序排序，然后选第 k 位置上的元素即中位值。该算法 时间效率显然取决于排序算法的效率，若用合并排序等优秀算法，本 算法效率类型属于 O(nl

23、ogn) 型。 2. 减治策略： 更高效（效率分析类似于前述的快速排序，本节略） 回顾：快速排序算法中关于分区(Partition)的概念。 s左边有 s-1个元素值As，s右边有n-s个元素值As，根据中值的 定义， n为奇数：s-1=n-s，s=n/2+1/2 ；n为偶数 s-1+1=n-s，s=n/2。 1) 若s=k，As 就是中值。 停止条件 2) 若sk，分裂点在中值点右边，对s左子区递归分解。（AsAk） 3) 若sk，分裂点在中值点左边，对s右子区递归分解。（AsAk）,32,减治法查找中值过程示例,减治法查找中值过程示例： 求：已知列表A的中值，A= 4,1,10,9,7,1

24、2,8,2,15 。观察：中值=8 解：n=9, 中值元素下标 k=9/2+1=5（向上取整），即中值A5 = ? 选择第1个元素为中轴p，用左右扫描法得到分裂点，并安排新顺序： p=A1=4 4 1 10 9 7 12 8 2 15 (左右未交叉) 4 1 2 9 7 12 8 10 15 (左右已交叉) 2 1 4 9 7 12 8 10 15 (得到分裂点) s=3k=5, 处理左子区 p=A4=8 2 1 4 ( 8 7 ) 9 12 10 15 (左右相等为7) 2 1 4 7 8 9 12 10 15 (得到分裂点) s=5=k，停止。中值为A5 = 8,33,减治法查找中值的算法

25、效率,插值查找 减可变规模法应用实例 算法意义：对某些查找问题，进一步提高 折半查找 效率。 算法要求：先对输入的 n元列表排序，即有序列表。 问题描述：折半查找，每轮用列表 中点 将列表减半即规模减半，我们 自然要问，就某些问题而言，是否有更好的 分点 将列表规模减小呢？ 回答是肯定的，这即是 插值点。它可将包含问题解的区域缩得更小， 比一半还小，从而减少问题规模的分解次数，获得更高的查找效率。 插值查找法一个实例：查字典（如电子辞典的检索） 问题描述：在英文字典中查找某个单词。 字典格式：按字母升序格式安排单词条目（已排序）。 查找策略：我们并非采用折半查找法。而是依据先验知识，首先翻到

26、尽量靠近待查单词的首字母附近，比如查找单词 word，你不会翻到 字典中间开始查，而是翻到字典中尽量靠后的地方开始查找，这与查 baby 不一样。然后，将这次翻到的位置上字母，与待查单词作比较后 决定下次查找方向（比较字母值的大小）和页码增量（比较字母值的 差距），多次查找后即可找到。,34,插值查找算法图解,插值查找算法图解：,元素下标x,元素值Ax,插值直线(构造),真实曲线(未知),因为AxtAx，所以应在x, r 区间查找Ax，l, x区域被丢弃 （无解）。为此左端点移位 lx 重新构造插值曲线（蓝色线）， 继续迭代过程。直到Axt=Ax 为止，输出查找结果x。,元素值Ax：全部单词首

27、字母的ASCII码值，字典中为非降序安排。 元素下标 x：待查单词首字母在字典A中的位置（页码）。 简评： 1. 平均键值比较次数 log2log2n+1，最差效率为线性（比折半法差）。 2. 规模不大用折半查找，大规模可考虑插值查找（视具体情况定）。,35,二叉查找树的查找算法,二叉查找树(Binary Search Tree, BST) 查找算法 二叉查找树：或称二叉检索树。设任一节点值为K，则该节点左子树 的任一节点值都小于K，该节点右子树的任一节点值都大于等于K。 下面给出一组已知节点值的两棵二叉查找树。 问题描述：查找给定节点值K的节点。如：k=40 若 K=35？ 减治算法 仅检索

28、两棵子树之一（子树规模不同） 1. 从根节点开始，比较K与当前节点值，若相等输出结果；否则转2； 2. 若当前节点值大于K，则检索其左子树；否则，检索其右子树。,37,7,24,42,32,40,42,120,2,120,2,42,42,37,40,32,24,7,Min,Max,Min,Max,36,二叉查找树的插入算法,二叉查找树(BST) 插入算法：生成二叉查找树 问题描述：给定 n 个节点值，生成一颗二叉查找树。举例：在下图的 二叉查找树中插入一个值为K=35的节点。,37,7,24,42,32,40,42,120,2,35,按照37,24,42,7,2,40,42,32,120的顺序

29、 将各个节点插入，生成查找二叉树。 现在，插入值为 35 的节点,查找二叉树的拓扑结构， 与插入的节点顺序有关。 一般讲，树高越小越好， 如此查找的节点数就少。 最坏情况下，可得到一个 严格歪斜的树，即整个树 所有节点仅有一个分支， 即一条链。这种情况发生 在节点按照已排好的顺序 插入生成的树。,插入算法：用查找算法找到待插入节点的位置后，执行插入操作。 因此，两种算法差不多，两者的时间效率相同 。,37,二叉查找树的删除算法,二叉查找树(BST) 删除算法 问题描述：删除二叉查找树的指定值K的节点。 减治策略：用查找算法（运用了减治技术）找到指定的节点。 删除算法：找到指定节点后，该节点有3种情况： 1. 叶节点：简单，直接删除之。 2. 非叶节点，有一个子节点：删除它，将其子节点连入。 3