蛮力法(Brute Force)
蛮力法(brute force)是一种简单直接地解决问题的方法(暴力求解),常常直接基于问题的描述和所涉及的概念定义。
蛮力法是一种简单直接地解决问题的方法(暴力求解),常常直接基于问题的描述和所涉及的概念定义。注意,这里的“力”是指计算机的计算“能力”。一般来说,蛮力策略常常是最容易应用的办法。
虽然巧妙和高效的算法很少来自于蛮力法,但我们不应该忽略它作为一种重要的算法设计策略的地位。第一,蛮力法可以解决广阔领域的各种问题。实际上,它可能是唯一一种几乎什么问题都能解决的一般性方法。第二,对于一些重要的问题(如排序、查找、字符串匹配等)来说,蛮力法可以产生一些合理的算法。第三,如果要解决的问题实例不多,而且蛮力法可以用一种能够接受的速度对实例求解,那么设计一个更高效算法所花费的代价很可能是不值得的。第四,即使效率通常很低,仍可使用蛮力法解决一些小规模的问题实例。第五,蛮力法可以作为研究或教学目的服务,如可以以之为准绳,来衡量同样问题的更高效算法(如计算最坏时间复杂度)。
设计思想
蛮力法是指采用遍历(扫描)技术,即采用一定的策略将待求解问题的所有元素依次处理一次,从而找出问题的解。依次处理所有元素是蛮力法的关键,为了避免陷入重复试探,应保证处理过的元素不再被处理。
蛮力法本质是先有策略地穷举,然后验证。简单来说,就是列举问题所有可能的解,然后去看看是否满足题目要求,是一种逆向解题方式。(虽然不知道答案是什么,但知道答案肯定在这些范围里面,一个个试就完了。)
注意,即便是穷举,也要“聪明地”穷举。同样是穷举,也有不同的方法。
实例
接下来,将从实例出发,介绍蛮力法的具体应用。
选择排序
考虑蛮力法在排序问题中的应用,给定一个可排序的
n
n
n个元素序列,将它们按照非降序方式排列。针对这个问题,存在多种解法。这里介绍下选择排序。
选择排序在开始的时候,先扫描整个列表,以找到列表中的最小元素,然后将这个元素与第一个元素进行交换。这样最小元素就放到它的最终位置上。然后,从第二个元素开始扫描,找到n-1个元素中的最小元素,然后再与第二个元素进行交换。以此类推,直到第n-1个元素(如果前n-1个元素都已在最终位置,则最后一个元素也将在最终位置上)。更多选择排序相关介绍,参考链接。
冒泡排序
除了选择排序,蛮力法在排序算法的另一个应用是冒泡排序。冒泡排序,需要比较表中的相邻元素,如果它们是逆序的话,就交换它们的位置。重复多次之后,最终,最大的元素就"冒泡"到列表的最后一个位置。第二遍操作,将第二大元素"冒泡"到最终位置。依次执行n-1次,直到前n-1个元素到达最终位置。更多冒泡排序相关介绍,参考链接。
顺序查找
蛮力法除了在排序算法中有应用,在查找算法中也有应用。这里介绍下顺序查找算法。顺序查找的查找过程为:从表中最后一个元素开始,逐个元素进行比较,如果存在相等的元素,则查找成功。如果直至第一个元素,也没有与之相等的元素,则表明没有所查找的元素,查找不成功。当使用列表来存储元素时,为避免每次循环检查是否到达了行尾,可以将查找的元素插入行尾。更多顺序查找相关介绍,参考链接。
字符串匹配
接下来介绍蛮力法在字符串匹配问题上的应用。字符串匹配问题描述如下:给定一个n个字符组成的文本,再给定一个m个字符的子串,从文本中寻找匹配模式的子串。
使用蛮力法求解的算法描述如下:将模式对准文本的前m个字符,然后从左到右匹配每一个相应的字符,直到m个字符全部匹配或者遇到不匹配的字符。在不匹配的情况下,模式向右移动一位,然后重复匹配文本上的相应字符。这里,最坏情况下,最后一轮子串匹配的起始位置是n-m(假设下标从0开始)。该算法的伪代码实现如下:
假设数组T[0...n-1]表示待查找文本
假设数组P[0...m-1]表示待匹配子串
for i=0 to i<=n-m then
for(j=0;j<m-1;j++) then
if(T[i+j] != P[j]) then
break
if(j == m-1) then
return true
return false
该算法的输入规模是同时依赖待查找文本长度和待匹配子串。对于该非递归算法,其基本操作是内层for循环的比较操作。其最坏情况下的执行次数是:(n-m+1)*m。所以该算法的时间复杂度是KaTeX parse error: Undefined control sequence: \* at position 4: O(n\̲*̲m)。
这里给出java版本实现:
public boolean match(char[] text, char[] pattern) {
if (isEmpty(text) && isEmpty(pattern)) {
return true;
}
if (isEmpty(text) || isEmpty(pattern)) {
return false;
}
for (int i = 0; i <= text.length - pattern.length; i++) {
for (int j = 0; j < pattern.length; j++) {
if (text[i + j] - pattern[j] != 0) {
break;
}
if (j == pattern.length - 1) {
return true;
}
}
}
return false;
}
private boolean isEmpty(char[] charArray) {
if (charArray == null || charArray.length <= 0) {
return true;
}
return false;
}
深度优先查找和广度优先查找
蛮力法在图论中也有应用,如图的深度优先查找和广度优先查找。深度优先查找基本思想如下:假设初始状态时图中所有顶点都未曾被访问,则深度优先遍历算法从图中某个顶点(任一顶点)出发,访问此顶点并把该顶点标记为已访问,然后依次从该顶点邻接的未被访问的顶点出发,深度优先遍历图,直至图中所有和该顶点有路径相通的顶点都被访问到;若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作为起始点,重复上述过程,直至图中所有顶点都被访问到为止。更多深度优先查找相关介绍,参考链接。
广度优先查找基本思想如下:假设初始状态时图中所有顶点都未曾被访问,则广度优先遍历算法从图中某个顶点(任一顶点)出发,访问此顶点并依次访问该顶点的各个未曾访问过的邻接点。然后,分别从这些邻接点出发依次访问他们的临邻接点,并使"先被访问的顶点的邻接点"先于"后被访问的顶点的邻接点"被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作为起始点,重复上述过程,直至图中所有顶点都被访问到为止。换句话说,广度优先遍历的过程是以任一顶点开始,由近及远,依次访问和该顶点路径相通且路径长度为1,2,3,…的顶点。更多广度优先查找相关介绍,参考链接。
总结
蛮力法,通过使用问题规模的所有元素来求解问题,是一种穷举算法。如果问题的输入规模在一个可预估的范围内,蛮力法表现出实用性。但随着问题规模的增大,蛮力法在某些场景(如时间复杂度是指数级的蛮力法,如使用蛮力法求解的背包问题)下将不再适用。
蛮力法的一个应用是得到一个算法,此算法可以通过适度的努力来提升它的性能。也就是,蛮力法提供了一个性能提升的基准。
参考
《算法设计与分析基础》 第三版 Anany Levitin 著 潘彦 译
https://blog.csdn.net/weixin_42929607/article/details/108895699 蛮力法的基本问题分析
https://blog.csdn.net/Wwinky/article/details/115052584 算法小结之蛮力法
原创不易,如果本文对您有帮助,欢迎关注我,谢谢 ~_~
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)