人工智能中的最佳优先搜索算法

最佳优先搜索算法的定义

BFS 是 Best First Search 的缩写，在人工智能的背景下，它是一种搜索类型，旨在通过使用预先设定的评估函数来评估节点，从而选择通往目标路径的最佳路径。该算法结合了 DFS 和 BFS 策略的最佳特性，以在搜索空间中进行高效搜索。启发式信息有助于 BFS 算法选择下一个合适的节点进行扩展，从而最大限度地减少整体搜索并更接近目标状态。

评估函数通常用作启发式函数，它衡量从当前节点到目标所需的步骤成本。以贪婪最佳优先搜索（如 A*）为例，该算法优先打开具有最低估计成本的节点，并迅速移向目标节点。相比之下，A* 搜索算法会考虑两个因素：路径成本和到达目标的估计成本，使其在选择最合适的路径方面更加有效。BFS 可以从任何节点开始，并同时向所有方向扩展；当搜索大区域且目标不易识别时，这尤其有利。

这被广泛用于路径查找问题、解谜以及所有需要快速和最优决策的智能应用程序的搜索策略中。尽管 BFS 在实践中非常强大，但它的成功在很大程度上取决于所应用的启发式函数的质量，该函数决定了算法的结果和精度。

搜索算法概述

• 广度优先搜索 (BFS)
  另一方面，BFS 会查看当前层的所有节点，然后跳转到下一层节点。对于访问候选结构所代表的节点的顺序，会实现一个队列，以便搜索树的每个级别都能在穷尽搜索中完成。它基于 BFS，如果图是无权图，它保证能找到最短路径，但由于它涉及存储大量节点，因此可能非常消耗内存。
• 统一成本搜索 (UCS)
  UCS，也称为Dijkstra 算法，根据最经济的路线来比较节点。它类似于 BFS，但在构建图时，会考虑路径成本，这适用于加权图。UCS 确保找到最优路径；但是，如果成本灵活，该方法可能需要更长时间才能找到路径。
• 贪婪最佳优先搜索
  这种有指导的搜索算法选择节点，并考虑目标的成本估计。它偏爱那些看起来最接近目标的节点，但并不总是保证最优解。当找到一个好的启发式函数时，它就很有用，这意味着我们不必总是从头开始解决问题。
• A* 搜索
  A* 结合了UCS 和 GBFS；它不仅使用从起始节点到当前节点的路径成本，还使用表示从当前节点到目标节点的估计成本的启发式函数。只要启发式函数是可接受的（即，它们不会高估实际解决方案的成本），这种策略就可以保证最佳和完整的解决方案。
• 迭代加深搜索 (IDS)
  DFS 和 BFS 相结合，以利用两种算法的特性。IDS 会进行多次搜索，将搜索的最大深度限制在一个级别，并逐渐增加深度限制。它能找到最短路径，但比 BFS 需要更少的内存，而由于回溯，其时间复杂度更高。
• 双向搜索
  该算法同时执行两次搜索：一次从起始节点开始，一次从目标节点开始，然后它们相交。它可以极大地减少搜索空间和时间，但它需要起始和目标状态以及对中间状态的适当管理。

基本术语

状态空间

• 状态空间是搜索算法和问题解决中的关键概念之一。它描述了从问题的初始状态可以到达的所有不同的可能状态或条件。在状态空间中，每个状态由一组变量定义，一组状态与被调查系统的一个特定配置相关。相比之下，状态之间的相互连接描述了可能的动作或操作。
• 在此基础上，状态空间也可以映射为树或图，其中节点是状态，边是从一个状态到另一个状态的转换或移动。搜索问题的解决方案，如迷宫、谜题或合适的物流空间，对于获得问题状态空间的概览至关重要。

节点和边

• 节点/顶点和边是图的基本结构，而图又用于说明搜索过程的状态空间。节点或顶点指的是状态空间中问题的状态或配置。连接两个节点的弧或边表示从一个状态到另一个状态的移动，更准确地说。有向图与简单图非常相似，唯一的区别是边也与指示状态之间关系的特定方向相关联。
• 在无向图中，连接节点的边没有方向，因此表示节点之间的双向连接。这也考虑了图中节点和边的性质有助于对有关路径、流和依赖关系的许多问题进行建模。事实上，了解节点的关系或它们之间的转换是形成搜索策略和算法的基础。

路径成本

