暴力搜索

  此条目介绍的是计算机科学中的搜索算法。关于数学中的穷举证明法，请见“穷举法”。关于密码学中的暴力破解法，请见“蛮力攻击”。

暴力搜索或穷举搜索，在计算机科学中也称生成与测试是一种非常低效的解决问题的技术，方法包括了系统地枚举解决方案的所有可能候选项以及检查每个候选项是否符合问题描述。

找出自然数n的约数的暴力搜索算法将枚举出从1到n的所有整数，并检查它们中的每一个是否除n后没有余数。针对八皇后问题的暴力搜索算法会检查所有在8X8棋盘上八个“皇后”可能的摆放方法并且对每一种摆放方法，检查其每一个“皇后”是否能攻击到其它人。

虽然暴力搜索很容易实现，并且如果解决方案存在，就一定能够找到，但是它的代价和候选方案的数量成正比，由于这一点，在很多实际问题中，消耗的代价会随着问题规模的增加而快速地增长。因此，当问题规模有限，或当存在可用于将候选解决方案的集合减少到可管理大小的针对特定问题的启发式算法时，通常使用暴力搜索。另外，当实现方法的简单度比速度更重要的时候，也会用到这种方法。

例如，在关键的应用中，或当用计算机证明数学定理时，算法中的任何错误将会导致严重的后果。暴力搜索也可在其他基准化算法和启发式算法里用作基准方法。事实上，暴力搜索可以被看作最简单的启发式算法。暴力搜索与回溯概念是不相同的，在回溯算法中，大量的解决方案并没有被枚举而直接被丢弃（例如上文提到的“八皇后问题”的解决方案）。用于在表中查找一个项目，也就是说顺序地检查表中所有条目的暴力方法被称为线性搜索。

实现

基本算法

为了将暴力搜索算法应用于特定类别的问题，必须实现四个步骤：“first”、“next”、“valid”以及“output”。这些步骤应该将待解决的问题的特定实例的数据P作为参数，并且进行以下操作：

1.first(P)：生成用于P的第一个候选解决方案；

2.next(P,c)：生成当前一个解c之后的下一个P的候选解；

3.valid(P,c)：检查候选项c是否为P的解；

4.output(P,c)：将P的解决方案c应用于适当地程序。

另外，“first”步骤也必须在当前解之后不再有P的候选解时给出说明，完成这一点的简单的方法是返回一个“空候选项”，即一些不同于真实候选的常规数据值Λ。同样地，如果实例P没有任何候选项，“first”步骤应该返回Λ。暴力搜索可以用以下算法描述：

c ← first(P)

while c ≠ Λ do

if valid(P,c) then output(P, c)

c ← next(P,c)

end while

例如，当查找整数n的约数时，实例P就是整数n。若n≧1，调用first(n)应该返回整数1，若n<1返回Λ；若n≧c，调用next(n,c)应该返回c+1，若n<c则返回Λ；并且valid(n,c)应该返回true当且仅当c是n的约数。（实际上，如果我们选定n+1作为Λ，那么检测n≧1和c<n就是不必要的。）上面的暴力搜索算法会为每一个作为给定实例P的解的候选项调用output。该算法很容易被修改以在找到第一个解或指定数目的解之后停止，或者在测试指定数量的候选项之后，或者在花费给定量的CPU时间之后。

组合爆炸

暴力搜索的主要缺点是对于许多现实世界中的问题，自然候选项的数量大得惊人。例如，就像上文描述的，如果查找一个数的约数，待测的候选项的数量将是给定的数字n，所以如果n是16位的十进制数字，那么搜索将会执行至少10¹⁵条计算机指令，在一台典型的计算机上这将花费几天的时间。如果n是一个任意的64位自然数，平均就有19个十进制，那么搜索将会耗费大约十年的时间。这种随着数据规模的增加，候选项数量急剧增长的现象发生在所有种类的问题中。举个例子，如果我们想要一个特殊的10个字母的重排，那么我们有10!共3,628,800个待考的候选项，一个典型的计算机可以在1秒内完成生成和测试。然而，增加1个字母——这只是数据规模的10%，将会使候选项数量乘上11——增长1000%。对于20个字母，候选项的数量就是20!，大约是$2.4\times 10^{18}$；并且搜索将会花费10年的时间，这种现象通常被称为组合爆炸或维数灾难。

