第3章 蛮力法

1、2022-3-7算法设计与分析-蛮力法1第第3章章 蛮力法蛮力法 3.1 概述概述3.2 查找问题中的蛮力法查找问题中的蛮力法3.3 排序问题中的蛮力法排序问题中的蛮力法3.4 组合问题中的蛮力法组合问题中的蛮力法3.5 图问题中的蛮力法图问题中的蛮力法3.6 几何问题中的蛮力法几何问题中的蛮力法2022-3-7算法设计与分析-蛮力法23.1 概述概述蛮力法蛮力法(穷举法穷举法)，是一种简单而直接地解决问题的方，是一种简单而直接地解决问题的方法。设计思想：直接基于问题的描述。法。设计思想：直接基于问题的描述。n次an=aaa例：计算例：计算an3.1.1 蛮力法的设计思想蛮力法的设计思想 20

2、22-3-7算法设计与分析-蛮力法3应用实例应用实例: 计算计算an的值是的值是RSA算法的主要组成算法的主要组成部分。部分。 RSA算法的加密和解密过程都需要一算法的加密和解密过程都需要一个整数的整数次幂再取模。个整数的整数次幂再取模。n例如，设公钥为例如，设公钥为(5,119)，私钥为，私钥为(77,119)，明，明文文m=19，则加密得密文，则加密得密文c为：为：nc=195 mod 119=2 476 099 mod 119=66n解密得明文解密得明文m为：为：nm=6677 mod 119=19n计算计算an算法的效率直接影响到算法的效率直接影响到RSA算法的性能。算法的性能。202

3、2-3-7算法设计与分析-蛮力法4n 蛮力法所依赖的基本技术蛮力法所依赖的基本技术扫描技术扫描技术n 关键关键依次处理所有元素依次处理所有元素 n 基本的扫描技术基本的扫描技术遍历遍历（1）集合的遍历）集合的遍历（2）线性表的遍历）线性表的遍历（3）树的遍历）树的遍历 （4）图的遍历）图的遍历 2022-3-7算法设计与分析-蛮力法5蛮力法也是一种重要的算法设计技术，原因如下：蛮力法也是一种重要的算法设计技术，原因如下： （1）理论上，蛮力法可以解决可计算领域的）理论上，蛮力法可以解决可计算领域的各种问题。各种问题。 （2）蛮力法经常用来解决一些较小规模的问）蛮力法经常用来解决一些较小规模的问

4、题。题。 （3）对于一些重要的问题（如：排序、查找）对于一些重要的问题（如：排序、查找）蛮力法可以产生一些合理的算法。蛮力法可以产生一些合理的算法。 （4）蛮力法可以作为某类问题时间性能的底）蛮力法可以作为某类问题时间性能的底限，来衡量同样问题的更高效算法。限，来衡量同样问题的更高效算法。 2022-3-7算法设计与分析-蛮力法6举例：百元买百鸡问题举例：百元买百鸡问题 已知公鸡已知公鸡5元一只，母鸡元一只，母鸡3元一只，小元一只，小鸡鸡1元三只，用元三只，用100元钱买元钱买100只鸡，问公鸡、只鸡，问公鸡、母鸡、小鸡各多少只？母鸡、小鸡各多少只？2022-3-7算法设计与分析-蛮力法73.

5、2 查找问题中的蛮力法查找问题中的蛮力法 3.2.1 顺序查找顺序查找 3.2.2 串匹配问题串匹配问题2022-3-7算法设计与分析-蛮力法8 顺序查找从表的一端向另一端顺序查找从表的一端向另一端逐个逐个将元素与给将元素与给定值进行比较，若相等，则查找成功，给出该元素定值进行比较，若相等，则查找成功，给出该元素在表中的位置；若整个表检测完仍未找到与给定值在表中的位置；若整个表检测完仍未找到与给定值相等的元素，则查找失败，给出失败信息。相等的元素，则查找失败，给出失败信息。3.2.1 顺序查找顺序查找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i

