上一节:
下一节:

  人工智能（AI） - 流行搜索算法

  • 简述

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

  • 单代理寻路问题

    诸如 3X3 8格、4X4 15格 和 5X5 24格拼图等游戏是单代理寻路挑战。它们由带有空白瓷砖的瓷砖矩阵组成。玩家需要通过将瓷砖垂直或水平滑动到空白空间来排列瓷砖，以实现某些目标。
    单代理寻路问题的其他示例是旅行商问题、魔方和定理证明。

  • 搜索术语

    • 问题空间− 它是搜索发生的环境。（一组状态和一组操作符来改变这些状态）
    • 问题实例− 初始状态 + 目标状态。
    • 问题空间图− 它代表问题状态。状态由节点表示，运算符由边表示。
    • 问题的深度− 从初始状态到目标状态的最短路径或最短运算符序列的长度。
    • 空间复杂性− 存储在内存中的最大节点数。
    • 时间复杂性− 创建的最大节点数。
    • 可容性− 算法总是找到最优解的特性。
    • 分支因子− 问题空间图中的平均子节点数。
    • 深度− 从初始状态到目标状态的最短路径长度。

  • 蛮力搜索策略

    它们最简单，因为它们不需要任何特定领域的知识。它们适用于少数可能的状态。
    要求 -
    • 状态描述
    • 一组有效的运算符
    • 初始状态
    • 目标状态描述

    广度优先搜索

    它从根节点开始，首先探索相邻节点，然后向下一级邻居移动。它一次生成一棵树，直到找到解决方案。它可以使用FIFO队列数据结构来实现。此方法提供了解决方案的最短路径。
    如果branching factor（给定节点的平均子节点数）= b 和深度 = d，然后级别 d = b d的节点数。
    在最坏情况下创建的节点总数为 b + b 2 + b 3 + ... + b d。
    Disadvantage− 由于保存了每一级节点用于创建下一个节点，因此会消耗大量内存空间。存储节点的空间需求是指数级的。
    它的复杂性取决于节点的数量。它可以检查重复的节点。
    广度优先搜索

    深度优先搜索

    它是用 LIFO 堆栈数据结构递归实现的。它创建与广度优先方法相同的节点集，只是顺序不同。
    由于在从根到叶节点的每次迭代中都存储了单个路径上的节点，因此存储节点的空间需求是线性的。以分支因子b和深度为m，存储空间为bm。
    Disadvantage− 该算法可能不会终止并在一条路径上无限继续。这个问题的解决方案是选择一个截止深度。如果理想的截止值是d，并且如果选择的截止值小于d，那么这个算法可能会失败。如果选择的截止值大于d，则执行时间会增加。
    它的复杂性取决于路径的数量。它无法检查重复节点。
    深度优先搜索

    双向搜索

    它从初始状态向前搜索，从目标状态向后搜索，直到两者相遇以识别共同状态。
    初始状态的路径与目标状态的反向路径连接。每次搜索最多只完成总路径的一半。

    统一成本搜索

    排序是通过增加到节点的路径成本来完成的。它总是扩展成本最低的节点。如果每个转换具有相同的成本，则它与广度优先搜索相同。
    它以成本递增的顺序探索路径。
    Disadvantage− 可以有多个成本≤ C* 的长路径。统一成本搜索必须全部探索。

    迭代深化深度优先搜索

    它执行深度优先搜索到级别 1，重新开始，执行完整的深度优先搜索到级别 2，并以这种方式继续直到找到解决方案。
    在生成所有较低节点之前，它永远不会创建节点。它只保存一堆节点。该算法在找到深度d的解时结束。在深度d处创建的节点数为 b d，在深度d-1处创建的节点数为 b d-1。
    交互式深化 DF 搜索

    各种算法复杂度的比较

    让我们看看基于各种标准的算法的性能 -
    标准 广度优先 深度优先 双向 统一成本 互动深化
    时间 b d b m b d/2 b d b d
    空间 b d bm b d/2 b d b d
    最优性 Yes No Yes Yes Yes
    完整性 Yes No Yes Yes Yes

  • 知情（启发式）搜索策略

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

    启发式评估函数

    他们计算两个状态之间最佳路径的成本。滑动棋子游戏的启发式函数是通过计算每个棋子从其目标状态移动的次数并为所有棋子添加这些移动次数来计算的。

    纯启发式搜索

    它按照启发式值的顺序扩展节点。它创建两个列表，一个用于已展开节点的关闭列表和一个用于已创建但未展开节点的打开列表。
    在每次迭代中，扩展具有最小启发式值的节点，创建其所有子节点并将其放置在封闭列表中。然后，将启发函数应用于子节点，并根据其启发值将它们放置在打开列表中。较短的路径被保存，较长的路径被丢弃。

    A * 搜索

    它是 Best First 搜索的最著名形式。它避免扩展已经很昂贵的路径，而是首先扩展最有希望的路径。
    f(n) = g(n) + h(n)，其中
    • g(n) 到达节点的成本（到目前为止）
    • h(n) 从节点到目标的估计成本
    • f(n) 通过 n 到目标的估计路径总成本。它是通过增加 f(n) 使用优先级队列实现的。

    贪婪的最佳优先搜索

    它扩展估计最接近目标的节点。它基于 f(n) = h(n) 扩展节点。它是使用优先级队列实现的。
    Disadvantage− 它可能会陷入循环。这不是最优的。

  • 本地搜索算法

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

    爬山搜索

    它是一种迭代算法，从问题的任意解决方案开始，并尝试通过逐步更改解决方案的单个元素来找到更好的解决方案。如果更改产生了更好的解决方案，则将增量更改视为新解决方案。重复这个过程，直到没有进一步的改进。
    函数爬山（问题），返回一个局部最大值的状态。 
    
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
    Disadvantage− 该算法既不完整，也不是最优的。

    局部波束搜索

    在这个算法中，它在任何给定时间都拥有 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 则接受 else if 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
    旅行商问题
上一节:
下一节: