暴力搜索

穷举搜索

在计算机科学中，暴力搜索是一个非常一般的解决问题的技术，包括系统地枚举解决方案的所有可能的候选项，以及检查每个候选项是否符合问题的描述。

简介

网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。是数学建模十类算法之一。

在信息学竞赛中，暴力搜索不用技巧，类似穷举，对于有点难度的题目，暴力搜索一般都会超时。

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

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

基本算法

为了将暴力搜索算法应用于特定类别的问题，必须实现四个步骤：“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)

whilec≠ Λdo

ifvalid(P,c)thenoutput(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=1和c

组合爆炸

暴力搜索的主要缺点是，对于许多现实世界中的问题，自然候选项的数量大得惊人。例如，就像上文描述的，如果查找一个数的约数，待测的候选项的数量将是给定的数字n，所以如果n是16位的十进制数字，那么搜索将会执行至少条计算机指令，在一台典型的PC机上这将花费几天的时间。如果n是一个任意的64位自然数，平均就有19个十进制位，那么搜索将会耗费大约十年的时间。这种随着数据规模的增加，候选项数量急剧增长的现象发生在所有种类的问题中。举个例子，如果我们想要一个特殊的10个字母的重排，那么我们有10!= 3,628,800个待考的候选项，一个典型的PC机可以在1秒内完成生成和测试。然而，增加1个字母——这只是数据规模的10%，将会使候选项数量乘上11——增长1000%。对于20个字母，候选项的数量就是20!，大约是2.4X；并且搜索将会花费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。更一般地来讲，假定先前的试验失败，搜索空间应该被以下一个候选项更可能有效的方式枚举，因此，如果有效解在某种意义上是“聚集的”，则每个新的候选项应当尽可能地与先前的候选项相同。相反的话，解决方案可能比预计的偶然分部分散的更加均匀。

暴力搜索的替代方法

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

在密码学中的应用

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

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省