暴力搜索

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

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

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

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

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

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

基本算法为了将暴力搜索算法应用于特定类别的问题，必须实现四个步骤：“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=c，调用next(n,c)应该返回c+1，若n=1和c