加速暴力搜索

加快暴力搜索的一种方法是通过使用具体问题类的启发式方法减小搜索空间，也就是减小候选解决方案的集合。例如，在“八皇后问题”中，挑战就是将八个皇后放置在标准的棋盘上，以致没有皇后能够攻击到其它任何皇后。因为每一个皇后可以被放在64个方格中的任何一个上，理论上来讲就有= 281,474,976,710,656个待测的可能性。然而，因为所有皇后都是相似的，而且任意两个都不能放在同一个方格中，候选项为从所有64个方格集合中选出的8个方格集合的所有可能的方式，这就意味着64选8，即64!/56!/8! = 4,426,165,368个候选解决方案——约为先前估计的1/60,000。更进一步，在同一行或同一列上放两个皇后的安排不是解决方案。因此，我们可以进一步约束那些放置方法的候选项集合。

正如这个例子所示，一点点的分析经常会导致候选方案的数量大幅减少，而且可能将一个复杂的问题变得很容易。

在一些情况下，分析可能会减小有效的候选解决方案的集合，也就是说，它可以产生直接枚举所有期望解的算法（或适当地找到一个解），而不将时间浪费在生成和测试无效的候选项上。举个例子，对于“找出所有1与1,000,000之间的能被417整除的所有整数”这个问题，一个简单的暴力搜索方法是产生这个范围内所有整数并测试每一个能否被整除。然而，这个问题可以采用从417开始并且每次增加417直到超出1,000,000这种办法从而被更高效地解决，而这种办法只需要2398(=1,000,000÷417)步而且不需要测试。

重新排序搜索空间

在只需要一个解决方案而不是全部的应用程序中，暴力搜索的期望运行时间通常依赖于候选项测试的顺序。作为一般规则，应该首先测试最有希望的候选项。例如，当搜索随机数n的适当约数时，以递增的顺序即从2到n-1枚举候选约数比相反的顺序更好，因为c能被n整除的概率是1/c。此外，候选项有效的概率经常会受之前失败的试验影响。例如，考虑在给定的1000位的字符串中找到”1”的问题，在这种情况下，候选解决方案是1到1000的索引，并且如果P[c] = 1的话候选项c就是有效的。现在，假定P的第一位为0或1的可能性相同，但是之后每一位跟前一位相等的概率为90%。如果候选项被以递增的顺序枚举，即从1到1000，在成功之前待测的候选项数量t平均大约是6。另外，如果候选项被以下面的顺序枚举：1,11,21,31,…,991,2,12,22,32…，t的期望值将仅稍大于2。更一般地来讲，假定先前的试验失败，搜索空间应该被以下一个候选项更可能有效的方式枚举，因此，如果有效解在某种意义上是“聚集的”，则每个新的候选项应当尽可能地与先前的候选项相同。相反的话，解决方案可能比预计的偶然分部分散的更加均匀。

暴力搜索的替代方法

对于各不同门类的知识，存在很多的搜索方法或元启发算法能求得解决方案，启发式方法也可用于提前截断搜索的部分。这样的一个例子就是搜索游戏树的最小化原则，其在搜索的早期消除了许多子树。在某些领域，例如语言分析中，一些技术例如图解法可以利用问题中的约束条件将指数复杂度的问题简化到多项式复杂度的问题。在很多情况下，如在约束满足问题中，通过约束传播可以极大地减小搜索空间，这一点在约束编程语言中被高效实现了。问题的搜索空间可以通过用简化版本代替完整的问题来实现。例如，在计算机象棋中，并不是计算游戏剩余部分所有移动可能的极大极小树，而是计算有限范围内的极大极小可能性的树，即由完整树以特定的移动步数修剪得到，而且这个树须和静态评估函数近似。

在密码学中的应用

在密码学中，暴力攻击与系统地检查所有的密钥直到找出正确的密钥有关。这个策略在理论上可以用于在攻击者无法利用加密系统中任何弱点时攻击任何加密的数据（除了一次性密码），否则破译密码的任务会更加容易。 加密中使用的密钥长度决定了执行暴力攻击的实际可行性，其中长度较长的密钥相比长度较短的更难以被破解。可以通过混淆编码数据的方法降低暴力攻击的有效性，这种方法就是让攻击者更难意识到他已经破解了密码。衡量加密系统的标准之一就是理论上攻击者暴力破解密码所需时间的长短。