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^米	B^D/2	b^d	b^d
空间	b^d	B^米	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）扩展节点。它是使用优先级队列实现的。

缺点 - 它可能会卡在循环中。这不是最佳的。

本地搜索算法

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

爬山搜索

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

函数爬坡（问题），返回一个局部最大值的状态。

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）） >随机（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