AI - 热门搜索算法

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

单代理寻路问题

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

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

搜索术语

  • 问题空间- 这是搜索发生的环境。（一组状态和一组更改这些状态​​的运算符）

  • 问题实例- 它是初始状态+目标状态。

  • 问题空间图- 它代表问题状态。状态由节点显示，运算符由边显示。

  • 问题的深度- 从初始状态到目标状态的最短路径或最短运算符序列的长度。

  • 空间复杂度- 内存中存储的最大节点数。

  • 时间复杂度- 创建的最大节点数。

  • 可接受性- 算法的一个属性，始终找到最佳解决方案。

  • 分支因子- 问题空间图中子节点的平均数量。

  • 深度- 从初始状态到目标状态的最短路径的长度。

暴力搜索策略

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

要求 -

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

广度优先搜索

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

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

最坏情况下创建的节点总数为 b + b 2 + b 3 + … + b d。

缺点- 由于保存每一级节点以用于创建下一级，因此会消耗大量内存空间。存储节点的空间需求是指数级的。

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

广度优先搜索

深度优先搜索

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

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

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

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

深度优先搜索

双向搜索

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

从初始状态开始的路径与从目标状态开始的逆路径连接起来。每次搜索仅完成总路径的一半。

统一成本搜索

排序是通过增加到节点的路径的成本来完成的。它总是扩展成本最低的节点。如果每个转换具有相同的成本，则它与广度优先搜索相同。

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

缺点- 可以有多个成本≤ C* 的长路径。统一成本搜索必须探索所有这些。

迭代深化深度优先搜索

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

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

交互式深化 DF 搜索

各种算法复杂度比较

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

标准 广度优先 深度优先 双向 统一成本 互动深化
时间 BD _ 米_ BD /2 BD _ BD _
空间 BD _ 米_ BD /2 BD _ BD _
最优性 是的 不 是的 是的 是的
完整性 是的 不 是的 是的 是的

知情（启发式）搜索策略

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

启发式评估函数

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

纯启发式搜索

它按照启发值的顺序扩展节点。它创建两个列表，一个用于已展开的节点的关闭列表，一个用于已创建但未展开的节点的打开列表。

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

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 )，返回解状态。

start with k randomly generated states
loop
   generate all successors of all k states
   if any of the states = solution, then return the state
   else select the k best successors
end

模拟退火

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

我们最初将温度设置得很高，然后随着算法的进行让它慢慢“冷却”。当温度较高时，允许算法以较高的频率接受较差的解。

开始

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

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

结尾

旅行商问题

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

Start
   Find out all (n -1)! Possible solutions, where n is the total number of cities.
   Determine the minimum cost by finding out the cost of each of these (n -1)! solutions.
   Finally, keep the one with the minimum cost.
end
旅行商问题