6、查找方向查找方向2022-3-7算法设计与分析-蛮力法9算法算法3.1顺序查找顺序查找 int SeqSearch1(int r , int n, int k) /数组r1 rn存放查找集合 i=n; while (i0 & ri!=k) i-; return i; C+描述算法算法3.1的的基本语句基本语句是是i0和和ri!=k，其执行次数为，其执行次数为:ninininiiiiinOninninncpbp1111)(1) 1(1) 1(1基本语句基本语句 ？其中其中pi是第是第i个元素的查找概率，而个元素的查找概率，而bi和和ci分别是分别是基本语句基本语句i0和和ri!=k的执行

7、次数的执行次数2022-3-7算法设计与分析-蛮力法10将将待查值待查值放在查找方向的放在查找方向的尽头尽头处，免去了在查找过处，免去了在查找过程中每一次比较后都要判断查找位置是否程中每一次比较后都要判断查找位置是否越界越界，从，从而提高了查找速度。而提高了查找速度。k 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i查找方向查找方向哨兵哨兵改进的顺序查找改进的顺序查找2022-3-7算法设计与分析-蛮力法11算法3.2改进的顺序查找 int SeqSearch2(int r , int n, int k) /数组数组r1 rn存放查找集合存放查找集

8、合 r0=k; i=n; while (ri!=k) i -; return i;C+描述算法算法3.2的的基本语句基本语句是是ri!=k，其执行次数为，其执行次数为: niniiinOninncp11)(21) 1(1数量级相同，数量级相同，系数相差一半系数相差一半2022-3-7算法设计与分析-蛮力法12 用蛮力法设计的算法，都可以对算法的用蛮力法设计的算法，都可以对算法的第一个版本进行一定程度的改良，改进其时第一个版本进行一定程度的改良，改进其时间性能，但只能减少系数，而数量级不会改间性能，但只能减少系数，而数量级不会改变。变。v 一般观点：一般观点：2022-3-7算法设计与分析-蛮力

9、法133.2.2 串匹配问题串匹配问题 （略）（略） 串匹配问题属于易解问题。串匹配问题属于易解问题。 串匹配问题的特征：串匹配问题的特征：（1）算法的一次执行时间不容忽视：问题规模）算法的一次执行时间不容忽视：问题规模 n 很大，很大，常常需要在大量信息中进行匹配；常常需要在大量信息中进行匹配；（2）算法改进所取得的积累效益不容忽视：串匹配操作）算法改进所取得的积累效益不容忽视：串匹配操作经常被调用，执行频率高。经常被调用，执行频率高。 串匹配问题串匹配问题给定两个串给定两个串S=“s1s2sn” 和和T=“t1t2tm”，在，在主串主串S中查找子串中查找子串T的过程称为的过程称为串匹配串匹

10、配，也称模式匹配。，也称模式匹配。2022-3-7算法设计与分析-蛮力法143.3 排序问题中的蛮力法排序问题中的蛮力法 3.3.1 选择排序选择排序 3.3.2 起泡排序起泡排序排序：给定一个记录序列排序：给定一个记录序列(r(r1 1,r,r2 2, ,r,rn n) )，其相应的，其相应的关键字分别为关键字分别为(k(k1 1,k,k2 2, ,k,kn n) ) ，排序是将这些记录，排序是将这些记录排列成顺序为排列成顺序为(r(rs1s1,r,rs2s2, ,r,rsnsn) )的一个序列，使得相的一个序列，使得相应的关键字满足应的关键字满足k ks1s1 k ks2 s2 k ksn

11、sn( (升序或非降序升序或非降序) )或或 k ks1s1 k ks2 s2 k ksn sn ( (降序或非升序降序或非升序) ) 。2022-3-7算法设计与分析-蛮力法153.3.1 选择排序选择排序 选择排序第选择排序第i趟排序从第趟排序从第i个记录开始扫描序列，个记录开始扫描序列，在在n-i+1（1in-1）个记录中找到关键码最小的记）个记录中找到关键码最小的记录，并和第录，并和第i个记录交换作为有序序列的第个记录交换作为有序序列的第i个记录。个记录。 r1 r2 ri- -1 ri ri+1 rmin rn 有序区有序区 无序区无序区 已经位于最终位置已经位于最终位置 rmin为

12、无序区的最小记录为无序区的最小记录 交换交换2022-3-7算法设计与分析-蛮力法16算法算法3.6选择排序选择排序 void SelectSort( (int r , int n) ) /数组下标从数组下标从1 1开始开始 for ( (i=1; i=n- -1; i+) ) /对对n个记录进行个记录进行n- -1趟简单选择排序趟简单选择排序 index=i; for ( (j=i+1; j=n; j+) ) /在无序区中找最小记录在无序区中找最小记录 if ( (rjrindex) ) index=j; if ( (index!=i) ) ririndex; /若最小记录不在最终位置则交换

13、若最小记录不在最终位置则交换 C+描述 该算法的基本语句是内层循环体中的比较语句该算法的基本语句是内层循环体中的比较语句rjrindex，其执行次数为：，其执行次数为： 112111)(2) 1()(1nininijnOnnin2022-3-7算法设计与分析-蛮力法17起泡排序在扫描过程中两两比较相邻记录，如果反起泡排序在扫描过程中两两比较相邻记录，如果反序则交换，最终，最大记录就被序则交换，最终，最大记录就被“沉到沉到”了序列的了序列的最后一个位置，第二遍扫描将第二大记录最后一个位置，第二遍扫描将第二大记录“沉到沉到”了倒数第二个位置，重复上述操作，直到了倒数第二个位置，重复上述操作，直到n

14、-1 遍扫遍扫描后，整个序列就排好序了。描后，整个序列就排好序了。 解释冒泡的含义解释冒泡的含义3.3.2 起泡排序起泡排序 rj rj+1 ri+1 rn- -1 rn 无序区无序区 有序区有序区 1ji- -1 位于最终位置位于最终位置反序则交换反序则交换2022-3-7算法设计与分析-蛮力法18算法算法3.7起泡排序起泡排序 void BubbleSort( (int r , int n) ) /数组下标从数组下标从1 1开始开始 for (i=1; i=n- -1; i+) for (j=1; jrj+1) rjrj+1；/如果反序，则交换元素如果反序，则交换元素 C+描述 该算法的基

15、本语句是内层循环体中的比较语该算法的基本语句是内层循环体中的比较语句句rjrj+1，其执行次数为：，其执行次数为： 112111)(2) 1()(1niniinjnOnnin2022-3-7算法设计与分析-蛮力法19基于起泡排序的特点，可对上述算法进行改进：基于起泡排序的特点，可对上述算法进行改进：算法算法3.8改进的起泡排序改进的起泡排序 void BubbleSort( (int r , int n) ) /数组下标从数组下标从1 1开始开始 exchange=n; /第一趟起泡排序的范围是第一趟起泡排序的范围是r1到到rn while ( (exchange) ) /仅当上一趟排序有记录

16、交换才进行本趟排序仅当上一趟排序有记录交换才进行本趟排序 bound=exchange; exchange=0； for ( (j=1; jrj+1) ) rjrj+1； exchange=j； /记录每一次发生记录交换的位置记录每一次发生记录交换的位置 C+描述2022-3-7算法设计与分析-蛮力法20在在最好情况最好情况下，待排序记录序列为正序，算下，待排序记录序列为正序，算法只执行一趟，进行了法只执行一趟，进行了n- -1次关键码的比较，次关键码的比较，不需要移动记录，时间复杂性为不需要移动记录，时间复杂性为O( (n) )例：正序例：正序 1 2 3 4 5 6 7 8 9 10例：反

17、序例：反序 10 9 8 7 6 5 4 3 2 12022-3-7算法设计与分析-蛮力法21最坏情况：最坏情况：记录的比较次数为记录的比较次数为 关键码的移动次数为关键码的移动次数为因此，时间复杂性为因此，时间复杂性为O( (n2) )；2)1(11nninni）（2)1(3311nninni）（平均情况：平均情况：时间复杂性与最坏情况同数量级。时间复杂性与最坏情况同数量级。2022-3-7算法设计与分析-蛮力法223.4 3.4 组合问题中的蛮力法组合问题中的蛮力法 3.4.1 0/1背包问题背包问题3.4.2 任务分配问题任务分配问题补充补充 生成排列对象生成排列对象 3.4.4 要求生

18、成并依次考察问题域中的每一个要求生成并依次考察问题域中的每一个元素，从中选出满足问题的约束的元素。元素，从中选出满足问题的约束的元素。易产生组合爆炸现象。易产生组合爆炸现象。2022-3-7算法设计与分析-蛮力法233.4.1 0/1背包问题背包问题 0/1背包问题是给定背包问题是给定n个重量为个重量为w1, w2, ,wn、价值为价值为v1, v2, ,vn的物品和一个容量为的物品和一个容量为C的背包，的背包，求这些物品中的一个最有价值的子集，并且要能够求这些物品中的一个最有价值的子集，并且要能够装到背包中。装到背包中。 用蛮力法解决用蛮力法解决0/1背包问题，需要考虑给定背包问题，需要考虑

19、给定n个个物品集合的所有子集，找出所有可能的子集（总重物品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价量不超过背包容量的子集），计算每个子集的总价值，然后在他们中找到价值最大的子集。值，然后在他们中找到价值最大的子集。2022-3-7算法设计与分析-蛮力法2410w1=7v1=42w2=3v2=12w3=4v3=40w4=5v4=25背包背包 物品物品1 物品物品2 物品物品3 物品物品4 81,412161,2,3,419序号序号子集子集总重量总重量总价值总价值序号序号子集子集总重量总重量总价值总价值 100 92,3752 21742102,4837

20、 32312113,4965 43440121,2,314不可行不可行 54525131,2,415 61,21054141,3,416 71,311不可行不可行152,3,412不可行不可行不可行不可行不可行不可行不可行不可行不可行不可行2022-3-7算法设计与分析-蛮力法25结论结论: 对于一个具有对于一个具有n个元素的集合，其子集个元素的集合，其子集数量是数量是2n，所以，不论生成子集的算法效率，所以，不论生成子集的算法效率有多高，蛮力法都会导致一个有多高，蛮力法都会导致一个(2n)的算法。的算法。2022-3-7算法设计与分析-蛮力法263.4.2 任务分配问题任务分配问题 假设有假

21、设有n个任务需要分配给个任务需要分配给n个人执行，每个人执行，每个任务只分配给一个人，每个人只分配一个任个任务只分配给一个人，每个人只分配一个任务，且第务，且第j个任务分配给第个任务分配给第i个人的成本是个人的成本是Ci, j（1i , jn），任务分配问题要求找出总成本），任务分配问题要求找出总成本最小的分配方案。最小的分配方案。 2022-3-7算法设计与分析-蛮力法27 下面是一个任务分配问题的成本矩阵，矩阵元下面是一个任务分配问题的成本矩阵，矩阵元素素Ci, j代表将任务代表将任务j分配给人员分配给人员i的成本。的成本。 C= 9 2 7 6 4 3 5 8 1任务任务1 任务任务2

22、任务任务3人员人员1人员人员2人员人员3 任务分配问题任务分配问题就是在分配成本矩阵中的每一行就是在分配成本矩阵中的每一行选取一个元素，这些元素分别属于不同的列，并且选取一个元素，这些元素分别属于不同的列，并且元素之和最小。元素之和最小。2022-3-7算法设计与分析-蛮力法28 用一个用一个n元组元组(j1, j2, , jn)来描述任务分配问题的来描述任务分配问题的一个可能解，其中第一个可能解，其中第i个分量个分量ji（1in）表示在第）表示在第i行中选择的列号，因此用蛮力法解决任务分配问题行中选择的列号，因此用蛮力法解决任务分配问题要求生成整数要求生成整数1n的全排列，然后把成本矩阵中的

23、相的全排列，然后把成本矩阵中的相应元素相加来求得每种分配方案的总成本，最后选应元素相加来求得每种分配方案的总成本，最后选出具有最小和的方案。出具有最小和的方案。 序号序号分配方案分配方案 总成本总成本11, 2, 39+4+1=1421, 3, 29+3+8=2032, 1, 32+6+1=942, 3, 12+3+5=1053, 1, 27+6+8=2163, 2, 17+4+5=162022-3-7算法设计与分析-蛮力法29结论 由于任务分配问题需要考虑的排列数量是由于任务分配问题需要考虑的排列数量是n!，所以，除了该问题的一些规模非常小的实例，所以，除了该问题的一些规模非常小的实例，蛮力

24、法几乎是不实用的。蛮力法几乎是不实用的。 2022-3-7算法设计与分析-蛮力法30补充：补充： 生成排列对象生成排列对象 假设已经生成了所有假设已经生成了所有(n-1)!个排列，可以把个排列，可以把n插入到插入到n-1个元素的每一种排列中的个元素的每一种排列中的n个位置中去，来得到个位置中去，来得到问题规模为问题规模为n的所有排列。按照这种方式生成的所的所有排列。按照这种方式生成的所有排列都是独一无二的，并且他们的总数应该是有排列都是独一无二的，并且他们的总数应该是n(n-1)!=n!。开始开始 1插入插入2 12 21插入插入3 123 132 312 213 231 321 生成排列的过

25、程生成排列的过程2022-3-7算法设计与分析-蛮力法31算法算法3.9生成排列对象生成排列对象 1生成初始排列生成初始排列1； 2for (i=2; i=n; i+) for (j=1; j=1; k-) 将将i插入到第插入到第j个排列中的第个排列中的第k个位置；个位置； 显然，算法显然，算法3.9的时间复杂性为的时间复杂性为O(n!)，也就，也就是说和排列对象的数量成正比。是说和排列对象的数量成正比。 2022-3-7算法设计与分析-蛮力法32补充：补充： 生成子集生成子集 n个元素的集合个元素的集合A=a1, a2, an的所有的所有2n个子个子集和长度为集和长度为n的所有的所有2n个比

26、特串之间的一一对应关个比特串之间的一一对应关系。系。 建立对应关系：为每一个子集指定一个比特串建立对应关系：为每一个子集指定一个比特串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,a22022-3-7算法设计与分析-蛮力法33生成生成n个元素子集的算法如下：个元素子集的算法如下： 算法算法3.10生成子集生成子集 1初始化一个长度为初始化一个长度为n的比特串

27、的比特串s=000并将对应的子集输出；并将对应的子集输出； 2for (i=1; i2n; i+) 2.1 s+； 2.2 将将s对应的子集输出；对应的子集输出； 显然，算法显然，算法3.10的时间复杂性为的时间复杂性为O(2n)，也就，也就是说和子集的数量成正比。是说和子集的数量成正比。 2022-3-7算法设计与分析-蛮力法343.5 图问题中的蛮力法图问题中的蛮力法 3.5.1 哈密顿回路问题哈密顿回路问题 3.5.2 TSP问题问题2022-3-7算法设计与分析-蛮力法353.5.1 哈密顿回路问题哈密顿回路问题 著名的爱尔兰数学家哈密顿（著名的爱尔兰数学家哈密顿（William Ha

28、milton，18051865）提出了著名的周游世界问题。他用正十二）提出了著名的周游世界问题。他用正十二面体的面体的20个顶点代表个顶点代表20个城市，要求从一个城市出发，个城市，要求从一个城市出发，经过每个城市恰好一次，然后回到出发城市。经过每个城市恰好一次，然后回到出发城市。1983141202131545679101112161718正十二面体的展开图，正十二面体的展开图，按照图中的顶点编号所按照图中的顶点编号所构成的回路，就是哈密构成的回路，就是哈密顿回路的一个解。顿回路的一个解。 2022-3-7算法设计与分析-蛮力法36 使用蛮力法寻找哈密顿回路的基本思想是：对于使用蛮力法寻找哈

29、密顿回路的基本思想是：对于给定的无向图给定的无向图G=(V, E)，首先生成图中所有顶点的，首先生成图中所有顶点的排列对象排列对象(vi1, vi2, , vin)，然后依次考察每个排列对，然后依次考察每个排列对象是否满足以下两个条件：象是否满足以下两个条件：（1）相邻顶点之间存在边，即）相邻顶点之间存在边，即 (vij, vij+1)E（1jn-1）（2）最后一个顶点和第一个顶点之间存在边，即）最后一个顶点和第一个顶点之间存在边，即 (vin, vi1)E 满足这两个条件的回路就是哈密顿回路。满足这两个条件的回路就是哈密顿回路。目前没有有效的算法求解哈密顿回路问题目前没有有效的算法求解哈密顿

30、回路问题2022-3-7算法设计与分析-蛮力法3712453路径路径(vij, vij+1)E1234512345（是）（是）12354123 54 （否）（否）1243512 43 5 （否）（否）否否否否1245312 45 3 （否）（否）12534125 34 （否）（否）1254312543（是）（是）(vin, vi1)E是是是是是是是是(a) 一个无向图一个无向图 显然，蛮力法求解哈密顿回路在最坏情况下需要考察显然，蛮力法求解哈密顿回路在最坏情况下需要考察所有顶点的排列对象，其时间复杂性为所有顶点的排列对象，其时间复杂性为O(n!)。 例:蛮力法求解哈密顿回路(b) 哈密顿回路求

31、解过程哈密顿回路求解过程2022-3-7算法设计与分析-蛮力法383.5.2 TSP问题问题 TSP问题是指旅行家要旅行问题是指旅行家要旅行n个城市然后回到个城市然后回到出发城市，要求各个城市经历且仅经历一次，并出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人邮递员问题、售货员问题，是图问题中最广为人知的问题。知的问题。 用蛮力法解决用蛮力法解决TSPTSP问题，可以找出所有可能问题，可以找出所有可能的旅行路线，从中选取路径长度最短的简单回路。的旅行路线，从中选取路径长度

32、最短的简单回路。 2022-3-7算法设计与分析-蛮力法398abdc23571序号序号路径路径路径长度路径长度是否最短是否最短 1abcda 18 否否 2abdca 11 是是 3acbda 23 否否 4acdba 11 是是 5adbca 23 否否 6adcba 18 否否 若有若有n n个城市，则可能的解有个城市，则可能的解有( (n- -1) )!/ /2个。随着个。随着n的增长，的增长，TSP问题的可能解也在迅速地增长。问题的可能解也在迅速地增长。2022-3-7算法设计与分析-蛮力法40l 一个一个10城市的城市的TSP问题有大约有问题有大约有180,000个可能解。个可能解

33、。l 一个一个20城市的城市的TSP问题有大约有问题有大约有 60,000,000,000,000,000个可能解。个可能解。l 一个一个50城市的城市的TSP问题有大约问题有大约1062个可能解，而一个个可能解，而一个行星上也只有行星上也只有1021升水。升水。 例如：例如：u用蛮力法求解用蛮力法求解TSP问题，只能解决问题问题，只能解决问题规模很小的实例。规模很小的实例。2022-3-7算法设计与分析-蛮力法413.6 几何问题中的蛮力法几何问题中的蛮力法 3.6.1 最近对问题最近对问题3.6.2 凸包问题凸包问题2022-3-7算法设计与分析-蛮力法423.6.1 最近对问题最近对问题 最近对问题要求找出一个包含最近对问题要求找出一个包含n个点的集合个点的集合中距离最近的两个点。中距离最近的两个点。 22)()(jijiyyxxd 考虑二维情况，并假设两个点考虑二维情况，并假设两个点Pi=(xi, yi)和和Pj=(xj, yj)之间的距离是标准的欧几里德距离：之间的距离是标准的欧几里德距离：2022-3-7算法设计与分析-蛮力法43分别计算每一对点之间的距离，然后找分别计算每一对点之间的距离，然后找出距离最小的那一对，为了避免对同一出距离最小的那一对，为了避免对同一对点计算两次距离，只考虑对点计算两次距离，只考虑ij的那些的那些点对点对(Pi, Pj