AI - 流行的搜索算法

搜索是 AI 中解决问题的通用技术。有一些单人游戏，例如瓷砖游戏、数独、填字游戏等。搜索算法可帮助您在此类游戏中搜索特定位置。

单代理寻路问题

3X3 八块瓷砖、4X4 十五块瓷砖和 5X5 二十四块瓷砖拼图等游戏是单代理寻路挑战。它们由带有空白瓷砖的瓷砖矩阵组成。玩家需要通过将图块垂直或水平滑动到空白处来排列图块，以完成某些目标。

单个代理寻路问题的其他示例是旅行商问题、魔方和定理证明。

搜索术语

问题空间 − 它是进行搜索的环境。（一组状态和一组用于更改这些状态的运算符）
问题实例 − 它是初始状态 + 目标状态。
问题空间图 − 它表示问题状态。状态由节点显示，运算符由边显示。
问题的深度 −从初始状态到目标状态的最短路径或最短运算符序列的长度。
空间复杂度 − 存储在内存中的最大节点数。
时间复杂度 − 创建的最大节点数。
可接受性 − 算法始终找到最佳解决方案的属性。
分支因子 − 问题空间图中子节点的平均数量。
深度 − 从初始状态到目标状态的最短路径的长度。

强力搜索策略

它们最简单，因为它们不需要任何特定领域的知识。它们在少数可能状态下工作良好。

要求 −

状态描述
一组有效运算符
初始状态
目标状态描述

广度优先搜索

从根节点开始，首先探索相邻节点，然后向下一级邻居移动。它一次生成一棵树，直到找到解决方案。它可以使用 FIFO 队列数据结构来实现。此方法提供最短路径解决方案。

如果分支因子（给定节点的平均子节点数）= b 且深度 = d，则级别 d 的节点数 = b^d。

最坏情况下创建的节点总数为 b + b² + b³ + … + b^d。

缺点 − 由于保存每一级节点以创建下一级，因此会占用大量内存空间。存储节点的空间需求呈指数增长。

其复杂性取决于节点数量。它可以检查重复节点。

深度优先搜索

它以递归方式实现，使用 LIFO 堆栈数据结构。它创建与广度优先方法相同的节点集，只是顺序不同。

由于单条路径上的节点存储在从根到叶节点的每次迭代中，因此存储节点的空间要求是线性的。分支因子为 b，深度为 m，存储空间为 bm。

缺点 − 该算法可能无法终止并在一条路径上无限继续。解决此问题的方法是选择一个截止深度。如果理想截止值为 d，而所选截止值小于 d，则该算法可能失败。如果所选截止值大于 d，则执行时间会增加。

其复杂性取决于路径数量。它无法检查重复节点。

双向搜索

从初始状态向前搜索，从目标状态向后搜索，直到两者相遇以识别共同状态。

从初始状态开始的路径与从目标状态开始的逆路径连接在一起。每次搜索只进行总路径的一半。

统一成本搜索

按到节点的路径成本递增进行排序。它总是扩展成本最低的节点。如果每个转换的成本相同，则它与广度优先搜索相同。

它按成本递增的顺序探索路径。

缺点 − 可以有多条长路径，其成本 ≤ C*。统一成本搜索必须探索所有这些。

迭代深化深度优先搜索

它执行深度优先搜索到第 1 级，重新开始，执行完整的深度优先搜索到第 2 级，并以此方式继续，直到找到解决方案。

它永远不会创建节点，直到生成所有较低节点。它只保存一堆节点。当算法在深度 d 处找到解决方案时结束。在深度d处创建的节点数为b^d，在深度d-1处创建的节点数为b^d-1

各种算法复杂度比较

让我们看看基于各种标准的算法的性能 −

标准	广度优先	深度优先	双向	统一成本	交互式深化
时间	b^d	b^m	b^d/2	b^d	b^d
空间	b^d	b^m	b^d/2	b^d	b^d
最优性	是	否	是	是	是
完整性	是	否	是	是	是

知情（启发式）搜索策略

