AI - 常用搜索算法

搜索是人工智能中通用的问题求解技术。有些单人游戏如拼图游戏、数独、填字游戏等。搜索算法帮助你在这些游戏中搜索特定位置。

单代理路径寻找问题

诸如 3×3 八格拼图、4×4 十五格拼图和 5×5 二十四格拼图等游戏是单代理路径寻找挑战。它们由一个带有空白格的方格矩阵组成。玩家需要通过将方格垂直或水平滑动到空白位置来排列方格，以实现某些目标。

单代理路径寻找问题的其他例子包括旅行推销员问题、魔方和定理证明。

搜索术语

• Problem Space − 搜索发生的环境。（状态集合和用于改变这些状态的操作符集合）

• Problem Instance − 初始状态 + 目标状态。

• Problem Space Graph − 表示问题状态。状态由节点表示，操作符由边表示。

• Depth of a problem − 从初始状态到目标状态的最短路径长度或最短操作符序列长度。

• Space Complexity − 存储在内存中的节点的最大数量。

• Time Complexity − 生成的节点的最大数量。

• Admissibility − 算法总是找到最优解的属性。

• Branching Factor − 问题空间图中子节点平均数量。

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

暴力搜索策略

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

要求 −

• 状态描述
• 一组有效算子
• 初始状态
• 目标状态描述

广度优先搜索

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

如果 branching factor（给定节点的平均子节点数）= b 且深度 = d，则 d 层上的节点数 = b^d。

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

缺点 − 由于每个层级的节点都会被保存以创建下一层，它消耗大量内存空间。存储节点的空间需求是指数级的。

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

深度优先搜索

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

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

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

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

双向搜索

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

从初始状态的路径与从目标状态的逆向路径连接。每次搜索仅进行到总路径的一半。

统一代价搜索

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

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

缺点 − 可能存在多个成本 ≤ C* 的长路径。统一代价搜索必须探索所有这些路径。

迭代加深深度优先搜索

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

它在生成所有较低层节点之前不会创建节点。它仅保存节点栈。当在深度 d 找到解决方案时，算法结束。在深度 d 创建的节点数为 b^d，在深度 d-1 为 b^d-1。

各种算法复杂度的比较

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

启发式（信息完整）搜索策略

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

启发式评估函数

它们计算两个状态之间最优路径的成本。对于滑块拼图游戏的启发式函数，通过计算每个拼块从其目标状态所需的移动次数并将所有拼块的移动次数相加以计算。

纯启发式搜索

它按照节点的启发式值顺序展开节点。它创建两个列表：一个用于已展开节点的closed list（关闭列表），另一个用于已创建但未展开节点的open list（开放列表）。

在每次迭代中，展开具有最小启发式值的节点，创建其所有子节点并将其放入closed list。然后，对子节点应用启发式函数，并根据其启发式值将其放入open list。较短路径被保存，较长路径被丢弃。

A * 搜索

它是Best First search（最佳优先搜索）的最著名形式。它避免展开已经代价高昂的路径，而是优先展开最具前景的路径。

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

• g(n) 到达该节点的成本（迄今为止）
• h(n) 从该节点到目标的估计成本
• f(n) 通过n到目标的路径的估计总成本。它使用按f(n)升序的priority queue（优先队列）实现。

贪心最佳优先搜索

它展开估计最接近目标的节点。它基于f(n) = h(n)展开节点。它使用priority queue实现。

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

局部搜索算法

它们从一个潜在的解开始，然后移动到邻近的解。即使在结束前随时中断，它们也能返回一个有效的解。

爬山搜索

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

function Hill-Climbing (problem), returns a state that is a local maximum.

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 个状态作为新的初始状态。这个过程持续进行，直到达到最大值为止。

function BeamSearch( problem, k), returns a solution state.

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 &plus; 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