• 路径成本是搜索算法的一个基本组成部分，特别是在发现最有效的解决方案时。它代表了在状态空间中从起始状态到目标状态的从一个状态到另一个状态的移动所产生的总成本。图中的每条边可能都有一个成本，可以灵活地表示距离、时间或问题相关的任何关键特征。
• 构成总路径的所有边的成本之和称为总路径成本。UCS（统一成本搜索）、A* 搜索等算法要求从起始节点到目标节点的路径成本最小化。这些算法利用路径成本来控制搜索过程，以确定获得的解决方案确实是一个解决方案，并且也是在特定度量方面最好的解决方案。

算法步骤

算法是一组预定义的规则，用于执行乘法和其他数学计算以及解决涉及一类对象的任何问题。算法的有效控制流组成部分通常用于解决某些问题，这些问题通常涉及输入、计算和输出。以下是算法的基本步骤

搜索算法概述

• 问题定义
  首先，重要的是要确定算法的用途及其旨在解决的问题。这包括识别业务实体的规范需求、限制和目标。这消除了算法漫无目的的可能性，并由于明确定义的问题而增加了其效率的可能性。
• 输入规范
  其次，它确定了算法所需的输入。输入是要输入算法进行处理的数据。因此，就类型、格式和范围而言，它应该被明确定义。数据输入规范有助于算法正确处理计算机接收到的数据。
• 初始设置
  但是，有时在实际处理之前有一个初步步骤，通常称为预处理。这可能包括输入变量的第一个实例的值，创建或组织要存储在数据结构中的数据，或者进行初步计算。
• 主处理
  这是数据计算或转换按顺序发生的过程。算法接收输入数据并对其进行各种操作以产生所需的输出。根据手头的任务，此步骤可以采取循环、条件或其他操作的形式，具体取决于需要。
• 输出规范
  结果作为输出从处理后的算法中获得。这些是算法计算的数量或数字。应清楚说明要生成的输出的格式和类型，以便进行无偏见测试。它应该在所考虑的问题中有用且有意义。
• 终止
  每种算法都必须有一个终止的基础，告知算法何时应该结束过程。这可能是在指定的轮数之后，在达到某个状态时，或者在获得所需结果时。
• 验证和测试
  算法编写完成后，必须对其进行检查以验证其是否正常工作并建立性能基线。这是通过在一组测试用例上执行算法，并将结果与这些测试用例上的预期结果进行比较来完成的。

最佳优先搜索的类型

贪婪最佳优先搜索

贪婪最佳优先搜索是一种搜索算法，它始终关注最佳可能的节点作为下一步。它依赖于启发式函数 h(n) 来近似从当前节点 n 到目标的剩余距离的成本。该算法试图以节点上最短的启发式成本完成搜索，从而有效地寻求到达目标。

步骤：

初始化

• 从您选择的第一个节点开始，这也是我们拥有的唯一节点。
• 请根据其估计启发式函数 h(n) 的值将第一个节点输入优先级队列。

扩展最有前途的节点

• 具有最低值的标记节点 - 必须删除此节点
• 下一个可用处理器从优先级队列中获取一个 h(n)。
• 如果此节点是目标节点，则打印到此节点的路径，搜索完成。

生成后继节点

• 生成当前节点的所有可能后继节点（细胞邻居）。

评估并添加后继节点

• 确定每个后继节点的启发式值 h。
• 根据其 h 值将后继节点添加到优先级队列。

重复

• 执行步骤 2 到 4 尽可能多次，直到找到目标节点，或者直到优先级队列耗尽且无法从中检索到任何节点。

示例

假设您迷失在迷宫中，有“选项”或“选择”。在贪婪最佳优先搜索中，算法将始终倾向于朝着似乎更接近出口的方向移动，利用估计或启发式函数，但它会遇到死胡同；也就是说，它会陷入死胡同，因为它在搜索中不考虑所走路径的实际成本。

A* 搜索

根据所需的路径和情况，A* 搜索比贪婪最佳优先搜索稍好，比 Dijkstra 算法稍差。它使用两个函数：A*-算法使用 g(n) 作为从起始节点到当前节点 n 的实际成本，以及 h(n) 作为从n 到目标的估计成本。因此，总成本函数 f(n)=g(n)+h(n) 用于选择下一个要扩展的节点，同时提供最优和高效的搜索。

步骤：

初始化

• 这里采用的策略是从第一个节点开始。
• 第一个节点，即源节点，其 g 值最初设置为 0，这意味着到达它没有产生任何成本。
• 在所需的结束节点，计算 f=g+h 并将起始节点添加到优先级队列。

扩展最低成本节点

• 选择 f(n) 步数成本最低的节点，并将其从优先级队列中删除。
• 如果此节点是目标节点，则开始构建并返回到此节点的路径，然后退出循环。

生成后继节点

• 生成给定节点的所有可能后继节点。

评估后继节点的成本（对于每个后继节点）

