搜索策略在人工智能中的应用

人工智能领域,PEAS代表性能评估、环境、执行器和传感器。智能体通过传感器理解其环境,并使用执行器执行相关动作。智能体的搜索策略决定了这些“相关”动作。这有助于智能体选择正确的移动以达到目的地。因此,计算智能体的路径以实现其目的是非常重要的。人工智能使用不同的搜索策略来计算智能体的路径。

为什么搜索策略很重要?

一个简单的井字棋游戏可能有362880(9!)种不同的状态,但只有少数几种能让获胜。同样,著名的传教士和食人族问题也有很多可能的状态。更不用说国际象棋了。搜索策略是解决问题的结构化方法。人工智能中的理性或问题解决智能体通常使用这些搜索策略来解决给定的问题,并提供最佳解决方案。

搜索策略主要分为两类:

无启发式搜索和启发式搜索。

无启发式搜索策略

无启发式搜索策略是采用蛮力方法的搜索策略。无启发式搜索策略除了问题约束中定义的之外没有任何知识。它们只是通过盲目遍历不同的状态来找到通往目的地的路径。将根据以下四个参数评估策略:

如果搜索策略能够识别出智能体通往目标的路径,才能称之为完整的。

时间的度量。

最坏情况下的最大存储量。

“最优解”指的是算法的最佳可能解决方案(最低路线成本)。

广度优先搜索、深度优先搜索、均匀成本搜索、深度限制搜索、迭代加深深度优先搜索和双向搜索。

广度优先搜索是遍历树或图的最流行方法,它遵循层次遍历方法。广度优先搜索算法在树或图上执行层次搜索。广度优先搜索算法从树的根节点开始搜索,并在移动到下一层的节点之前,扩展当前层的每个子节点。使用队列来实现广度优先搜索。

广度优先搜索承诺提供解决方案(如果存在)。但这会增加时间和空间复杂度,当目标状态位于树/图中的深层时。这里有一个广度优先搜索解决传教士和食人族问题的解决方案。

深度优先搜索是一种递归方法,用于探索树或图。深度优先搜索从根节点开始,沿着每条路径一直走到树的深度,通过扩展其子节点之一,然后移动到下一条路径。使用栈来实现深度优先搜索。

深度优先搜索只需要存储从根节点到当前节点的路径上的节点栈,因此与其他策略相比,它使用的内存相对较少。由于深度优先搜索首先深入,有时可能会进入无限循环。因此,深度优先搜索不能保证完整的解决方案。

当图具有加权顶点时,可以使用均匀成本搜索。它有助于以一种最优化的方式为基于效用的智能体找到目标。其思想是每次都扩展最便宜的节点。这是通过维护一个边界来实现的,即按路径成本排序的优先队列(较低状态获得更高的优先级)。

任何需要最优成本的图或树都可以用它来解决。这种策略有时会陷入无限循环,因为它更关注路径成本。

深度限制搜索与深度优先搜索类似,但它预设了一个深度限制(比如说l)。深度l以下的节点被用作没有后继节点的节点,即叶子节点。这有助于解决深度优先搜索的无限路径问题。但这也不能保证完整的解决方案。当目标状态位于l以下的某个层次时,它可能会失败。

它递归地移动以遍历图的深度,直到达到限制。如果达到限制,它将切断并回溯到其他节点进行搜索。

这是一种广泛使用的策略,因为它试图结合深度优先搜索和广度优先搜索的优点。当搜索空间太大且解决方案的深度未知时,这特别有用。它从树的深度限制0开始,并在增加限制之前探索其所有节点,每次增加1。这一直持续到找到目标之一。

像深度优先搜索一样,它的内存需求适中。像广度优先搜索一样,它承诺提供完整的解决方案,并且当路径成本是节点深度的非递减函数时,也提供最优解决方案。对于分支因子为10、深度为5的图/树,广度优先搜索在其最坏情况下遍历111,110个节点。与此同时,迭代加深深度优先搜索遍历123,450个节点。

双向搜索是一种双向搜索,即一个从初始状态向前搜索,另一个从目标状态向后搜索。希望两个搜索能在某个状态的中间相遇。

沪ICP备2024098111号-1
上海秋旦网络科技中心:上海市奉贤区金大公路8218号1幢 联系电话:17898875485