---

一、蛮力法的设计思想

（一）基本概念

• 指计算机的“计算能力”，不是人的“智力”。
• 蛮力法也称穷举法或枚举法。
• 是一种简单直接地解决问题的方法，采用一定的策略依次处理待求解问题的所有元素，从而找出问题的解。
• 

（二）时间性能

• 用蛮力法设计的算法其时间性能往往也是最低的，
• 典型的指数时间算法一般都是通过蛮力穷举得到的。

（三）关键——依次处理所有元素

• 1.确定穷举范围
• 2.保证处理过的元素不再被处理（为了避免陷入重复试探）

（四）用途

• 1.理论上，蛮力法可以解决可计算领域的各种问题。
• 2.蛮力法经常用来解决一些较小规模的问题。
• 3.对于一些重要的问题（例如排序、查找等）蛮力法可以产生一些合理的算法，他们具备一些实用价值，而且不受问题规模的限制。
• 4.蛮力法可作为某类问题时间性能的上界，来衡量同样问题的其他算法是否具有更高的效率。

二、查找问题中的蛮力法

（一）顺序查找

时间复杂度：$O(n)$

（二）串匹配问题

1.问题描述

给定两个串$S=“s_0{s}_1\dots s_{n-1}”4$和$T=“t_0{t}_1\dots 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\le i\le n-1）$个记录中找到关键码最小的记录，并和第 i 个记录交换作为有序序列的第 i 个记录。
  

2.实例

3.时间复杂度

最好、最坏、平均都是$O(n^2)$

（二）冒泡排序

1.基本思想

• 冒泡排序在扫描过程中两两比较相邻记录，如果反序则交换，最终，最大记录就被移到了序列的最后一个位置，第二遍扫描将第二大记录移到了倒数第二个位置，重复上述操作，直到n-1 遍扫描后，整个序列就排好序了。

2.时间复杂度

四、图问题中的蛮力法

（一）哈密顿回路

1.问题描述

2.基本思想

3.时间复杂度

在最坏情况下需要考察所有顶点的排列对象，其时间复杂性为$O(n!)$

（二）TSP问题

1.问题描述

• TSP问题（traveling salesman problem）是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。 该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。

2.时间复杂度

蛮力法求解TSP问题必须依次考察顶点集合的所有全排列，从中找出路径长度最短的简单回路，因此其时间下界为Ω(n!) 。

---