暴力搜索
维基百科,自由的 encyclopedia
暴力搜索或穷举搜索,在计算机科学中也称生成与测试是一种非常低效的解决问题的技术,方法包括了系统地枚举解决方案的所有可能候选项以及检查每个候选项是否符合问题描述。
此条目需要补充更多来源。 (2022年6月11日) |
找出自然数n的约数的暴力搜索算法将枚举出从1到n的所有整数,并检查它们中的每一个是否除n后没有余数。针对八皇后问题的暴力搜索算法会检查所有在8X8棋盘上八个“皇后”可能的摆放方法并且对每一种摆放方法,检查其每一个“皇后”是否能攻击到其它人。
虽然暴力搜索很容易实现,并且如果解决方案存在,就一定能够找到,但是它的代价和候选方案的数量成正比,由于这一点,在很多实际问题中,消耗的代价会随着问题规模的增加而快速地增长。因此,当问题规模有限,或当存在可用于将候选解决方案的集合减少到可管理大小的针对特定问题的启发式算法时,通常使用暴力搜索。另外,当实现方法的简单度比速度更重要的时候,也会用到这种方法。
例如,在关键的应用中,或当用计算机证明数学定理时,算法中的任何错误将会导致严重的后果。暴力搜索也可在其他基准化算法和启发式算法里用作基准方法。事实上,暴力搜索可以被看作最简单的启发式算法。暴力搜索与回溯概念是不相同的,在回溯算法中,大量的解决方案并没有被枚举而直接被丢弃(例如上文提到的“八皇后问题”的解决方案)。用于在表中查找一个项目,也就是说顺序地检查表中所有条目的暴力方法被称为线性搜索。