《算法设计与分析》课件 chp2枚举法

枚举法算法设计的起点与基础什么是枚举法?枚举法,也称为蛮力法,是一种根据问题本身的性质和定义,逐一列举出所有可能的解,并在列举过程中逐一检验每个可能解是否为问题的真正解的方法。如果某个解满足条件,则采纳该解;否则,忽略它。尽管这种方法不一定是最快的,但它保证能够找到最优解,因此枚举法是我们学习算法的起点。生活中的枚举法假设一个袋子中装有许多大小不同的球,现在需要找出其中最大的一个球。我们可以逐一取出球进行比较,直到找到最大的那个球。这就是枚举法的基本思路:列出所有可能的解,然后逐一验证每个解是否满足条件。寻找最大球算法枚举法的优势与局限优势能够全面遍历整个搜索空间,从而确保最终得到最优解局限需要检查所有可能的解,效率往往较低,尤其是在解空间规模较大时应用场景适合小规模问题或作为算法学习的起点,通常需要结合其他优化方法枚举法求解范式01确定枚举对象枚举对象定义了问题解的整个搜索空间02逐一列举可能解根据枚举对象的性质,逐一列举每一种可能的情况03逐一验证可能解根据问题的要求,逐一验证枚举对象的每一个取值是否满足条件中国剩余定理《孙子算经》中记载:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?有一个数,它被3除的余数是2,它被5除的余数是3,被7除的余数是2,求这个数。用枚举法求解"有数几何"1确定枚举对象此问题的枚举对象为所有的正整数2逐一列举可能解通过循环的方式从1开始逐一遍历正整数,直到找到一个满足条件的正整数3逐一验证可能解如果正整数满足三个整除条件,则采纳它,算法结束枚举法的编程优势枚举法在求解问题时,除了能保证得到最优解,还有一个明显的优势是方便编程。只要根据问题描述确定搜索空间,然后在逐一验证时确定搜索条件,那么可容易解决问题。字符串匹配问题字符串匹配问题是计算机科学中的一个经典问题,有着广泛的实际应用。搜索引擎在网页中查找包含关键词的内容文本编辑器"查找和替换"功能DNA序列分析匹配特定的序列模式字符串匹配的目标在一个较长的文本字符串T中,寻找一个较短的模式字符串P出现的位置。如果能够找到这个位置,就说明模式字符串存在于文本中,否则就不存在。假设文本字符串为"helloworld",模式字符串为"world",字符串匹配问题就是要找到"world"在"helloworld"中的位置,也就是文本字符串的第七个字符开始匹配成功。字符串匹配的枚举法求解确定枚举对象假设文本字符串T的长度为n,模式字符串P的长度为m(n≥m),则P在T中出现的位置可能有n-m+1个逐一列举可能解通过循环的方式逐一遍历可能的匹配位置,从位置1开始,直到n-m+1逐一验证可能解如果模式字符串中的每一个字符都与文本字符串对应位置的字符相等,就认为匹配成功字符串匹配算法复杂度Θ(nm)最坏情况需要检查文本字符串T中的所有可能匹配位置,每个位置上都要比较模式字符串P的所有字符Θ(m)最好情况模式字符串P在文本字符串T的第一个位置就成功匹配O(1)空间复杂度仅需常数级别的额外空间来存储变量旅行商问题(TSP)TSP是一个经典的组合优化问题,目标是找到一条最短路径,使得旅行商从一个城市出发,访问每个城市恰好一次,并最终返回起始城市。4城市TSP问题示例对于每个城市，都有一条路径去往其他3个城市，而城市之间的路径为正整数。