为了解决具有大量可能状态的大型问题，需要添加特定于问题的知识来提高搜索算法的效率。

启发式评估函数

它们计算两个状态之间最佳路径的成本。滑动瓷砖游戏的启发式函数通过计算每个瓷砖从其目标状态进行的移动次数并将所有瓷砖的移动次数相加来计算。

纯启发式搜索

它按启发式值的顺序扩展节点。它创建两个列表，一个已扩展节点的封闭列表和一个已创建但未扩展节点的开放列表。

在每次迭代中，扩展具有最小启发式值的节点，创建其所有子节点并将其放置在封闭列表中。然后，将启发式函数应用于子节点，并根据其启发式值将它们放置在开放列表中。保存较短的路径，处理较长的路径。

A * 搜索

这是最佳优先搜索最著名的形式。它避免扩展已经很昂贵的路径，但首先扩展最有希望的路径。

f(n) = g(n) + h(n)，其中

g(n) 到达节点的成本（到目前为止）
h(n) 从节点到目标的估计成本
f(n) 从 n 到目标的路径的估计总成本。它通过增加 f(n) 使用优先级队列来实现。

贪婪最佳优先搜索

它扩展估计最接近目标的节点。它根据 f(n) = h(n) 扩展节点。它使用优先级队列实现。

缺点 − 它可能陷入循环。它不是最优的。

局部搜索算法

它们从一个预期解决方案开始，然后移动到相邻的解决方案。它们可以返回有效的解决方案，即使在它们结束之前的任何时间被中断。

爬山搜索

它是一种迭代算法，从问题的任意解决方案开始，并尝试通过逐步更改解决方案的单个元素来找到更好的解决方案。如果更改产生了更好的解决方案，则增量更改将被视为新解决方案。重复此过程，直到没有进一步的改进。

函数 Hill-Climbing（问题），返回局部最大值的状态。

inputs: problem, a problem
local variables: current, a node
                 neighbor, a node
current <-Make_Node(Initial-State[problem])
loop
   do neighbor <- a highest_valued successor of current
      if Value[neighbor] ≤ Value[current] then
      return State[current]
      current <- neighbor				  
	
end

缺点 − 该算法既不完整，也不是最优的。

局部波束搜索

在该算法中，它在任何给定时间都保存 k 个状态。开始时，这些状态是随机生成的。这 k 个状态的后继是借助目标函数计算的。如果这些后继中的任何一个是目标函数的最大值，则算法停止。

否则，将（初始 k 个状态和状态的 k 个后继 = 2k）状态放置在池中。然后按数字对池进行排序。选择最高的 k 个状态作为新的初始状态。此过程持续到达到最大值。

函数 BeamSearch( problem, k) 返回解决方案状态。

从 k 个随机生成的状态开始
循环
    生成所有 k 个状态的所有后继
    如果任何状态 = 解决方案，则返回该状态
    否则选择 k 个最佳后继
结束

模拟退火

退火是加热和冷却金属以改变其内部结构从而修改其物理特性的过程。当金属冷却时，其新结构被抓住，金属保留其新获得的特性。在模拟退火过程中，温度保持不变。

我们最初将温度设置为较高，然后随着算法的进行，让它慢慢"冷却"。当温度较高时，算法可以高频率地接受更差的解决方案。

开始

初始化 k = 0；L = 整数变量数；
从 i → j，搜索性能差异 Δ。
如果 Δ <= 0，则接受，否则如果 exp(-Δ/T(k)) > random(0,1) then accept;
重复步骤 1 和 2 共 L(k) 步。
k = k + 1;

重复步骤 1 到 4 直到满足条件。

结束

旅行商问题

在此算法中，目标是找到一条低成本的旅行路线，从某个城市出发，沿途访问所有城市一次，并在同一出发城市结束。

Start
    找出所有 (n -1)! 个可能的解决方案，其中 n 是城市总数。
    通过找出每个 (n -1)! 个解决方案的成本来确定最低成本。
    最后，保留成本最低的那个。
end

人工智能教程