文章目录
- 一、蛮力法的设计思想
- （一）基本概念
- （二）时间性能
- （三）关键——依次处理所有元素
- （四）用途
- 二、查找问题中的蛮力法
- （一）顺序查找
- （二）串匹配问题
- 1.问题描述
- 2.BF算法
- （1）如何实现
- （2）时间复杂度
- 3.KMP算法（改进的模式匹配算法）
- （1）BF低效原因
- （2）设计思想
- 三、排序问题中的蛮力法
- （一）选择排序
- 1.基本思想
- 2.实例
- 3.时间复杂度
- （二）冒泡排序
- 1.基本思想
- 2.时间复杂度
- 四、图问题中的蛮力法
- （一）哈密顿回路
- 1.问题描述
- 2.基本思想
- 3.时间复杂度
- （二）TSP问题
- 1.问题描述
- 2.时间复杂度
一、蛮力法的设计思想
（一）基本概念
- 指计算机的“计算能力”，不是人的“智力”。
- 蛮力法也称穷举法或枚举法。
- 是一种简单直接地解决问题的方法，采用一定的策略依次处理待求解问题的所有元素，从而找出问题的解。
（二）时间性能
- 用蛮力法设计的算法其时间性能往往也是最低的，
- 典型的指数时间算法一般都是通过蛮力穷举得到的。
（三）关键——依次处理所有元素
- 1.确定穷举范围
- 2.保证处理过的元素不再被处理（为了避免陷入重复试探）
（四）用途
- 1.理论上，蛮力法可以解决可计算领域的各种问题。
- 2.蛮力法经常用来解决一些较小规模的问题。
- 3.对于一些重要的问题（例如排序、查找等）蛮力法可以产生一些合理的算法，他们具备一些实用价值，而且不受问题规模的限制。
- 4.蛮力法可作为某类问题时间性能的上界，来衡量同样问题的其他算法是否具有更高的效率。
二、查找问题中的蛮力法
（一）顺序查找
时间复杂度：O ( n ) O(n)O(n)
（二）串匹配问题
1.问题描述
给定两个串S = “ s 0 s 1 … s n − 1 ” 4 S=“s_0s_1…s_{n-1}” 4S=“s0s1…sn−1”4和T = “ t 0 t 1 … t m − 1 ” T=“t_0t_1…t{m-1}”T=“t0t1…tm−1”，在主串 S 中查找子串 T 的过程称为串匹配，其中 T 称为模式，因而这一过程也称模式匹配。
2.BF算法
（1）如何实现
（2）时间复杂度
3.KMP算法（改进的模式匹配算法）
（1）BF低效原因
- 在每趟匹配不成功时存在大量回溯，没有利用已经部分匹配的结果。每趟匹配失败，i要回溯到本趟匹配开始字符的下一个字符，j要回溯到T的第一个字符。
（2）设计思想
- 主串 S 不进行回溯，模式 T 要回溯到某一个字符。即，让 i 不回溯，尽量利用已经得到的“部分匹配”的结果信息和模式串本身所含信息让j向右“滑动”尽可能远的一段距离后，加快模式串的滑动速度。
三、排序问题中的蛮力法
（一）选择排序
1.基本思想
- 第 i 趟排序从第 i 个记录开始扫描序列，在n – i + 1 （ 1 ≤ i ≤ n − 1 ） n – i + 1（1 ≤ i ≤ n - 1）n–i+1（1≤i≤n−1）个记录中找到关键码最小的记录，并和第 i 个记录交换作为有序序列的第 i 个记录。
2.实例
3.时间复杂度
最好、最坏、平均都是O ( n 2 ) O(n^2)O(n2)
（二）冒泡排序
1.基本思想
- 冒泡排序在扫描过程中两两比较相邻记录，如果反序则交换，最终，最大记录就被移到了序列的最后一个位置，第二遍扫描将第二大记录移到了倒数第二个位置，重复上述操作，直到n-1 遍扫描后，整个序列就排好序了。
2.时间复杂度
四、图问题中的蛮力法
（一）哈密顿回路
1.问题描述
2.基本思想
3.时间复杂度
在最坏情况下需要考察所有顶点的排列对象，其时间复杂性为O ( n ! ) O(n!)O(n!)
（二）TSP问题
1.问题描述
- TSP问题（traveling salesman problem）是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。
2.时间复杂度
蛮力法求解TSP问题必须依次考察顶点集合的所有全排列，从中找出路径长度最短的简单回路，因此其时间下界为Ω(n!) 。