A→B→C→D→A,距离:23A→B→D→C→A,距离:23A→C→B→D→A,距离:14A→C→D→B→A,距离:23A→D→B→C→A,距离:14A→D→C→B→A,距离:23从城市A出发再返回A的最短路径是:(A,C,B,D,A)和(A,D,B,C,A)第二步：逐一验证可能解起始城市为A时,共有6条路线。当起始城市为B、C或D时,各有6条路线。当有4个城市时,路线总数量为24条。TSP枚举法的时间复杂度1010个城市路径数量为10!=3,628,8002020个城市路径数量超过2×10¹⁸虽然枚举法能够保证找到TSP的最优解,但它需要遍历所有n!条可能的路径,时间复杂度为O(n!)。随着城市数量n的增加,算法的运行时间呈阶乘级增长,使得枚举法在解决大规模TSP问题时变得不切实际。O(n!)背包问题在某地发生地震后,一架运输机需要将一些物资送往灾区。运输机的最大承重为W,每个物品的重量和紧急程度分别为w₁,w₂,...,wₙ和v₁,v₂,...,vₙ,其中n是物品的数量。目标是从这些物品中选择一部分放入运输机,使得运输机的总重量不超过W,同时让运输机带去的物资能满足灾区人民的急迫需求。背包问题示例假设运输机的最大承重是W=10,现有4件物资:食物2中(3)水3高(5)帐篷4低(1)药品5高(5)物品

重量紧急程度背包问题的枚举法求解确定枚举对象枚举对象是所有物品的选择组合。对于每个物品,可以选择放入运输机或者不放入,所以每个物品有两种选择。对于4个物品,则总共有2⁴=16种可能的物品组合逐一列举可能解对于每个可能的物品组合,可以使用二进制数(a₁,a₂,a₃,a₄)来表示,aᵢ=1表示选择第i个物品,aᵢ=0表示不选择第i个物品逐一验证可能解对于每一个可能的物品组合,验证其总重量是否超过背包的承重限制。如果超过,则忽略这个组合;如果不超过,则计算该组合的总紧急程度背包问题最优解最优组合:1101(二进制)选择:食物+水+药品总重量:10总紧急程度:13(最大值)因此,算法时间复杂度为Θ(n·2ⁿ),当n较大时,算法的运行时间将迅速增加。在后续章节,我们会用贪心算法、动态规划等思想再次分析此问题并给出更高效的算法。外层循环遍历每一种物品组合(共2ⁿ种),随后调用calculateWeightAndUrgency函数计算当前物品组合下的物体总重量和总紧急程度(循环体需要执行n次)。n皇后问题在一个n×n的棋盘上,摆放n个皇后使得任意的两个皇后不在同一行、同一列和同一对角线上,问有多少种不同的摆放方法。我们考虑一个4×4的棋盘来理解这个问题。

4皇后问题的枚举法求解1确定枚举对象枚举对象是4个皇后的摆放位置,用(p₁,p₂,p₃,p₄)表示,其中pᵢ表示第i个皇后在棋盘中的列位置2逐一列举可能解假定每一行只放一个皇后,且各皇后不在同一列,则4个皇后的组合为4×3×2×1=24种3逐一验证可能解对于每一种可能的摆放组合,需要验证其是否符合4皇后问题的要求,只需检查两个皇后是否处于同一条对角线遍历n!种摆放方式isValid需要两两比较,最坏情况下时间复杂度为Θ(n²)枚举法求解n皇后问题的时间复杂度至少为Ω(n!),组合算法概述TSP问题和n皇后问题涉及到排列生成问题。目前已有多种方法可生成给定集合的所有排列,下面介绍几种经典的排列生成算法。自底向上的排列生成对于生成{1,...,n}的所有n!个排列,假设已知{1,...,n-1}的所有(n-1)!个排列,那么如何得到{1,...,n}的所有排列?我们可以通过将n插入到这些排列中的不同位置来得到{1,...,n}的所有排列。排列生成示例假设已知{1,2,3}的所有排列为:1,2,3;1,3,2;2,1,3;2,3,1;3,1,2;3,2,1将元素4插入到每个排列中的每个位置,得到{1,2,3,4}的所有排列。例如,对于排列1,2,3,可以生成:4,1,2,3(插入位置1)1,4,2,3(插入位置2)1,2,4,3(插入位置3)1,2,3,4(插入位置4)同理，要得到{1,2,3}的所有排列，可以将数字3插入到{1,2}的每个排列中的所有可插入位置。自底向上排列生成的复杂度在第i次迭代时,会遍历perms中所有长度为i-1的排列(此时perms中已包含(i-1)!个这类排列),每个排列有i个可插入位置。算法的时间复杂度为Θ(n!),空间复杂度为Θ(n·n!)。按字典序的排列生成

