蛮力法(Brute Force)

蛮力法（brute force）是一种简单直接地解决问题的方法(暴力求解)，常常直接基于问题的描述和所涉及的概念定义。

夜雨风云

16103人浏览 · 2021-11-28 18:00:27

夜雨风云 · 2021-11-28 18:00:27 发布

蛮力法是一种简单直接地解决问题的方法(暴力求解)，常常直接基于问题的描述和所涉及的概念定义。注意，这里的“力”是指计算机的计算“能力”。一般来说，蛮力策略常常是最容易应用的办法。
虽然巧妙和高效的算法很少来自于蛮力法，但我们不应该忽略它作为一种重要的算法设计策略的地位。第一，蛮力法可以解决广阔领域的各种问题。实际上，它可能是唯一一种几乎什么问题都能解决的一般性方法。第二，对于一些重要的问题（如排序、查找、字符串匹配等）来说，蛮力法可以产生一些合理的算法。第三，如果要解决的问题实例不多，而且蛮力法可以用一种能够接受的速度对实例求解，那么设计一个更高效算法所花费的代价很可能是不值得的。第四，即使效率通常很低，仍可使用蛮力法解决一些小规模的问题实例。第五，蛮力法可以作为研究或教学目的服务，如可以以之为准绳，来衡量同样问题的更高效算法（如计算最坏时间复杂度）。

设计思想

蛮力法是指采用遍历（扫描）技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解。依次处理所有元素是蛮力法的关键，为了避免陷入重复试探，应保证处理过的元素不再被处理。
蛮力法本质是先有策略地穷举，然后验证。简单来说，就是列举问题所有可能的解，然后去看看是否满足题目要求，是一种逆向解题方式。（虽然不知道答案是什么，但知道答案肯定在这些范围里面，一个个试就完了。）
注意，即便是穷举，也要“聪明地”穷举。同样是穷举，也有不同的方法。

实例

接下来，将从实例出发，介绍蛮力法的具体应用。

选择排序

考虑蛮力法在排序问题中的应用，给定一个可排序的 $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，…的顶点。更多广度优先查找相关介绍，参考链接。

总结

蛮力法，通过使用问题规模的所有元素来求解问题，是一种穷举算法。如果问题的输入规模在一个可预估的范围内，蛮力法表现出实用性。但随着问题规模的增大，蛮力法在某些场景(如时间复杂度是指数级的蛮力法，如使用蛮力法求解的背包问题)下将不再适用。
蛮力法的一个应用是得到一个算法，此算法可以通过适度的努力来提升它的性能。也就是，蛮力法提供了一个性能提升的基准。