搜索
第3章蛮力法Bruteforcemethod算法设计与分析—本科生课程DesignandAnalysisofAlgorithm海南大学信息科学技术学院CollegeofInformationScienceandTechnology,HainanUniversity2算法设计技术是设计算法的一般方法，可用于解决不同计算领域的各种问题。有下列的一般方法：•蛮力法。采用一定的策略依次处理待求解问题的所有元素，从而找出问题的解。时间性能最差。•基于问题分解（求解时间与问题规模有关）的思想：•分治法。将复杂问题分解成若干独立的子问题，通过求解子问题并将解合并得到原问题的解。•减治法。同样分解问题，但只需求解某个子问题，也无须合并解，退化的分治法。•动态规划。将复杂问题分解成若干相互重叠的子问题，通过保存和重复利用重叠的子问题的解来减少计算量。•贪心法。把复杂问题分解为一系列较为简单的局部最优选择，每一步选择都是对当前解的扩展，直到获得问题的完备解。•基于搜索的思想：回溯法、分支限界法基本的算法设计技术2021/3/14Chapter3Bruteforcemethod3本章要点：3.1概述：蛮力法的设计思想3.2查找问题中的蛮力法（顺序查找、串匹配问题）3.3排序问题中的蛮力法（选择排序、起泡排序）3.4组合问题中的蛮力法（0/1背包、任务分配）3.5图问题中的蛮力法（哈密尔顿回路、TSP问题）3.6几何问题中的蛮力法（最近对、凸包问题）阅读材料——KMP算法中next值的计算第3章蛮力法2021/3/14Chapter3Bruteforcemethod4第3章蛮力法教学重点蛮力法的设计思想，各种经典问题的蛮力思想教学难点串匹配问题，凸包问题教学内容及目标知识点教学要求了解理解掌握熟练掌握蛮力法设计思想√顺序查找√串匹配问题√选择排序和起泡排序√0/1背包问题√任务分配问题√哈密尔顿回路√TSP问题√最近对问题√凸包问题√2021/3/14Chapter3Bruteforcemethod5蛮力法中“力”是指计算机的“计算能力”，不是人的智“力”。蛮力法的设计思想：直接基于问题的描述，从有限集合中，逐一列举集合的所有元素，对每一个元素逐一判断和处理，从而找出问题的解。例：计算ann次an=a×a×…×a3.1概述：蛮力法的设计思想注：最简单的想法就是把a和a相乘n次。2021/3/14Chapter3Bruteforcemethod6一个RSA算法应用实例值的计算是非对称加密算法RSA的重要组成部分。RSA的加密/解密过程都需要求一个整数的的整数次幂再取模。如已知：公钥为：KU={e,n}，私钥为：KR={d,n}，则对明文m的加密/解密算法如下：蛮力法的设计思想na加密明文：Mn密文：C=Me(modn)解密密文：C明文：M=Cd(modn)注：计算an算法的效率直接影响到RSA算法的性能2021/3/14Chapter3Bruteforcemethod7蛮力法所依赖的基本技术——遍历（扫描）技术关键——依次处理所有元素遍历技术：可确保处理过的元素不再被处理）（1）集合的遍历：按集合中元素序号的顺序处理各元素（2）线性表的遍历：以数组形式存储，按下标顺序处理（3）树的遍历：对二叉树，包括前序、中序、后序和层序（4）图的遍历：深度优先、广度优先蛮力法的设计思想2021/3/14Chapter3Bruteforcemethod8因要穷举待处理的元素，故蛮力法的时间性能往往最低，但基于以下原因，蛮力法也是一种重要的算法设计技术：（1）理论上，蛮力法可以解决可计算领域的各种问题。（2）蛮力法经常用来解决一些较小规模的问题。（3）对于一些重要的问题（例如排序、查找等）蛮力法可以产生一些合理的算法，他们具备一些实用价值，而且不受问题规模的限制。（4）蛮力法可以作为某类问题时间性能（不是复杂性，两者恰好相反）的下界，来衡量同样问题的更高效算法。蛮力法的设计思想蛮力法的设计思想例百鸡问题。“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”a：公鸡只数，b：母鸡只数，c：小鸡只数。约束方程：2021/3/149a+b+c=100(1)5a+3b+c/3=100(2)C%3=0(3)Chapter3Bruteforcemethod解法1：a、b、c的可能取值范围：0~100，对在此范围内的，a、b、c的所有组合进行测试，凡是满足上述三个约束方程的组合，都是问题的解。把问题转化为用n元钱买n只鸡，n为任意正整数，则方程（1）与（2）转换为：输入：所购买的三种鸡的总数目n输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g[],m[],s[]2021/3/1410a+b+c=n(4)5a+3b+c/3=n(5)Chapter3Bruteforcemethod蛮力法的设计思想1.voidchicken_question(intn,int&k,intg[],intm[],ints[])2.{3.inta,b,c;4.k=0;5.for(a=0;a=n;a++)6.for(b=0;b=n;b++)7.for(c=0;c=n;c++){8.if((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)){9.g[k]=a;10.m[k]=b;11.s[k]=c;12.k++;13.}14.}}}17.}2021/3/1411Chapter3Bruteforcemethod蛮力法的设计思想蛮力法的设计思想执行时间：外循环：(n+1)次，中间循环：(n+1)(n+1)次，内循环：(n+1)*(n+1)*(n+1)次。当时n=100，内循环的循环体执行次数大于100万次。2021/3/1412Chapter3Bruteforcemethod蛮力法的设计思想算法2：改进的百鸡问题.公鸡只数：0~n/5;母鸡只数：0~n/3;小鸡只数：c=n-a-b输入：所购买的三种鸡的总数目n输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g[],m[],s[]2021/3/1413Chapter3Bruteforcemethod蛮力法的设计思想1.voidchicken_problem(intn,int&k,intg[],intm[],ints[])2.{3.inti,j,a,b,c;4.k=0;5.i=n/5;6.j=n/3;7.for(a=0;a=i;a++)8.for(b=0;b=j;b++){9.c=n–a–b;10.if((5*a+3*b+c/3==n)&&(c%3==0)){11.g[k]=a;12.m[k]=b;13.s[k]=c;14.k++;15.}}}18.}2021/3/1414Chapter3Bruteforcemethod蛮力法的设计思想执行时间：外循环：n/5+1内循环：(n/5+1)*(n/3+1)当时n=100，内循环的循环体的执行次数为次:21*34=714次。对某类特定问题，在规模较小的情况下，穷举法往往是一个简单有效的方法。2021/3/1415Chapter3Bruteforcemethod蛮力法的设计思想算法的输入规模和运行时间的关系设百鸡问题的两个算法中其最内部的循环体每执行一次，需1μs时间。算法N=100时间N=10000时间算法1算法2100万次714次1s714us10000^3(10000/5+1)*(10000/3+1)11天13小时6.7秒2021/3/1416上表就是算法的执行时间随问题规模的增大而增长的情况。Chapter3Bruteforcemethod2021/3/14Chapter3Bruteforcemethod17本章要点：3.1概述：蛮力法的设计思想3.2查找问题中的蛮力法（顺序查找、串匹配问题）3.3排序问题中的蛮力法（选择排序、起泡排序）3.4组合问题中的蛮力法（0/1背包、任务分配）3.5图问题中的蛮力法（哈密尔顿回路、TSP问题）3.6几何问题中的蛮力法（最近对、凸包问题）阅读材料——KMP算法中next值的计算第3章蛮力法2021/3/14Chapter4Bruteforcemethod183.2查找问题中的蛮力法在查找问题中应用蛮力法就是依次考察待查找集合，显然这是最笨拙的查找方法。但在某些情况下（如查找集合不大）也是一种合理的方法。顺序查找从表的一端向另一端逐个将元素与给定值进行比较，若相等，则查找成功，给出该元素在表中的位置；若整个表检测完仍未找到与给定值相等的元素，则查找失败，给出失败信息。3.2.1顺序查找101524612354098550123456789i查找方向算法3.1——顺序查找intSeqSearch1(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{i=n;while(i0&&r[i]!=k)i--;returni;}算法3.1的基本语句是i0和r[i]!=k，其执行次数为:111111(1)(1)1()nnnniiiiiiiipbpcnininOnnn基本语句？3.2.1顺序查找pi为查找第i个元素的概率,bi为查找第i个元素执行的次数将待查值放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高了查找速度。k101524612354098550123456789i查找方向哨兵改进的顺序查找算法3.2——改进的顺序查找intSeqSearch2(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{r[0]=k;i=n;while(r[i]!=k)i--;returni;}算法3.2的基本语句是r[i]!=k，其执行次数为:1111(1)()2nniiiinpcniOnn数量级相同，系数相差一半改进的顺序查找用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能，但只能减少系数，而数量级不会改变。一般观点：3.2.1顺序查找2021/3/14Chapter3Bruteforcemethod24串匹配问题属于易解问题,频繁用于信息检索等。串匹配问题的特征：（1）问题规模n很大，常常需要在大量信息中进行匹配,故算法的一次执行时间不容忽视；（2）串匹配操作经常被调用，执行频率高,故算法改进所取得的积累效益不容忽视。串匹配问题——给定两个串S=“s1s2…sn”和T=“t1t2…tm”，在主串S中查找子串T的过程称为串匹配，也称模式匹配。3.2.2串匹配问题2021/3/14Chapter3Bruteforcemethod25基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是n-m+1，则主串S中剩下的字符不足够匹配整个模式T，匹配失败。这个算法称为朴素的模式匹配算法，简称BF算法。例：蛮力法解决串匹配问题——BF算法3.2.2串匹配问题ababcabcacbababc2021/3/14Chapter3Bruteforcemethod26本趟匹配开始位置si……主串S模式Ttjj回溯回溯i…查找问题中的蛮力法2021/3/14Chapter3Bruteforcemethod27设主串s=“ababcabcacbab”，模式t=“abcacababcabcacbababci=3，j=3失败；i回溯到2，j回溯到1第1趟ijijijij查找问题中的蛮力法i下标j下标2021/3/14Chapter3Bruteforcemethod28ababcabcacbabaijij第2趟i=2，j=1失败i回溯到3，j回溯到1第3趟ababcabcacbababcaci=7，j=