人工智能中的搜索算法

本文概述

• 搜索算法术语
• 搜索算法的性质
• 搜索算法的类型

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

解决问题的代理人：

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

搜索算法术语

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

搜索算法的性质

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

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

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

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

空间复杂度：它是搜索过程中任何时候所需的最大存储空间，这是问题的复杂性。

搜索算法的类型

根据搜索问题，我们可以将搜索算法分为非信息搜索（盲搜索）和知情搜索（启发式搜索）算法。

不知情/盲目搜索：

不知情的搜索不包含任何领域知识，例如紧密性，目标位置。它以蛮力方式操作，因为它仅包含有关如何遍历树以及如何识别叶节点和目标节点的信息。不知情的搜索采用一种搜索树的方式，它不包含有关搜索空间的任何信息（例如初始状态运算符）并测试目标，因此也称为盲搜索（盲搜索），它检查树的每个节点，直到达到目标节点为止。

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

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

知情搜索

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

试探法可能无法始终保证获得最佳解决方案，但可以保证在合理的时间内找到好的解决方案。

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

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

1. 贪婪的搜索
2. A *搜索