《第3章-蛮力法详解优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第3章-蛮力法详解优秀PPT.ppt（95页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第3章 蛮力法 Brute force method算法设计与分析算法设计与分析算法设计与分析算法设计与分析本科本科本科本科生课程生课程生课程生课程Design and Analysis of AlgorithmDesign and Analysis of Algorithm海南高校信息科学技术学院海南高校信息科学技术学院College of Information Science and College of Information Science and Technology,Hainan UniversityTechnology,Hainan University2 2算法设计技术是设计
2、算法的一般方法，可用于解决不同计算领域的各算法设计技术是设计算法的一般方法，可用于解决不同计算领域的各种问题。有下列的一般方法：种问题。有下列的一般方法：蛮力法。接受确定的策略依次处理待求解问题的全部元素，从而找出蛮力法。接受确定的策略依次处理待求解问题的全部元素，从而找出问题的解。时间性能最差。问题的解。时间性能最差。基于问题分解（求解时间与问题规模有关）的思想：基于问题分解（求解时间与问题规模有关）的思想：分治法。将困难问题分解成若干独立的子问题，通过求解子问题并将分治法。将困难问题分解成若干独立的子问题，通过求解子问题并将解合并得到原问题的解。解合并得到原问题的解。减治法。同样分解问题，
3、但只需求解某个子问题，也无须合并解，退减治法。同样分解问题，但只需求解某个子问题，也无须合并解，退化的分治法。化的分治法。动态规划。将困难问题分解成若干相互重叠的子问题，通过保存和重动态规划。将困难问题分解成若干相互重叠的子问题，通过保存和重复利用重叠的子问题的解来削减计算量。复利用重叠的子问题的解来削减计算量。贪心法。把困难问题分解为一系列较为简洁的局部最优选择，每一步贪心法。把困难问题分解为一系列较为简洁的局部最优选择，每一步选择都是对当前解的扩展，直到获得问题的完备解。选择都是对当前解的扩展，直到获得问题的完备解。基于搜寻的思想：回溯法、分支限界法基于搜寻的思想：回溯法、分支限界法基本的
4、算法设计技术基本的算法设计技术2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force method3 3本章要点：本章要点：3.13.1概述：蛮力法的设计思想概述：蛮力法的设计思想概述：蛮力法的设计思想概述：蛮力法的设计思想 3.23.2查找问题中的蛮力法（依次查找、串匹配问题）查找问题中的蛮力法（依次查找、串匹配问题）查找问题中的蛮力法（依次查找、串匹配问题）查找问题中的蛮力法（依次查找、串匹配问题）3.33.3排序问题中的蛮力法（选择排序、起泡排序）排序问题中的蛮力法（选择排序、起泡排序）排序问题中的蛮力法（选
5、择排序、起泡排序）排序问题中的蛮力法（选择排序、起泡排序）3.43.4组合问题中的蛮力法（组合问题中的蛮力法（组合问题中的蛮力法（组合问题中的蛮力法（0/10/1背包、任务安排）背包、任务安排）背包、任务安排）背包、任务安排）3.53.5图问题中的蛮力法（哈密尔顿回路、图问题中的蛮力法（哈密尔顿回路、图问题中的蛮力法（哈密尔顿回路、图问题中的蛮力法（哈密尔顿回路、TSPTSP问题）问题）问题）问题）3.63.6几何问题中的蛮力法（最近对、凸包问题）几何问题中的蛮力法（最近对、凸包问题）几何问题中的蛮力法（最近对、凸包问题）几何问题中的蛮力法（最近对、凸包问题）阅读材料阅读材料阅读材料阅读材料K
6、MPKMP算法中算法中算法中算法中nextnext值的计算值的计算值的计算值的计算第第3章章 蛮力法蛮力法2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force method4 4第第3章章 蛮力法蛮力法教学重点蛮力法的设计思想，各种经典问题的蛮力思想教学难点串匹配问题，凸包问题教学内容及目标知识点教学要求了解理解掌握熟练掌握蛮力法设计思想顺序查找串匹配问题选择排序和起泡排序0/1背包问题任务分配问题哈密尔顿回路TSP问题最近对问题凸包问题2022/11/52022/11/5Chapter 3 Brute forc
7、e methodChapter 3 Brute force method5 5蛮力法中蛮力法中蛮力法中蛮力法中“力力力力”是指计算机的是指计算机的是指计算机的是指计算机的“计算实力计算实力计算实力计算实力”，不是人的智，不是人的智，不是人的智，不是人的智“力力力力”。蛮力法的设计思想：干脆基于问题的描述，蛮力法的设计思想：干脆基于问题的描述，蛮力法的设计思想：干脆基于问题的描述，蛮力法的设计思想：干脆基于问题的描述，从有限集合中，逐一列举集合的全部元素，从有限集合中，逐一列举集合的全部元素，从有限集合中，逐一列举集合的全部元素，从有限集合中，逐一列举集合的全部元素，对每一个元素逐一推断和处理，
8、从而找出问对每一个元素逐一推断和处理，从而找出问对每一个元素逐一推断和处理，从而找出问对每一个元素逐一推断和处理，从而找出问题的解。题的解。题的解。题的解。例：计算例：计算例：计算例：计算anann n次次a an n=a a a aa a3.1 概述：蛮力法的设计思想概述：蛮力法的设计思想注：最简洁的想法就是把注：最简洁的想法就是把注：最简洁的想法就是把注：最简洁的想法就是把 a a 和和和和 a a 相乘相乘相乘相乘 n n 次。次。次。次。2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force method6
9、 6 一个RSA算法应用实例 值的计算是非对称加密算法RSA的重要组成部分。RSA的加密/解密过程都须要求一个整数的的整数次幂再取模。如已知：公钥为：KU=e,n，私钥为：KR=d,n，则对明文m的加密/解密算法如下：蛮力法的设计思想蛮力法的设计思想加密加密加密加密明文：明文：明文：明文：MnMn密文：密文：密文：密文：C=MC=Me e(mod n)(mod n)解密解密解密解密密文：密文：密文：密文：C C明文：明文：明文：明文：M=CM=Cd d(mod n)(mod n)注：计算注：计算注：计算注：计算anan算法的效率干脆影响到算法的效率干脆影响到算法的效率干脆影响到算法的效率干脆影
10、响到RSARSA算法的性能算法的性能算法的性能算法的性能2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force method7 7n n 蛮力法所依靠的基本技术蛮力法所依靠的基本技术蛮力法所依靠的基本技术蛮力法所依靠的基本技术遍历（扫描）技术遍历（扫描）技术遍历（扫描）技术遍历（扫描）技术n n 关键关键关键关键依次处理全部元素依次处理全部元素依次处理全部元素依次处理全部元素n n遍历技术：可确保处理过的元素不再被处理）遍历技术：可确保处理过的元素不再被处理）遍历技术：可确保处理过的元素不再被处理）遍历技术：可确保
11、处理过的元素不再被处理）n n（1 1）集合的遍历：按集合中元素序号的依次处理）集合的遍历：按集合中元素序号的依次处理）集合的遍历：按集合中元素序号的依次处理）集合的遍历：按集合中元素序号的依次处理各元素各元素各元素各元素n n（2 2）线性表的遍历：以数组形式存储，按下标依）线性表的遍历：以数组形式存储，按下标依）线性表的遍历：以数组形式存储，按下标依）线性表的遍历：以数组形式存储，按下标依次处理次处理次处理次处理n n（3 3）树的遍历：对二叉树，包括前序、中序、后）树的遍历：对二叉树，包括前序、中序、后）树的遍历：对二叉树，包括前序、中序、后）树的遍历：对二叉树，包括前序、中序、后序和层
12、序序和层序序和层序序和层序n n（4 4）图的遍历：深度优先、广度优先）图的遍历：深度优先、广度优先）图的遍历：深度优先、广度优先）图的遍历：深度优先、广度优先蛮力法的设计思想蛮力法的设计思想2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force method8 8因要穷举待处理的元素，故蛮力法的时间性能往往最低，因要穷举待处理的元素，故蛮力法的时间性能往往最低，因要穷举待处理的元素，故蛮力法的时间性能往往最低，因要穷举待处理的元素，故蛮力法的时间性能往往最低，但基于以下缘由，蛮力法也是一种重要的算法设计技术：但基
13、于以下缘由，蛮力法也是一种重要的算法设计技术：但基于以下缘由，蛮力法也是一种重要的算法设计技术：但基于以下缘由，蛮力法也是一种重要的算法设计技术：（1 1）理论上，蛮力法可以解决可计算领域的各种问题。）理论上，蛮力法可以解决可计算领域的各种问题。）理论上，蛮力法可以解决可计算领域的各种问题。）理论上，蛮力法可以解决可计算领域的各种问题。（2 2）蛮力法常常用来解决一些较小规模的问题。）蛮力法常常用来解决一些较小规模的问题。）蛮力法常常用来解决一些较小规模的问题。）蛮力法常常用来解决一些较小规模的问题。（3 3）对对对对于于于于一一一一些些些些重重重重要要要要的的的的问问问问题题题题（例例例例如
14、如如如排排排排序序序序、查查查查找找找找等等等等）蛮蛮蛮蛮力力力力法法法法可可可可以以以以产产产产生生生生一一一一些些些些合合合合理理理理的的的的算算算算法法法法，他他他他们们们们具具具具备备备备一一一一些些些些好好好好用用用用价价价价值值值值，而而而而且且且且不受问题规模的限制。不受问题规模的限制。不受问题规模的限制。不受问题规模的限制。（4 4）蛮蛮蛮蛮力力力力法法法法可可可可以以以以作作作作为为为为某某某某类类类类问问问问题题题题时时时时间间间间性性性性能能能能（不不不不是是是是困困困困难难难难性性性性，两者恰好相反）的下界，来衡量同样问题的更高效算法。两者恰好相反）的下界，来衡量同样问
15、题的更高效算法。两者恰好相反）的下界，来衡量同样问题的更高效算法。两者恰好相反）的下界，来衡量同样问题的更高效算法。蛮力法的设计思想蛮力法的设计思想蛮力法的设计思想蛮力法的设计思想n n例例例例 百鸡问题。百鸡问题。“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？一。百钱买百鸡，问鸡翁、母、雏各几何？”a a：公鸡只数，：公鸡只数，b b：母鸡只数，：母鸡只数，c c：小鸡只数。：小鸡只数。约束方程：约束方程：约束方程：约束方程：2022/11/52022/11/59 9a+b+c=100 (1)a+b+c=100
16、 (1)5a+3b+c/3=100 (2)5a+3b+c/3=100 (2)C%3=0 (3)C%3=0 (3)Chapter 3 Brute force methodChapter 3 Brute force methodn n解法解法1 1：n na a、b b、c c的可能取值范围：的可能取值范围：0 1000 100，对在此范围，对在此范围内的，内的，a a、b b、c c的全部组合进行测试，凡是满足上的全部组合进行测试，凡是满足上述三个约束方程的组合，都是问题的解。述三个约束方程的组合，都是问题的解。n n把问题转化为用把问题转化为用n n元钱买元钱买n n只鸡，只鸡，n n为随意正
17、整数，为随意正整数，则方程（则方程（1 1）与（）与（2 2）转换为：）转换为：n n输入：所购买的三种鸡的总数目输入：所购买的三种鸡的总数目n nn n输出：满足问题的解的数目输出：满足问题的解的数目k,k,公鸡公鸡,母鸡母鸡,小鸡的只小鸡的只数数g,m,s g,m,s 2022/11/52022/11/51010a+b+c=n (4)a+b+c=n (4)5a+3b+c/3=n (5)5a+3b+c/3=n (5)Chapter 3 Brute force methodChapter 3 Brute force method蛮力法的设计思想蛮力法的设计思想1.1.void chicken_
18、question(int n,int&k,int g,int m,int s)void chicken_question(int n,int&k,int g,int m,int s)2.2.3.int a,b,c;3.int a,b,c;4.k=0;4.k=0;5.for(a=0;a=n;a+)5.for(a=0;a=n;a+)6.for(b=0;b=n;b+)6.for(b=0;b=n;b+)7.for(c=0;c=n;c+)7.for(c=0;c=n;c+)8.8.if(a+b+c=n)&(5*a+3*b+c/3=n)&(c%3=0)if(a+b+c=n)&(5*a+3*b+c/3=n)&
19、(c%3=0)9.gk=a;9.gk=a;10.mk=b;10.mk=b;11.sk=c;11.sk=c;12.k+;12.k+;13.13.14.14.17.17.2022/11/52022/11/51111Chapter 3 Brute force methodChapter 3 Brute force method蛮力法的设计思想蛮力法的设计思想蛮力法的设计思想蛮力法的设计思想n n执行时间：执行时间：n n外循环：外循环：(n+1)(n+1)次，次，n n中间循环：中间循环：(n+1)(n+1)(n+1)(n+1)次，次，n n内循环：内循环：(n+1)*(n+1)*(n+1)(n+1
20、)*(n+1)*(n+1)次。次。当时当时n=100n=100，内循环的循环体执行次数大于，内循环的循环体执行次数大于100100万次。万次。2022/11/52022/11/51212Chapter 3 Brute force methodChapter 3 Brute force method蛮力法的设计思想蛮力法的设计思想n n算法2：改进的百鸡问题.n n公鸡只数：0n/5;n n母鸡只数：0n/3;n n小鸡只数：c=n-a-bn n输入：所购买的三种鸡的总数目nn n输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g,m,s2022/11/52022/11/51313Chapte
21、r 3 Brute force methodChapter 3 Brute force method蛮力法的设计思想蛮力法的设计思想1.void chicken_problem(int n,int&k,int g,int m,int s)1.void chicken_problem(int n,int&k,int g,int m,int s)2.2.3.int3.int i,j,a,b,c;i,j,a,b,c;4.k=0;4.k=0;5.i=n/5;5.i=n/5;6.j=n/3;6.j=n/3;7.for(a=0;a=i;a+)7.for(a=0;a=i;a+)8.for(b=0;b=j;b
22、+)8.for(b=0;b0&ri!=ki0&ri!=k)i i-;return i;return i;C+描述算法算法算法算法3.13.1的的的的基本语句基本语句基本语句基本语句是是是是i0i0和和和和ri!=kri!=k，其执行次数为，其执行次数为，其执行次数为，其执行次数为:基本语句基本语句基本语句基本语句？3.2.1依次查找依次查找p pi i为查找第为查找第i i个元素的概率个元素的概率,b,bi i为查找第为查找第i i个元素执行的次数个元素执行的次数将待查值放在查找方向的终点处，免去了在查找过将待查值放在查找方向的终点处，免去了在查找过将待查值放在查找方向的终点处，免去了在查找过
23、将待查值放在查找方向的终点处，免去了在查找过程中每一次比较后都要推断查找位置是否越界，从程中每一次比较后都要推断查找位置是否越界，从程中每一次比较后都要推断查找位置是否越界，从程中每一次比较后都要推断查找位置是否越界，从而提高了查找速度。而提高了查找速度。而提高了查找速度。而提高了查找速度。k 10 15 24 6 12 35 40 98 55k 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 i i查找方向查找方向查找方向查找方向哨兵哨兵哨兵哨兵改进的依次查找改进的依次查找算法算法3.23.2改进的顺序查找改进
24、的顺序查找 intSeqSearch2(intr,intn,intk)intSeqSearch2(intr,intn,intk)/数组数组数组数组r1rnr1rn存放查找集合存放查找集合存放查找集合存放查找集合 r0=k;i=n;r0=k;i=n;while(ri!=k)while(ri!=k)i-;i-;returni;returni;C+描述算法算法3.23.2的的基本语句基本语句是是ri!=kri!=k，其执行次数为，其执行次数为:数量级相同，数量级相同，系数相差一半系数相差一半改进的依次查找改进的依次查找 用蛮力法设计的算法，一般来说，经过适度的努力后，用蛮力法设计的算法，一般来说，经
25、过适度的努力后，都可以对算法的第一个版本进行确定程度的改良，改进其时都可以对算法的第一个版本进行确定程度的改良，改进其时间性能，但只能削减系数，而数量级不会变更。间性能，但只能削减系数，而数量级不会变更。v 一般观点：一般观点：3.2.1依次查找依次查找2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force method2424n n 串匹配问题属于易解问题串匹配问题属于易解问题,频繁用于信息检索等。频繁用于信息检索等。n n 串匹配问题的特征：串匹配问题的特征：n n（1 1）问题规模）问题规模 n n 很大，常
26、常须要在大量信息中很大，常常须要在大量信息中进行匹配进行匹配,故算法的一次执行时间不容忽视；故算法的一次执行时间不容忽视；n n（2 2）串匹配操作常常被调用，执行频率高）串匹配操作常常被调用，执行频率高,故算故算法改进所取得的积累效益不容忽视。法改进所取得的积累效益不容忽视。串匹配问题串匹配问题串匹配问题串匹配问题给定两个串给定两个串给定两个串给定两个串S S=“=“s s1 1s s2 2s sn n”和和和和T T=“=“t t1 1t t2 2t tmm”，在，在，在，在主串主串主串主串S S中查找子串中查找子串中查找子串中查找子串T T的过程称为的过程称为的过程称为的过程称为串匹配串
27、匹配串匹配串匹配，也称模式匹配。，也称模式匹配。，也称模式匹配。，也称模式匹配。3.2.2串匹配问题串匹配问题2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force method2525 基基本本思思想想：从从主主串串S S的的第第一一个个字字符符起起先先和和模模式式T T的的第第一一个个字字符符进进行行比比较较，若若相相等等，则则接接着着比比较较两两者者的的后后续续字字符符；若若不不相相等等，则则从从主主串串S S的的其其次次个个字字符符起起先先和和模模式式T T的的第第一一个个字字符符进进行行比比较较，重重复复
28、上上述述过过程程，若若T T中中的的字字符符全全部部比比较较完完毕毕，则则说说明明本本趟趟匹匹配配成成功功；若若最最终终一一轮轮匹匹配配的的起起始始位位置置是是n-m+1n-m+1，则则主主串串S S中中剩剩下下的的字字符符不不足足够够匹匹配配整整个个模模式式T T，匹匹配配失失败败。这这个个算法称为朴实的模式匹配算法，简称算法称为朴实的模式匹配算法，简称BFBF算法。算法。例：蛮力法解决串匹配问题例：蛮力法解决串匹配问题例：蛮力法解决串匹配问题例：蛮力法解决串匹配问题BFBF算法算法算法算法3.2.2串匹配问题串匹配问题 ababcabcacbabababcabcacbababcabc202
29、2/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force method2626本趟匹配起先位置本趟匹配起先位置本趟匹配起先位置本趟匹配起先位置si主串主串主串主串S S模式模式模式模式T Ttjj j 回溯回溯回溯回溯 回溯回溯回溯回溯i i查找问题中的蛮力法查找问题中的蛮力法 2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force method2727设设设设主串主串主串主串s=“ababcabcacbab”s=“ababcabcacbab”
30、，模式模式模式模式t=“abcact=“abcacababcabcacbabababcabcacbababcabci=3i=3，j=3j=3失败；失败；失败；失败；i i回溯到回溯到回溯到回溯到2 2，j j回溯到回溯到回溯到回溯到1 1第第第第1 1趟趟趟趟i ij ji ij ji ij ji ij j查找问题中的蛮力法查找问题中的蛮力法 i i下标下标下标下标j j下标下标下标下标2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force method2828ababcabcacbabababcabcacbaba
31、 ai ij ji ij j第第第第2 2趟趟趟趟i=2i=2，j=1j=1失败失败失败失败i i回溯到回溯到回溯到回溯到3 3，j j回溯到回溯到回溯到回溯到1 1第第第第3 3趟趟趟趟ababcabcacbabababcabcacbababcacabcaci=7i=7，j=5j=5失败失败失败失败i i回溯到回溯到回溯到回溯到4 4，j j回溯到回溯到回溯到回溯到1 1i ij ji ij ji ij ji ij ji ij jj ji i查找问题中的蛮力法查找问题中的蛮力法 2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 B
32、rute force method2929第第第第4 4趟趟趟趟ababcabcacbabababcabcacbaba ai ij ji=4i=4，j=1j=1失败失败失败失败i i回溯到回溯到回溯到回溯到5 5，j j回溯到回溯到回溯到回溯到1 1j ji i第第第第5 5趟趟趟趟ababcabcacbabababcabcacbabi ij ja aj ji ii=5i=5，j=1j=1失败失败失败失败i i回溯到回溯到回溯到回溯到6 6，j j回溯到回溯到回溯到回溯到1 1查找问题中的蛮力法查找问题中的蛮力法 2022/11/52022/11/5Chapter 3 Brute force
33、methodChapter 3 Brute force method3030第第第第6 6趟趟趟趟ababcabcacbababcaci=11i=11，j=6j=6，模式，模式，模式，模式t t中全部字符都比较完毕，匹配成功。中全部字符都比较完毕，匹配成功。中全部字符都比较完毕，匹配成功。中全部字符都比较完毕，匹配成功。i ij ji ij ji ij ji ij ji ij ji ij j查找问题中的蛮力法查找问题中的蛮力法 2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force method3131intBFi
34、ntBF(charS,charTcharS,charT)inti=0,j=0,index=0inti=0,j=0,index=0whilewhile(iS.length&jT.lengthiS.length&jT.length)ifif(Si=TjSi=Tj)i+;j+;i+;j+;elseelsei=+index;j=0i=+index;j=0;ifif(j=T.lengthj=T.length)returnindex+1;returnindex+1;elsereturn0;elsereturn0;BFC+算算法法查找问题中的蛮力法查找问题中的蛮力法 2022/11/52022/11/5Ch
35、apter 3 Brute force methodChapter 3 Brute force method3232设串设串设串设串S S S S长度为长度为长度为长度为n n n n，串，串，串，串T T T T长度为长度为长度为长度为m m m m，在匹配成功的状况下，考虑最坏，在匹配成功的状况下，考虑最坏，在匹配成功的状况下，考虑最坏，在匹配成功的状况下，考虑最坏状况，即每趟不成功的匹配都发生在串状况，即每趟不成功的匹配都发生在串状况，即每趟不成功的匹配都发生在串状况，即每趟不成功的匹配都发生在串T T T T的最终一个字符。的最终一个字符。的最终一个字符。的最终一个字符。例如：例如：例
36、如：例如：S=aaaaaaaaaaabS=aaaaaaaaaaabT=aaabT=aaab设设设设匹匹匹匹配配配配成成成成功功功功发发发发生生生生在在在在si si处处处处，则则则则在在在在i-1i-1趟趟趟趟不不不不成成成成功功功功的的的的匹匹匹匹配配配配中中中中共共共共比比比比较较较较了了了了(i-(i-1)m1)m次次次次，第第第第i i趟趟趟趟成成成成功功功功的的的的匹匹匹匹配配配配共共共共比比比比较较较较了了了了mm次次次次，所所所所以以以以总总总总共共共共比比比比较较较较了了了了imim次，因此平均比较次数是：次，因此平均比较次数是：次，因此平均比较次数是：次，因此平均比较次数是：
37、查找问题中的蛮力法查找问题中的蛮力法 2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force method3333改进的串匹配算法改进的串匹配算法KMP算法算法KMPKnuthKMPKnuth、MorrisMorris和和和和PrattPrattBFBF低效缘由低效缘由低效缘由低效缘由:每趟匹配失败每趟匹配失败每趟匹配失败每趟匹配失败,i,i要回溯到本趟匹配起先要回溯到本趟匹配起先要回溯到本趟匹配起先要回溯到本趟匹配起先字符的下一个字符字符的下一个字符字符的下一个字符字符的下一个字符,j,j要回溯到第一个字符要回溯
38、到第一个字符要回溯到第一个字符要回溯到第一个字符.设计思想：让设计思想：让设计思想：让设计思想：让ii不回溯，尽量利用已经得到的不回溯，尽量利用已经得到的不回溯，尽量利用已经得到的不回溯，尽量利用已经得到的“部分部分部分部分匹配匹配匹配匹配”的结果信息将的结果信息将的结果信息将的结果信息将j j向右向右向右向右“滑动滑动滑动滑动”尽可能远的一段距尽可能远的一段距尽可能远的一段距尽可能远的一段距离后，加快模式串的滑动速度。离后，加快模式串的滑动速度。离后，加快模式串的滑动速度。离后，加快模式串的滑动速度。查找问题中的蛮力法查找问题中的蛮力法 2022/11/52022/11/5Chapter 3
39、 Brute force methodChapter 3 Brute force method3434ababcabcacbabababcabcacbababcacabcaci=3i=3，j=3j=3失败；失败；失败；失败；第第第第1 1趟趟趟趟i ii ii ij jababcabcacbabababcabcacbabaai ij j第第第第2 2趟趟趟趟没必要比较没必要比较没必要比较没必要比较s s2 2=t=t2 2;t;t1 1tt2 2t t1 1ss2 2j jj j查找问题中的蛮力法查找问题中的蛮力法 2022/11/52022/11/5Chapter 3 Brute force
40、 methodChapter 3 Brute force method3535第第第第3 3趟趟趟趟ababcabcacbabababcabcacbababcacabcaci=7i=7，j=5j=5失败失败失败失败i ij ji ij ji ij ji ij ji ij j第第第第4 4趟趟趟趟ababcabcacbabababcabcacbaba ai ij j没必要比较没必要比较没必要比较没必要比较s s4 4=t=t2 2;t;t1 1tt2 2t t1 1ss4 42022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute
41、 force method3636第第第第5 5趟趟趟趟ababcabcacbabababcabcacbabi ij ja a没必要比较没必要比较没必要比较没必要比较s s5 5=t=t3 3;t;t1 1tt3 3t t1 1ss5 5第第第第6 6趟趟趟趟ababcabcacbabababcabcacbababcaci=11i=11，j=6j=6，t t中中中中全全全全部部部部字字字字符符符符都比较完毕，匹配成功。都比较完毕，匹配成功。都比较完毕，匹配成功。都比较完毕，匹配成功。i ij ji ij ji ij ji ij ji ij j2022/11/52022/11/5Chapter
42、3 Brute force methodChapter 3 Brute force method3737须要探讨两个问题：须要探讨两个问题：须要探讨两个问题：须要探讨两个问题：如何由当前部分匹配结果确定模式如何由当前部分匹配结果确定模式如何由当前部分匹配结果确定模式如何由当前部分匹配结果确定模式T T向右向右向右向右滑动的新比较起点滑动的新比较起点滑动的新比较起点滑动的新比较起点k k？模式模式模式模式T T应当向右滑多远才是最高效率的应当向右滑多远才是最高效率的应当向右滑多远才是最高效率的应当向右滑多远才是最高效率的?结论：结论：结论：结论：i i可以不回溯，模式可以不回溯，模式可以不回溯，
43、模式可以不回溯，模式T T向右滑动到的新向右滑动到的新向右滑动到的新向右滑动到的新比较比较比较比较起点起点起点起点k k（j j回溯到回溯到回溯到回溯到k k），并且，并且，并且，并且kk仅与模式串仅与模式串仅与模式串仅与模式串T T有关！有关！有关！有关！查找问题中的蛮力法查找问题中的蛮力法 2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force method3838抓住部分匹配时的两个特征：抓住部分匹配时的两个特征：抓住部分匹配时的两个特征：抓住部分匹配时的两个特征：S=S=abababababab b b c
44、acbabcacbab abab ababc ci i（1）设模式滑动到第）设模式滑动到第k个字符，则个字符，则T T1 1T Tk k-1-1 S Si i-(-(k k-1)-1)Si i-1-1(不用比较不用比较)j jS=ababS=ababababb bcacbabcacbababab ababc ci ik kk k查找问题中的蛮力法查找问题中的蛮力法（2）则）则Tj-(k-1)Tj-1S Si i-(-(k k-1)-1)Si i-1-1两式联立可得：两式联立可得：T T1 1T Tk k-1-1T Tj j-(-(k k-1)-1)T Tj j-1-1j j2022/11/52
45、022/11/5Chapter 3 Brute force methodChapter 3 Brute force method3939查找问题中的蛮力法查找问题中的蛮力法 T1Tk-1T1Tk-1Tj-(k-1)Tj-1Tj-(k-1)Tj-1说明白什么？说明白什么？说明白什么？说明白什么？（1 1）kk与与与与jj具有函数关系，由当前失配位置具有函数关系，由当前失配位置具有函数关系，由当前失配位置具有函数关系，由当前失配位置jj，可，可，可，可以计算出滑动位置以计算出滑动位置以计算出滑动位置以计算出滑动位置kk（即比较的新起点）；（即比较的新起点）；（即比较的新起点）；（即比较的新起点）；
46、（2 2）滑动位置）滑动位置）滑动位置）滑动位置kk仅与模式串仅与模式串仅与模式串仅与模式串T T有关。有关。有关。有关。从第从第从第从第1 1位往右位往右位往右位往右经过经过经过经过k-1k-1位位位位从从从从j-1j-1位往左位往左位往左位往左经过经过经过经过k-1k-1位位位位T T1 1TTk k-1-1T Tj j-(-(k k-1)-1)TTj j-1-1的物理意义是什么？的物理意义是什么？的物理意义是什么？的物理意义是什么？真前缀真前缀真后缀真后缀2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force
47、 method4040nextjnextj00当当当当j j1 1时时时时/不比较不比较不比较不比较maxk|1kjmaxk|1kj且且且且T1Tk-1=Tj-(k-1)Tj-1T1Tk-1=Tj-(k-1)Tj-111其他状况其他状况其他状况其他状况令令令令k=nextjk=nextj，则：，则：，则：，则：t t1 1 t t22t t33t t44t t5 5 t t6 6a b a b a b aa b a c c真前缀真前缀真前缀真前缀真后缀真后缀真后缀真后缀假设假设假设假设j=6j=6t t1 1=t t5 5,t t1 1t t2 2t t3 3=t t3 3t t4 4t t5
48、 5a a和和和和abaaba都是都是都是都是ababaababa的真前缀和真后缀，的真前缀和真后缀，的真前缀和真后缀，的真前缀和真后缀，但但但但abaaba的长度最大的长度最大的长度最大的长度最大next6=3+1=4next6=3+1=4即当即当即当即当t t6 6和和和和s si i匹配失败后，匹配失败后，匹配失败后，匹配失败后，k=4k=4，将，将，将，将t t4 4和和和和s si i进行比较进行比较进行比较进行比较查找问题中的蛮力法查找问题中的蛮力法 k kmaxmaxk k|1|1k k j j 且且且且T T1 1TTk k-1-1T Tj j-(-(k k-1)-1)TTj
49、j-1-1 模式应该向右滑多远模式应该向右滑多远模式应该向右滑多远模式应该向右滑多远(k=?)(k=?)才是最高效率的才是最高效率的才是最高效率的才是最高效率的?2022/11/52022/11/5Chapter 3 Brute force methodChapter 3 Brute force method4141nextjnextj函数表征着模式函数表征着模式函数表征着模式函数表征着模式T T中最大相同真前缀和真后缀的长中最大相同真前缀和真后缀的长中最大相同真前缀和真后缀的长中最大相同真前缀和真后缀的长度。可见，模式中相像部分越多，则度。可见，模式中相像部分越多，则度。可见，模式中相像部分
50、越多，则度。可见，模式中相像部分越多，则nextjnextj函数越大，模式串函数越大，模式串函数越大，模式串函数越大，模式串向右滑动得越远（向右滑动得越远（向右滑动得越远（向右滑动得越远（k k往后越远），与主串进行比较的次数越少往后越远），与主串进行比较的次数越少往后越远），与主串进行比较的次数越少往后越远），与主串进行比较的次数越少（m-km-k），时间困难度就越低。），时间困难度就越低。），时间困难度就越低。），时间困难度就越低。查找问题中的蛮力法查找问题中的蛮力法 由模式由模式由模式由模式T T定义知定义知定义知定义知:next1=0:next1=0设设设设已已已已算算算算出出出出ne