暴力搜索是什么

维基 问答 2022-05-06 10:48:29 阅读(...)

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

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

search 搜索

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

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

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

组合爆炸

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

暴力搜索的替代方法

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

在密码学中的应用

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

0个人收藏 收藏

评论交流

泪雪默认头像 请「登录」后参与评论
  1. 加载中..

相关推荐

  • 对称密钥算法 Symmetric-key algorithm

    对称密钥算法是什么

    对称密钥算法又称为对称加密、私钥加密、共享密钥加密,是密码学中的一类加密算法。这类算法在加密和解密时使用相同的密钥,或是使用两个可以简单地相互推算的密钥。事实上这组密钥成为在两个或多个成员间的共同秘密,以便维持专属的通信联系。
  • 无服务器计算 Serverless Computing

    无服务器计算是什么

    无服务器计算是在无需最终用户管理的基础设施上托管应用程序的新方式,是IaaS(基础设施即服务)演进的下一个阶段。它将底层基础架构从开发人员中分离出来,基本上虚拟化了运行时(虚拟机的一种,一般指进程级别的虚拟机)和运营管理。
  • 无服务器 Serverless

    无服务器是什么

    无服务器(Serverless)是指根据用户需求提升计算资源的云计算服务。无服务器的最大优点是用户不需要监控和管理。用于开发中,为开发者腾出更多时间优化代码,或者为应用特性或功能寻找更多创新点。
  • 群晖 synology nas

    群晖NAS如何使用VPN异地容灾备份

    群晖NAS想要使用VPN异地容灾备份需要先通过后台控制面板-网络来设置VPN连接,连接成功之后要通过Hyper Backup 套件来进行异地容灾备份的实现,如果没有这个套件需要在套件中心搜索安装。
  • 群晖 synology nas

    群晖NAS如何安装DSM系统

    首先通过群晖官网下载中心根据NAS型号下载pat文件和Synology Assistant,先按照平时安装新软件,安装并打开群晖Assistant软件扫描群晖NAS,找到后右键DSM未安装的机器选择安装。然后按照流程点击同意协议和选择pat文件及系统引导即可安装成功。
  • 群晖 synology nas

    群晖NAS如何创建共享文件夹

    群晖NAS有两个位置可以创建共享文件夹,在控制面板-共享文件夹-新建中选择新建来创建;另一个是通过在File station套件中,也可以点击新增按钮,后选择新增共享文件夹的方式创建。