人工智能中的搜索算法

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

问题解决代理：

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

搜索算法术语：

• 搜索：搜索是在给定搜索空间中解决搜索问题的逐步过程。搜索问题可能具有三个主要因素：

1. 搜索空间：搜索空间表示系统可能具有的一组可能的解决方案。

2. 开始状态：这是代理开始搜索的状态。

3. 目标测试：观察当前状态并返回是否达到目标状态的函数。

• 搜索树：搜索问题的树表示称为搜索树。搜索树的根是初始状态对应的根节点。

• 动作：它向代理提供所有可用动作的描述。

• 转换模型：对每个动作做什么的描述，可以表示为转换模型。

• 路径成本：它是一个函数，它为每条路径分配一个数字成本。

• 解：它是一个从起始节点到目标节点的动作序列。

• 最优解：如果一个解在所有解中成本最低。

搜索算法的特性：

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

完整性：如果搜索算法保证在任何随机输入至少存在任何解决方案时返回解决方案，则称该搜索算法是完整的。

最优性：如果保证为算法找到的解决方案是所有其他解决方案中的最佳解决方案（最低路径成本），那么这种解决方案就称为最优解决方案。

时间复杂度：时间复杂度是算法完成其任务的时间度量。

空间复杂度：它是搜索过程中任何一点所需的最大存储空间，作为问题的复杂度。

搜索算法的类型

根据搜索问题，我们可以将搜索算法分为无信息（Blind search）搜索和有信息搜索（Heuristic search）算法。

不知情/盲目搜索：

无信息搜索不包含任何领域知识，例如接近度、目标位置。它以蛮力方式运行，因为它只包含有关如何遍历树以及如何识别叶节点和目标节点的信息。无信息搜索是一种搜索树的搜索方式，在搜索树中没有任何关于搜索空间的信息，如初始状态算子和测试目标，因此也称为盲搜索。它检查树的每个节点，直到达到目标节点。

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

• 广度优先搜索

• 统一成本搜索

• 深度优先搜索

• 迭代深化深度优先搜索

• 双向搜索

知情搜索

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

启发式方法可能并不总是保证获得最佳解决方案，但可以保证在合理的时间内找到一个好的解决方案。

知情搜索可以解决许多其他方式无法解决的复杂问题。

知情搜索算法的一个例子是旅行商问题。

1. 贪婪搜索

2. A* 搜索