• 获取暂定 g 值为 g(当前) + cost(当前, 后继)。
• 最后一部分是通过数学上对后继节点的 g 和 h 值进行求和来完成的，即 f = g(后继) + h(后继)。
• 如果后继节点不在优先级队列中，并且新的 g 值小于记录的 g 值，则使用新的 f 值扩展优先级队列并记录此路径。

重复

• 如果优先级队列不为空，请返回步骤 2 到 4 以识别目标节点。

示例

在执行与上述相同的迷宫场景时，A* 搜索会找到看似最接近出口的方向，这与贪婪最佳优先搜索类似，但此外，它还会考虑已经走了多少步。这样，如果地图上显示较长且曲折的路径不太理想，但实际上它更短，它就会被检查。

优点

• 减少人为错误
  人工智能系统有助于减少与人相比的错误，从而提高结果的效率和准确性。这种区别在医学和工程等职业中非常有用。
• 冒险承担
  人工智能可以在危及人们生命的危险情况下使用，从而减少事故。这包括在危险区域、地外旅行以及管理洪水等灾难中的活动。
• 效率和生产力
  大多数常规和单调的任务都可以由人工智能系统有效地完成，从而使人们能够花费更多时间从事更具创造性的工作。
• 增强的决策制定
  人工智能可以在短时间内分析海量数据，并有助于改进许多领域的决策。
• 个性化和客户体验
  因此，人工智能可以始终帮助设计和推荐最适合客户需求的解决方案，从而提高他们的满意度。

缺点

• 减少就业
  人工智能系统的自我自动化可能会导致失业，因为它会用计算机系统取代人力劳动，尤其是在工作是例行性工作的情况下。
• 缺乏创造力
  我们还认为，虽然人工智能系统很有效率，但它们不能像人类那样具有创造性或跳出框框思考。
• 缺乏情感范围
  人工智能无法取代人类，因为它无法表现出适当的敏感性，而敏感性在医疗保健和客户关系等领域非常重要。
• 伦理困境
  人工智能应用的一些主要伦理问题如下：课程、隐私、决策责任以及人工智能模型中的歧视。
• 高成本
  人工智能的创建、集成和管理也可能成本高昂，因此其应用主要限于大型组织。

最佳优先搜索的应用

• 游戏中的寻路
  BFS 算法经常用于视频游戏中，以查找角色或对象如何以最快的方式从起点到达目标，而不会与其他任何对象发生碰撞。A* 搜索因其效率和搜索结果的准确性水平而受到青睐。
• 机器人技术
  在机器人领域，BFS 算法在导航存在的情况下很有用。这些算法帮助机器人在执行任务时实时寻找最佳路径。
• 网络路由
  如今，BFS 算法被用于网络路由，使数据包能够轻松地通过网络。这确保了几乎所有网络资源都与延迟时间直接成比例。
• 人工智能
  BFS 算法对于人工智能来说非常重要，因为它能够提供解决复杂问题（如 NL、ML 和决策制定解决方案）的方法。它们支持人工智能系统评估不同的选项并决定采取哪种选项。
• 导航系统
  包括 GPS 在内的导航系统使用 BFS 算法来确定最短和最快的出行方式。该算法在计算和生成有利路线方面的效率，尤其是在查看大量交通数据时，对该应用非常有益。

最佳优先搜索算法的独特功能

• 启发式评估函数
  BFS 始终有一个由启发式评估函数确定的节点访问顺序。该函数计算从起始节点到目标节点所需的成本，从而通过识别最有前途的移动来提高算法的效率。
• 优先队列
  待探索的节点存储在 BFS 的优先级队列中。对应于被定义为最远离启发式成本起点的节点的路径被给予高度优先，这使得算法更有可能首先搜索最佳路径。
• 普遍性
  BFS 算法确实非常通用，可以通过特定的修改用于进一步的需求。由于启发式函数的更改，BFS 可以转换为其他算法，例如 A* 搜索，从而有助于解决不同形式的搜索问题。
• 有指导的搜索
  虽然在这种情况下，搜索路径是随机生成的，没有任何关于到目标的成本的信息，但 BFS 是一种有指导的搜索算法。启发式函数有助于控制搜索方向，从而使其更有效地到达最佳搜索路径。

结论

最佳优先搜索 (BFS) 算法是人工智能的关键组成部分，用于借助启发式评估函数在大型空间中搜索有效解决方案。因此，由于专注于最成功的节点，BFS 结合了广度优先和深度优先搜索，这使其多样化和最优。应注意，该算法可以根据启发式函数的选择进行改进，以用于路径识别和最优问题。总而言之，由于其有指导的搜索和应用灵活性，BFS 是解决各种人工智能问题的最佳方法之一。