天津科技大学算法设计与分析第3章蛮力法

《天津科技大学算法设计与分析第3章蛮力法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章蛮力法3.1蛮力法的设计思想3.2查找问题中的蛮力法3.3排序问题中的蛮力法3.4组合问题中的蛮力法3.5图问题中的蛮力法3.6几何问题中的蛮力法7/19/20211算法设计与分析--蛮力法3.1蛮力法的设计思想蛮力法的设计思想：直接基于问题的描述。例：计算ann次an=a×a×…×a应用实例:计算an的值是RSA算法的主要组成部分。RSA算法的加密和解密过程都需要一个整数的整数次幂再取模。7/19/20212算法设计与分析--蛮力法蛮力法所赖的基本技术——扫描技术关键——依次处理所有元素基本的扫描技术——遍历（1）集合的遍历（2）线性表的遍历（3）树的遍历（4）图

2、的遍历7/19/20213算法设计与分析--蛮力法虽然巧妙和高效的算法很少来自于蛮力法，基于以下原因，蛮力法也是一种重要的算法设计技术：（1）理论上，蛮力法可以解决可计算领域的各种问题。（2）蛮力法经常用来解决一些较小规模的问题。（3）对于一些重要的问题蛮力法可以产生一些合理的算法，他们具备一些实用价值，而且不受问题规模的限制。（4）蛮力法可以作为某类问题时间性能的底限，来衡量同样问题的更高效算法。7/19/20214算法设计与分析--蛮力法3.2查找问题中的蛮力法3.2.1顺序查找3.2.2串匹配问题7/19/20215算法设计与分析--蛮力法顺序查找从表的一端向另一端

3、逐个将元素与给定值进行比较，若相等，则查找成功，给出该元素在表中的位置；若整个表检测完仍未找到与给定值相等的元素，则查找失败，给出失败信息。3.2.1顺序查找101524612354098550123456789i查找方向7/19/20216算法设计与分析--蛮力法算法3.1——顺序查找intSeqSearch1(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{i=n;while(i>0&&r[i]!=k)i--;returni;}C++描述算法3.1的基本语句是i>0和r[i]!=k，其执行次数为:基本语句？7/19/20217算法设计与分析-

4、-蛮力法将待查值放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高了查找速度。k101524612354098550123456789i查找方向哨兵改进的顺序查找7/19/20218算法设计与分析--蛮力法算法3.2——改进的顺序查找intSeqSearch2(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{r[0]=k;i=n;while(r[i]!=k)i--;returni;}C++描述算法3.2的基本语句是r[i]!=k，其执行次数为:数量级相同，系数相差一半7/19/20219算法设计与分析--蛮力法

5、用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能，但只能减少系数，而数量级不会改变。一般观点：7/19/202110算法设计与分析--蛮力法3.2.2串匹配问题串匹配问题属于易解问题。串匹配问题的特征：（1）算法的一次执行时间不容忽视：问题规模n很大，常常需要在大量信息中进行匹配；（2）算法改进所取得的积累效益不容忽视：串匹配操作经常被调用，执行频率高。串匹配问题——给定两个串S=“s1s2…sn”和T=“t1t2…tm”，在主串S中查找子串T的过程称为串匹配，也称模式匹配。7/19/202111算法设计与分析--

6、蛮力法基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是n-m，则主串S中剩下的字符不足够匹配整个模式T，匹配失败。这个算法称为朴素的模式匹配算法，简称BF算法。蛮力法解决串匹配问题——BF算法7/19/202112算法设计与分析--蛮力法本趟匹配开始位置si……主串S模式Ttjj回溯回溯i…7/19/202113算法设计与分析--蛮力法设主串s=“ababcabcacbab

7、”，模式t=“abcacababcabcacbababci=3，j=3失败；i回溯到2，j回溯到1第1趟ijijijij7/19/202114算法设计与分析--蛮力法ababcabcacbabaijij第2趟i=2，j=1失败i回溯到3，j回溯到1第3趟ababcabcacbababcaci=7，j=5失败i回溯到4，j回溯到1ijijijijijji7/19/202115算法设计与分析--蛮力法第4趟ababcabcacbabaiji=4，j=1失败i回溯到5，j回溯到1ji第5趟ababcabcacbabijajii=5，