例如,对于{1,2,3,4},按照字典序它的所有排列为:1234,1243,1324,1342,1423,1432,2134,2143,2314,2341,2413,2431,3124,3142,3214,3241,3412,3421,4123,4132,4213,4231,4312,4321字典序排列生成算法步骤字典序算法复杂度O(n·n!)时间复杂度每次迭代生成排列时,最坏情况下为O(n),共有n!种排列O(1)空间复杂度仅需要存储若干临时变量(j,l)等Heap's算法Heap's算法是一种生成给定数组所有排列的方法。它的核心思想是,除了第一个排列外,每一个排列都是通过交换前一个排列中的两个元素得到的,从而生成不同的排列。Heap's算法的递归方式1第一步固定最后一个元素为n,递归生成前n-1个元素的所有排列,共有(n-1)!种排列2第二步从前n-1个元素中选择一个数m₁与aₙ交换,递归生成前n-1个元素的所有排列3第三步从前n-1个元素中选择一个数m₂与m₁交换,递归生成前n-1个元素的所有排列4重复依次类推,直到生成以mₙ₋₁为最后一个元素的所有排列

Heap's算法的交换策略n是偶数时先选择第一个数,然后是第二个数,接着是第三个数,依此类推n是奇数时总是选择第一个数Heap's算法示例生成{1,2,3,4}所有排列的过程:先生成最后一个元素为4的6个排列,然后将4和1交换,再生成最后一个元素为1的6个排列,然后将1和2交换,再生成最后一个元素为2的6个排列,最后将2和3交换,生成最后一个元素为3的6个排列,共生成24个排列。Heap's算法复杂度算法的时间复杂度为O(n!)空间复杂度为O(1)。算法的基本操作为swap,假设S(n)表示生成n个元素的所有排列需要的swap操作的次数,则:枚举法在操作系统中的应用磁盘调度问题是操作系统中一个经典的调度问题,涉及如何有效地管理磁盘的读写请求以优化磁盘的性能。假设磁盘上的当前磁头位置H磁道,现有一组待处理的磁盘请求,表示为一个整数数组R={r₁,r₂,...,rₙ},其中每个rᵢ表示一个待访问的磁道号。磁盘调度的目标是确定磁头移动的顺序,以最小化总的寻道时间或寻道距离,从而提高磁盘的访问效率。磁盘调度问题的枚举法求解1确定枚举对象枚举对象是n个待访问磁道的所有可能排列。对于每一个排列,表示一种可能的磁头移动顺序2逐一列举可能解生成所有n!种可能的请求处理顺序3逐一验证可能解对于每一种排列,计算其对应的总寻道距离,并记录最小值及其对应的排列磁盘调度示例假设当前磁头位置H=50,请求序列R={10,22,20,2,40,6}。对于排列{10,22,20,2,40,6},总寻道距离为:|50-10|+|10-22|+|22-20|+|20-2|+|2-40|+|40-6|=144对于n个请求,排列的总数为n!。对每种方案,需要计算总的寻道距离,因此,枚举法求解磁盘调度算法的时间复杂度为Ω(n×n!)。磁盘调度的实际应用随着请求数量n的增加,算法的时间复杂度呈阶乘级增长,这意味着当n较大时,枚举法的计算量将变得极其庞大,导致其在实际应用中几乎不可行。实际操作系统中通常采用更高效的磁盘调度算法,如SCAN算法、C-SCAN算法等。枚举法总结枚举法就是按照问题本身的性质,一一列举出该问题所有可能的解,并在列举的过程中,逐一检验每个可能解是否是问题的真正解。若是则采纳这个解;否则,忽略它。枚举法的主要特点实现简单算法逻辑清晰,易于理解和编程实现效率较低需要遍历所有可能的解,时间复杂度通常较高优化空间大通过剪枝等技术可以