人工智能搜索算法

人工智能搜索算法

搜索算法是人工智能最重要的领域之一。本主题将解释有关AI中搜索算法的所有信息。

解决问题的代理

在人工智能中,搜索技术是普遍的问题解决方法。AI中的合理代理或问题解决代理主要使用这些搜索策略或算法来解决特定问题并提供最佳结果。解决问题的代理是基于目标的代理并使用原子表示。在本主题中,我们将学习各种解决问题的搜索算法。

搜索算法术语

  • 搜索:搜索是一个一步一步的过程,用于解决给定搜索空间中的搜索问题。搜索问题可能有三个主要因素:
    • 搜索空间:搜索空间表示系统可能具有的一组可能的解决方案。
    • 开始状态:代理开始搜索的状态。
    • 目标测试:它是一个观察当前状态并返回目标状态是否达到的函数。
  • 搜索树:搜索问题的树表示称为搜索树。搜索树的根是与初始状态对应的根节点。
  • 操作:它向代理提供所有可用操作的描述。
  • 过渡模型:每个动作的描述,可以表示为过渡模型。
  • 路径成本:它是一个为每个路径分配数字成本的功能。
  • 解决方案:它是一个从起始节点到目标节点的动作序列。
  • 最佳解决方案:如果解决方案在所有解决方案中成本最低。

搜索算法的属性

以下是搜索算法的四个基本属性,用于比较这些算法的效率:

  • 完整性:如果搜索算法保证在任何随机输入存在至少任何解决方案的情况下保证返回解决方案,则称该搜索算法是完整的。
  • 优化性:如果为算法找到的解决方案被保证是所有其他解决方案中的最佳解决方案(最低路径成本),那么这种解决方案被认为是最佳解决方案。
  • 时间复杂度:时间复杂度是算法完成任务的时间度量。
  • 空间复杂性:它是搜索过程中任何点所需的最大存储空间,因为问题的复杂性。

搜索算法的类型

基于搜索问题,我们可以将搜索算法分类为不知情(盲搜索)搜索和通知搜索(启发式搜索)算法。

搜索算法的类型

1. 不知情/盲搜索

不知情搜索不包含任何领域知识,如亲密度,目标的位置。它以蛮力的方式运行,因为它只包含有关如何遍历树以及如何识别叶子和目标节点的信息。不知情的搜索应用搜索搜索树的方式,没有任何关于搜索空间的信息,如初始状态运算符和目标测试,因此它也称为盲搜索。它检查树的每个节点,直到它达到目标节点。

它可以分为五种主要类型:

  • 广度优先搜索
  • 统一成本搜索
  • 深度优先搜索
  • 迭代加深深度优先搜索
  • 双向搜索

2. 知情搜索

知情搜索算法使用领域知识。在知情搜索中,可以获得可以指导搜索的问题信息。知情搜索策略可以比不知情的搜索策略更有效地找到解决方案。知情搜索也称为启发式搜索。

启发式算法可能无法始终保证最佳解决方案,但保证在合理的时间内找到一个好的解决方案。
知情搜索可以解决许多无法以其他方式解决的复杂问题。