第3章 蛮力法资料课件.ppt
2023/1/16,算法设计与分析-蛮力法,1,第3章 蛮力法,3.1 概述,3.2 查找问题中的蛮力法,3.3 排序问题中的蛮力法,3.4 组合问题中的蛮力法,3.5 图问题中的蛮力法,3.6 几何问题中的蛮力法,2023/1/16,算法设计与分析-蛮力法,2,3.1 概述,蛮力法(穷举法)，是一种简单而直接地解决问题的方法。设计思想：直接基于问题的描述。,例：计算an,3.1.1 蛮力法的设计思想,2023/1/16,算法设计与分析-蛮力法,3,应用实例:计算an的值是RSA算法的主要组成部分。RSA算法的加密和解密过程都需要一个整数的整数次幂再取模。,例如，设公钥为(5,119)，私钥为(77,119)，明文m=19，则加密得密文c为：c=195 mod 119=2 476 099 mod 119=66解密得明文m为：m=6677 mod 119=19计算an算法的效率直接影响到RSA算法的性能。,2023/1/16,算法设计与分析-蛮力法,4,蛮力法所依赖的基本技术扫描技术 关键依次处理所有元素,基本的扫描技术遍历（1）集合的遍历（2）线性表的遍历（3）树的遍历（4）图的遍历,2023/1/16,算法设计与分析-蛮力法,5,蛮力法也是一种重要的算法设计技术，原因如下：,（1）理论上，蛮力法可以解决可计算领域的各种问题。（2）蛮力法经常用来解决一些较小规模的问题。（3）对于一些重要的问题（如：排序、查找）蛮力法可以产生一些合理的算法。（4）蛮力法可以作为某类问题时间性能的底限，来衡量同样问题的更高效算法。,2023/1/16,算法设计与分析-蛮力法,6,举例：百元买百鸡问题,已知公鸡5元一只，母鸡3元一只，小鸡1元三只，用100元钱买100只鸡，问公鸡、母鸡、小鸡各多少只？,2023/1/16,算法设计与分析-蛮力法,7,3.2 查找问题中的蛮力法,3.2.1 顺序查找,3.2.2 串匹配问题,2023/1/16,算法设计与分析-蛮力法,8,顺序查找从表的一端向另一端逐个将元素与给定值进行比较，若相等，则查找成功，给出该元素在表中的位置；若整个表检测完仍未找到与给定值相等的元素，则查找失败，给出失败信息。,3.2.1 顺序查找,2023/1/16,算法设计与分析-蛮力法,9,算法3.1的基本语句是i0和ri!=k，其执行次数为:,基本语句？,其中pi是第i个元素的查找概率，而bi和ci分别是基本语句i0和ri!=k的执行次数,2023/1/16,算法设计与分析-蛮力法,10,将待查值放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高了查找速度。,改进的顺序查找,2023/1/16,算法设计与分析-蛮力法,11,算法3.2的基本语句是ri!=k，其执行次数为:,数量级相同，系数相差一半,2023/1/16,算法设计与分析-蛮力法,12,用蛮力法设计的算法，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能，但只能减少系数，而数量级不会改变。,一般观点：,2023/1/16,算法设计与分析-蛮力法,13,3.2.2 串匹配问题（略）,串匹配问题属于易解问题。串匹配问题的特征：（1）算法的一次执行时间不容忽视：问题规模 n 很大，常常需要在大量信息中进行匹配；（2）算法改进所取得的积累效益不容忽视：串匹配操作经常被调用，执行频率高。,串匹配问题给定两个串S=“s1s2sn”和T=“t1t2tm”，在主串S中查找子串T的过程称为串匹配，也称模式匹配。,2023/1/16,算法设计与分析-蛮力法,14,3.3 排序问题中的蛮力法,3.3.1 选择排序,3.3.2 起泡排序,排序：给定一个记录序列(r1,r2,rn)，其相应的关键字分别为(k1,k2,kn)，排序是将这些记录排列成顺序为(rs1,rs2,rsn)的一个序列，使得相应的关键字满足ks1ks2 ksn(升序或非降序)或 ks1 ks2 ksn(降序或非升序)。,2023/1/16,算法设计与分析-蛮力法,15,3.3.1 选择排序,选择排序第i趟排序从第i个记录开始扫描序列，在n-i+1（1in-1）个记录中找到关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。,2023/1/16,算法设计与分析-蛮力法,16,该算法的基本语句是内层循环体中的比较语句rjrindex，其执行次数为：,2023/1/16,算法设计与分析-蛮力法,17,起泡排序在扫描过程中两两比较相邻记录，如果反序则交换，最终，最大记录就被“沉到”了序列的最后一个位置，第二遍扫描将第二大记录“沉到”了倒数第二个位置，重复上述操作，直到n-1遍扫描后，整个序列就排好序了。解释冒泡的含义,3.3.2 起泡排序,2023/1/16,算法设计与分析-蛮力法,18,该算法的基本语句是内层循环体中的比较语句rjrj+1，其执行次数为：,2023/1/16,算法设计与分析-蛮力法,19,基于起泡排序的特点，可对上述算法进行改进：,2023/1/16,算法设计与分析-蛮力法,20,在最好情况下，待排序记录序列为正序，算法只执行一趟，进行了n-1次关键码的比较，不需要移动记录，时间复杂性为O(n),例：正序 1 2 3 4 5 6 7 8 9 10,例：反序 10 9 8 7 6 5 4 3 2 1,2023/1/16,算法设计与分析-蛮力法,21,最坏情况：记录的比较次数为 关键码的移动次数为因此，时间复杂性为O(n2)；,平均情况：时间复杂性与最坏情况同数量级。,2023/1/16,算法设计与分析-蛮力法,22,3.4 组合问题中的蛮力法,3.4.1 0/1背包问题,3.4.2 任务分配问题,补充 生成排列对象,3.4.4,要求生成并依次考察问题域中的每一个元素，从中选出满足问题的约束的元素。易产生组合爆炸现象。,2023/1/16,算法设计与分析-蛮力法,23,3.4.1 0/1背包问题,0/1背包问题是给定n个重量为w1,w2,wn、价值为v1,v2,vn的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。,用蛮力法解决0/1背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价值，然后在他们中找到价值最大的子集。,2023/1/16,算法设计与分析-蛮力法,24,2023/1/16,算法设计与分析-蛮力法,25,结论:,对于一个具有n个元素的集合，其子集数量是2n，所以，不论生成子集的算法效率有多高，蛮力法都会导致一个(2n)的算法。,2023/1/16,算法设计与分析-蛮力法,26,3.4.2 任务分配问题,假设有n个任务需要分配给n个人执行，每个任务只分配给一个人，每个人只分配一个任务，且第j个任务分配给第i个人的成本是Ci,j（1i,jn），任务分配问题要求找出总成本最小的分配方案。,2023/1/16,算法设计与分析-蛮力法,27,下面是一个任务分配问题的成本矩阵，矩阵元素Ci,j代表将任务j分配给人员i的成本。,任务分配问题就是在分配成本矩阵中的每一行选取一个元素，这些元素分别属于不同的列，并且元素之和最小。,2023/1/16,算法设计与分析-蛮力法,28,用一个n元组(j1,j2,jn)来描述任务分配问题的一个可能解，其中第i个分量ji（1in）表示在第i行中选择的列号，因此用蛮力法解决任务分配问题要求生成整数1n的全排列，然后把成本矩阵中的相应元素相加来求得每种分配方案的总成本，最后选出具有最小和的方案。,2023/1/16,算法设计与分析-蛮力法,29,结论,由于任务分配问题需要考虑的排列数量是n!，所以，除了该问题的一些规模非常小的实例，蛮力法几乎是不实用的。,2023/1/16,算法设计与分析-蛮力法,30,补充：生成排列对象,假设已经生成了所有(n-1)!个排列，可以把n插入到n-1个元素的每一种排列中的n个位置中去，来得到问题规模为n的所有排列。按照这种方式生成的所有排列都是独一无二的，并且他们的总数应该是n(n-1)!=n!。,开始 1插入2 12 21插入3 123 132 312 213 231 321 生成排列的过程,2023/1/16,算法设计与分析-蛮力法,31,显然，算法3.9的时间复杂性为O(n!)，也就是说和排列对象的数量成正比。,2023/1/16,算法设计与分析-蛮力法,32,补充：生成子集,n个元素的集合A=a1,a2,an的所有2n个子集和长度为n的所有2n个比特串之间的一一对应关系。建立对应关系：为每一个子集指定一个比特串b1b2bn，如果ai属于该子集，则bi1；如果ai不属于该子集，则bi0（1in）。,比特串 000 001 010 011 100 101 110 111子集 a3 a2 a2,a3 a1 a1,a3 a1,a2 a1,a2,a2,2023/1/16,算法设计与分析-蛮力法,33,生成n个元素子集的算法如下：,显然，算法3.10的时间复杂性为O(2n)，也就是说和子集的数量成正比。,2023/1/16,算法设计与分析-蛮力法,34,3.5 图问题中的蛮力法,3.5.1 哈密顿回路问题,3.5.2 TSP问题,2023/1/16,算法设计与分析-蛮力法,35,3.5.1 哈密顿回路问题,著名的爱尔兰数学家哈密顿（William Hamilton，18051865）提出了著名的周游世界问题。他用正十二面体的20个顶点代表20个城市，要求从一个城市出发，经过每个城市恰好一次，然后回到出发城市。,2023/1/16,算法设计与分析-蛮力法,36,使用蛮力法寻找哈密顿回路的基本思想是：对于给定的无向图G=(V,E)，首先生成图中所有顶点的排列对象(vi1,vi2,vin)，然后依次考察每个排列对象是否满足以下两个条件：,（1）相邻顶点之间存在边，即(vij,vij+1)E（1jn-1）（2）最后一个顶点和第一个顶点之间存在边，即(vin,vi1)E,满足这两个条件的回路就是哈密顿回路。,目前没有有效的算法求解哈密顿回路问题,2023/1/16,算法设计与分析-蛮力法,37,(a)一个无向图,显然，蛮力法求解哈密顿回路在最坏情况下需要考察所有顶点的排列对象，其时间复杂性为O(n!)。,例:蛮力法求解哈密顿回路,(b)哈密顿回路求解过程,2023/1/16,算法设计与分析-蛮力法,38,3.5.2 TSP问题,TSP问题是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。,用蛮力法解决TSP问题，可以找出所有可能的旅行路线，从中选取路径长度最短的简单回路。,2023/1/16,算法设计与分析-蛮力法,39,若有n个城市，则可能的解有(n-1)!/2个。随着n的增长，TSP问题的可能解也在迅速地增长。,2023/1/16,算法设计与分析-蛮力法,40,一个10城市的TSP问题有大约有180,000个可能解。一个20城市的TSP问题有大约有 60,000,000,000,000,000个可能解。一个50城市的TSP问题有大约1062个可能解，而一个行星上也只有1021升水。,例如：,用蛮力法求解TSP问题，只能解决问题规模很小的实例。,2023/1/16,算法设计与分析-蛮力法,41,3.6 几何问题中的蛮力法,3.6.1 最近对问题,3.6.2 凸包问题,2023/1/16,算法设计与分析-蛮力法,42,3.6.1 最近对问题,最近对问题要求找出一个包含n个点的集合中距离最近的两个点。,考虑二维情况，并假设两个点Pi=(xi,yi)和Pj=(xj,yj)之间的距离是标准的欧几里德距离：,2023/1/16,算法设计与分析-蛮力法,43,分别计算每一对点之间的距离，然后找出距离最小的那一对，为了避免对同一对点计算两次距离，只考虑ij的那些点对(Pi,Pj)。,蛮力法求解最近对问题的过程,2023/1/16,算法设计与分析-蛮力法,44,int ClosestPoints(int n,int x,int y,int,2023/1/16,算法设计与分析-蛮力法,45,算法3.11的基本操作是计算两个点的欧几里德距离。所以，算法3.11的基本操作就是求平方，其执行次数为：,2023/1/16,算法设计与分析-蛮力法,46,3.6.2 凸包问题,定义3.1 对于平面上的一个点的有限集合，如果以集合中任意两点P和Q为端点的线段上的点都属于该集合，则称该集合是凸集合。显然，任意凸多边形都是凸集合。,2023/1/16,算法设计与分析-蛮力法,47,定义 一个点集S的凸包是包含S的最小凸集合，其中，最小是指S的凸包一定是所有包含S的凸集合的子集。,对于平面上n个点的集合S，它的凸包就是包含所有这些点（或者在内部，或者在边界上）的最小凸多边形。,2023/1/16,算法设计与分析-蛮力法,48,凸包问题是为一个具有n个点的集合构造凸多边形的问题。为了解决凸包问题，需要找出凸多边形的顶点，这样的点称为极点。一个凸集合的极点应该具有这样性质：对于任何以凸集合中的点为端点的线段来说，它不是这种线段中的点。,定理3.1 任意包含n2个点（不共线）的集合S的凸包是以S中的某些点为顶点的凸多边形；如果所有点都位于一条直线上，则凸多边形退化为一条线段。,2023/1/16,算法设计与分析-蛮力法,49,蛮力法求解凸包问题的基本思想：对于一个由n个点构成的集合S中的两个点Pi和Pj，当且当该集合中的其他点都位于穿过这两点的直线的同一边时（假定不存在三点同线的情况），他们的连线是该集合凸包边界的一部分。对每一对顶点都检验一遍后，满足条件的线段构成了该凸包的边界。,2023/1/16,算法设计与分析-蛮力法,50,这样一条直线把平面分成两个半平面：其中一个半平面中的点都满足ax+byc，另一个半平面中的点都满足ax+byc，因此，为了检验这些点是否位于这条直线的同一边，可以简单地把每个点代入表达式ax+by-c，检验这些表达式的符号是否相同。,在平面上，过两个点(x1,y1)和(x2,y2)的直线是由下面的方程定义的：ax+by=c(其中，a=y2-y1,b=x1-x2,c=x1y2-y1x2),2023/1/16,算法设计与分析-蛮力法,51,算法的效率,所有不同的点共组成了n(n-1)/2边，对每条边都要对其他n-2个顶点求出表达式ax+by-c的符号，所以，其时间复杂性是O(n3)。,
