第蛮力法
5
章
蛮力法(bruteforcemethod,也称穷举法或枚举法), 是一种简单直接
地解决问题的方法。用蛮力法设计的算法其时间性能往往是最低的,典型
的指数时间算法一般都是通过蛮力穷举得到的。
5.概
1
述
课件5-
1
5.1.1
蛮力法的设计思想
蛮力法采用一定的策略依次处理待求解问题的所有元素,从而找出问
题的解。通常来说,蛮力法是最容易应用的方法。例如,对于给定的整数
a
和非负整数n,计算an
的值,最直接最简单的想法就是把1和
a
相乘,再
与
a
乘n-1次。
依次处理所有元素是蛮力法的关键,应用蛮力法首先要确定穷举的范
围,其次为了避免陷入重复试探,应保证处理过的元素不再被处理。由于
蛮力法需要依次穷举待处理的元素,因此,用蛮力法设计的算法其时间性
能往往是最低的。但是,基于以下原因,蛮力法也是一种重要的算法设计
技术:
(1)理论上,蛮力法可以解决可计算领域的各种问题。对于一些基本
的问题,例如求一个序列的最大元素,计算
n
个数的和等,蛮力法是一种常
用的算法设计技术。
(2)蛮力法经常用来解决一些较小规模的问题。如果问题的输入规模
不大,用蛮力法设计的算法其时间是可以接受的,此时,设计一个更高效算
法的代价是不值得的。
(3)对于一些重要的问题(如排序、查找、串匹配), 蛮力法可以设计一
些合理的算法,这些算法具有实用价值,而且不受问题规模的限制。
(4)蛮力法可以作为某类问题时间性能的下界,来衡量同样问题的其
他算法是否具有更高的效率。
54 算法设计与分析(第3 版)
5.1.2 一个简单的例子: 百元买百鸡问题
【问题】 已知公鸡5元一只,母鸡3元一只,小鸡1元三只,用100元钱买100只鸡,
问公鸡、母鸡、小鸡各多少只?
【想法】 设公鸡、母鸡和小鸡的个数分别为x、y、z,则有如下方程组成立:
{x +y +z =100
5×x +3×y +z/3=100 且
0≤x ≤20
0≤y ≤33
0≤z ≤100
ì
.
í
..
..
则百元买百鸡问题转换为求方程组的解。应用蛮力法求方程组的解只能依次试探变量
x、y 和z 的值,验证x、y 和z 的某个特定值是否能够使方程组成立。
【算法实现】 设变量x、y 和z 分别表示公鸡、母鸡和小鸡的个数,由于方程组可能
有多个解,设变量count表示解的个数,注意到小鸡1元三只,在判断总价是否满足方程
时要先判断z 是否是3的倍数。程序如下。
void Chicken( )
{
int x, y, z, count = 0;
for (x = 0; x <= 20; x++)
{
for (y = 0; y <= 33; y++)
{
z = 100 - x - y; //满足共100 只
if ((z % 3 == 0) && (5 * x + 3 * y + z/3 == 100)) //满足总价100 元
{
count++; //解的个数加1
cout<<"公鸡:"<<x<<"母鸡:"<<y<<"小鸡:"<<z<<endl;
}
}
}
if (count == 0)
cout<<"问题无解"<<endl;
}
【算法分析】 算法由两层嵌套循环组成,基本语句是条件表达式((z%3==0)&&
(5*x+3*y+z/3==100)),执行次数为21×34=714。一般地,假设共买n 只鸡,基
本语句的执行次数为n5×n3
=O(n2)。
5.2 查找问题中的蛮力法
5.2.1 顺序查找
【问题】 顺序查找(sequentialsearch)是在查找集合中依次查找值为k 的元素。若
源代码5-1
课件5-2
第5 章 蛮力法 55
查找成功,给出该元素在查找集合中的位置;若查找失败,则给出失败信息。
【想法1】 将查找集合存储在一维数组中,然后从数组的一端向另一端逐个将元素
与待查值进行比较。若相等,则查找成功,给出该元素在查找集合中的序号;若整个数组
检测完仍未找到与待查值相等的元素,则查找失败,给出失败的标志0。
【算法实现1】 将查找集合存储在数组元素r[1]~r[n]中,下标i 初始化在数组的
高端,这样查找结束时,若查找成功,下标i 的值即元素的序号,若查找失败,下标i 的值
即为失败标志0。注意,在查找过程中要检测比较位置是否越界,程序如下:
int SeqSearch1(int r[ ], int n, int k)
{
int i = n;
while (i > 0 && r[i] != k) //检测比较位置是否越界
i--;
return i;
}
【算法分析1】 算法SeqSearch1的时间主要耗费在条件表达式(i>0&&r[i]!=
k),设pi 表示查找第i 个元素的概率,等概率情况下,执行次数为:
Σn
i=1
pici =1 nΣn
i=1 (n -i+1)=n +1
2 =O(n)
【想法2】 为了避免在查找过程中每一次比较后都要判断查找位置是否越界,可以
设置观察哨(sentinel),即将待查值放在查找方向的“尽头”处,则比较位置i 至多移动到
下标0处,也就是“哨兵”的位置。改进的查找过程如图5-1所示。
图5-1 改进的顺序查找示意图
【算法实现2】 设函数SeqSearch2实现改进的顺序查找算法,程序如下:
int SeqSearch2(int r[ ], int n, int k)
{
int i = n;
r[0] = k; //设置哨兵
while (r[i] != k) //不用检测比较位置是否越界
i--;
return i;
}
源代码5-2
源代码5-3
56 算法设计与分析(第3 版)
【算法分析2】 算法SeqSearch2的时间主要耗费在条件表达式(r[i]!= k),设pi
表示查找第i 个元素的概率,等概率情况下,执行次数为:
Σn
i=1
pici =1 nΣn
i=1 (n -i+1)=n +1
2 =O(n)
顺序查找算法和其改进算法的时间复杂度都是O (n),但是算法SeqSearch1要执行
两个判断,而算法SeqSearch2只执行一个判断。实验表明,改进算法在待查找集合的长
度大于1000时,进行一次顺序查找的时间几乎减少一半。
5.2.2 串匹配问题
【问题】 给定两个字符串S 和T ,在主串S 中查找子串T 的过程称为串匹配(string
matching,也称模式匹配),T 称为模式。在文本处理系统、操作系统、编译系统、数据库
系统以及Internet信息检索系统中,串匹配是使用最频繁的操作。串匹配问题具有两个
明显的特征:①问题规模很大,常常需要在大量信息中进行匹配,因此,算法的一次执行
时间不容忽视;②匹配操作执行频率高,因此,算法改进所取得的效益因积累往往比表面
上看起来要大得多。
应用实例
在Word等文本编辑器中有这样一个功能:在“查找”对话框中输入待查找内容
(常见的是查找某个字或词),编辑器会在整个文档中进行查找,将与待查找内容相匹
配的部分高亮显示。
【想法1】 应用蛮力法解决串匹配问题的过程是:从主串S 的第一个字符开始和模
式T 的第一个字符进行比较,若相等,则继续比较二者的后续字符;若不相等,则从主串
S 的第二个字符开始和模式T 的第一个字符进行比较。重复上述过程,若T 中的字符全
部比较完毕,则说明本趟匹配成功;若S 中的字符全部比较完毕,则匹配失败。这个算法
称为朴素的模式匹配算法,简称BF算法,如图5-2所示。
图5-2 BF算法的基本思想
设主串S="abcabcacb",模式T ="abcac",BF算法的匹配过程如图5-3所示。
第5 章 蛮力法 57
图5-3 BF算法的执行过程
【算法1】 设字符数组S 存放主串,字符数组T 存放模式,BF算法如下。
算法:串匹配算法BF
输入:主串S,模式T
输出:T 在S 中的位置
1.初始化主串比较的开始位置index=0;
2.在串S 和串T 中设置比较的起始下标i=0,j=0;
3.重复下述操作,直到S 或T 的所有字符均比较完毕:
3.1如果S[i]等于T[j],则继续比较S 和T 的下一对字符;
3.2否则,下一趟匹配的开始位置index++,回溯下标i=index,j=0;
4.如果T中所有字符均比较完,则返回匹配开始位置的序号;否则返回0;
【算法分析1】 设主串S 长度为n,模式T 长度为m ,在匹配成功的情况下,考虑最
坏情况,即每趟不成功的匹配都发生在串T 的最后一个字符。
例如:S="aaaaaaaaaaab"
T ="aaab"
设匹配成功发生在si 处,则在i-1趟不成功的匹配共比较了(i-1)×m 次,第i 趟
成功的匹配共比较了m 次,所以总共比较了i×m 次,平均比较次数是:
Σ n-m+1
i=1
pi × (i×m )= Σ n-m+1
i=1
1 n -m +1× (i×m )=m (n -m +2)
2
一般情况下,m .n,因此最坏情况下的时间复杂度是O(n×m )。
【算法实现1】 设字符数组S 和T 分别存储主串和模式,程序如下。
int BF(char S[ ], char T[ ])
{
源代码5-4
58 算法设计与分析(第3 版)
int index = 0, i = 0, j = 0;
while ((S[i] != '\0') && (T[j] != '\0'))
{
if (S[i] == T[j]) {i++; j++;}
else {index++; i = index; j = 0; } //i 和j 分别回溯
}
if (T[j] == '\0') return index + 1; //返回本趟匹配开始位置的序号
else return 0;
}
【想法2】 BF算法简单但效率较低,KMP算法①对于BF算法有了很大改进,基本
思想是主串不进行回溯。
分析BF算法的执行过程,造成BF算法效率低的原因是回溯,即在某趟匹配失败后,
对于主串S 要回溯到本趟匹配开始字符的下一个字符,模式T 要回溯到第一个字符,而
这些回溯往往是不必要的。观察图5-3所示的匹配过程,在第1趟匹配过程中,S[0]~
S[3]和T[0]~T[3]匹配成功,S[4]≠T[4]匹配失败。因为在第1趟中有S[1]=T[1],
而T[0]≠T[1],因此有T[0]≠S[1],所以第2趟是不必要的,同理第3趟也是不必要的,
可以直接到第4趟。进一步分析第4趟中的第一对字符S[3]和T[0]的比较是多余的,
因为第1趟中已经比较了S[3]和T[3],并且S[3]=T[3],而T[0]=T[3],因此必有S[3]=
T[0],因此第4趟比较可以从第二对字符S[4]和T[1]开始进行,这就是说,第1趟
匹配失败后,下标i不回溯,而是将下标j回溯至第2个字符,从T[1]和S[4]开始进
行比较。
综上所述,希望某趟在S[i]和T[j]匹配失败后,下标i 不回溯,下标j 回溯至某个位
置k,从T[k]和S[i]开始进行比较。显然,关键问题是如何确定位置k。
观察部分匹配成功时的特征,某趟在S[i]和T[j]匹配失败后,下一趟比较从S[i]和
T[k]开始,则有T[0]~T[k-1]=S[i-k]~S[i-1]成立,如图5-4(a)所示;在部分匹配
成功时,有T[j-k]~T[j-1]=S[i-k]~S[i-1]成立,如图5-4(b)所示。
图5-4 部分匹配时的特征
由T[0]~T[k-1]=S[i-k]~S[i-1]和T[j-k]~T[j-1]=S[i-k]~S[i-1],
可得:
① KMP算法是克努思(Knuth)、莫里斯(Morris)和普拉特(Pratt)设计的。
第5 章 蛮力法 59
T[0]~ T[k-1]=T[j-k]~ T[j-1] (5-1)
式(5-1)说明,模式中的每一个字符T[j]都对应一个k 值,这个k 值仅依赖于模式本
身,与主串无关,且T[0]~T[k-1]是T[0]~T[j-1]的真前缀,T[j-k]~T[j-1]是
T[0]~T[j-1]的真后缀,k 是T[0]~T[j-1]的真前缀和真后缀相等的最大子串的长
度。用next[j]表示T[j]对应的k 值(0≤j<m),定义如下:
next[j]=
-1 j=0
max{k|1≤k<j且T[0]…T[k-1]=T[j-k]…T[j-1]} 集合非空
0 其他情况
ì
.
í
..
..
设模式T ="ababc",根据next[j]的定义,计算过程如下:
j=0时,next[0]=-1
j=1时,next[1]=0
j=2时,T[0]≠T[1],则next[2]=0
j=3时,T[0]T[1]≠T[1]T[2],T[0]=T[2],则next[3]=1
j=4时,T[0]T[1]T[2]≠T[1]T[2]T[3],T[0]T[1]=T[2]T[3],则next[4]=2
设主串S="ababaababcb",模式T ="ababc",模式T 的next值为{-1,0,0,1,
2},KMP算法的匹配过程如图5-5所示。
图5-5 KMP算法的执行过程
【算法2】 在求得了模式T 的next值后,KMP算法如下。
算法:串匹配算法KMP
输入:主串S,模式T
输出:T 在S 中的位置
1.在串S 和串T 中分别设置比较的起始下标i=0,j=0;
2.重复下述操作,直到S 或T 的所有字符均比较完毕:
2.1如果S[i]等于T[j],则继续比较S 和T 的下一对字符;
60 算法设计与分析(第3 版)
2.2否则,将下标j回溯到next[j]位置,即j=next[j];
2.3如果j等于-1,则将下标i和j分别加1,准备下一趟比较;
3.如果T 中所有字符均比较完毕,则返回本趟匹配开始位置的序号;否则返回0;
【算法分析2】 在求得模式T 的next值后,KMP算法只需将主串扫描一遍,设主串
的长度为n,则KMP算法的时间复杂度是O(n)。
【算法实现2】 设函数GetNext用蛮力法求得模式T 的next值,函数KMP实现
KMP算法,程序如下。
void GetNext(char T[ ], int next[ ])
{
int i, j, len;
next[0] = -1;
for (j = 1; T[j]!='\0'; j++) // 依 次求next[j]
{
for (len = j - 1; len >= 1; len--) / /相 等 子串的最大长度为j-1
{
for (i = 0; i < len; i++) // 比较T[0]~T[len-1]与T[j-len]~T[j-1]
if (T[i] != T[j-len+i]) break;
if (i == len) { next[j] = len; break;}
}
if (len < 1) next[j] = 0; // 其他情况,无相等子串
}
}i
nt KMP(char S[ ], char T[ ]) //求T 在S 中的序号
{
int i = 0, j = 0;
int next[80]; //假定模式最长为80 个字符
GetNext(T, next);
while (S[i] != '\0' && T[j] != '\0')
{
if (S[i] == T[j]) {i++; j++; }
else
{
j = next[j];
if (j == -1) {i++; j++;}
}
}
if (T[j] == '\0') return (i - j + 1); // 返 回 本趟匹配开始位置序号
else return 0;
}
源代码5-5
第5 章 蛮力法 61
5.3 排序问题中的蛮力法
5.3.1 选择排序
【问题】 选择排序(selectionsort)的基本思想是:第i 趟排序在无序序列ri~rn 中
找到值最小的记录,并和第i 个记录交换作为有序序列的第i 个记录,如图5-6所示。
图5-6 简单选择排序的基本思想图解
【想法】 图5-7给出了一个选择排序的例子(无序区用方括号括起来),具体的排序
过程如下。
(1)将整个记录序列划分为有序区和无序区,初始时有序区为空,无序区含有待排序
的所有记录。
(2)在无序区查找值最小的记录,将它与无序区的第一个记录交换,使得有序区扩展
一个记录,同时无序区减少一个记录。
(3)重复执行步骤(2),直至无序区只剩下一个记录。
图5-7 简单选择排序的过程示例
【算法实现】 设数组r[n]存储待排序记录序列,注意,数组下标从0开始,则第i个
记录存储在r[i-1]中。程序如下。
void SelectSort(int r[ ], int n)
{
int i, j, index, temp;
for (i = 0; i < n - 1; i++) //进行n-1 趟选择排序
{
index = i;
for (j = i + 1; j < n; j++) //在无序区中查找最小记录
if (r[j] < r[index]) index = j;
课件5-3
源代码5-6
62 算法设计与分析(第3 版)
temp = r[i]; r[i] = r[index]; r[index] = temp; //交换记录
}
}
【算法分析】 算法SelectSort的基本语句是内层循环体的比较语句(r[j]<r[index]),
执行次数为:
Σn-2
i=0 Σn-1
j=i+11=Σn-2
i=0 (n -i-1)=n(n -1)
2 =O(n2)
5.3.2 起泡排序
【问题】 起泡排序(bubblesort)的基本思想是:两两比较相邻记录,如果反序则交
换,直至没有反序的记录(图5.8)。
图5-8 起泡排序的基本思想图解
【想法】 图5-9给出了一个起泡排序的例子(方括号括起来的为无序区),具体的排
序过程如下。
(1)将整个待排序的记录序列划分成有序区和无序区,初始时有序区为空,无序区包
括所有待排序的记录。
(2)对无序区从前向后依次比较相邻记录,若反序则交换,从而使值较小的记录向前
移,值较大的记录向后移(像水中的气泡,体积大的先浮上来,起泡排序因而得名)。
(3)重复执行步骤(2),直至无序区没有反序的记录。
图5-9 起泡排序过程示例
【算法实现】 注意,在一趟起泡排序过程中,如果有多个记录交换到最终位置,下一
趟起泡排序将不再处理这些记录;另外,在一趟起泡排序过程中,如果没有交换记录操作,
则表明序列已经有序,算法将终止。起泡排序算法请参见2.1.1节。
【算法分析】 参见2.1.4节。