人工智能中的搜索策略

引言

在人工智能中，搜索是一种由算法用于识别解决方案或应对挑战的潜在路径的有序方法。决策搜索策略在人工智能中至关重要，因为它们能够使系统在各种复杂领域中做出决策，包括简单的游戏算法、现实世界的规划和优化问题。合适的搜索机制可以提高设计的人工智能系统的效率、速度和解决问题的能力。

人工智能中的搜索策略

搜索策略分为无信息搜索和有信息搜索。 需要注意的是，无信息搜索除了发现实际问题之外，没有更多信息，而有信息搜索则利用启发式方法更精确、更有效地指导搜索。

无信息搜索策略

无信息或盲目搜索策略在没有任何关于待解决问题领域的进一步知识的情况下，对一系列选择进行优化。它们需要很高的计算资源才能达到目标，并且在对搜索环境的先验知识有限时最有效。

广度优先搜索 (BFS)

BFS（广度优先搜索）的一个特点是，当前层的每个节点都会在进入下一层之前被扩展。BFS是高效的（如果存在答案，它就是完整的搜索；如果每一步的成本都相同，它就是最优的）。然而，它是一种内存密集型数据结构，因为必须在进入下一层之前保存当前层的所有节点。

• 迭代加深广度优先搜索 (IDBFS)：BFS 和 DFS 在此处相结合，通过逐级递增进行，直到达到解决方案的深度。它内存效率高，在搜索需要达到的最大深度未知时很有用。

应用：BFS 用于解决谜题或在非加权图中找到最短路径的情况，例如社交网络分析。

优点：当每一步的度量都相同时，可以准确地找到节点 x 到节点 y 的最短路径。

缺点：由于内存和更关键的时间复杂度取决于分支因子，因此 BFS 对于具有大或深搜索空间的问题效率不高。

深度优先搜索 (DFS)

DFS（深度优先搜索）通常会沿着树的一个分支尽可能深地搜索，然后再回溯。它比 BFS 更高效，因为它不会用某个级别的所有节点淹没程序的内存。

• 深度受限搜索 (DLS)：将搜索限制在某个程度或标准之内，低于该标准则不再搜索。它适用于解决无限路径问题，并且适用于内存有限的环境。
• 迭代加深深度优先搜索 (IDDFS)：DFS 和 BFS 交替进行深度限制和增加深度，以在搜索时间内优化内存使用。

应用：DFS 在尽快找到任何解决方案的情况下很有用，尤其是在远离起点时，例如迷宫或其他谜题。

优点：与 BFS 相比，DFS 使用的内存更少，并且适用于搜索答案可能位于树上方的空间。

缺点：它并不总是能找到最短路径，并且如果没有其他措施（例如路径深度）的帮助，可能会在循环中无限循环。

一致代价搜索 (UCS)

与 BFS 一样，UCS 代表一致代价搜索，但在这里，它关注的是路径成本而非深度。本文使用的 CNN 算法首先考虑最低成本节点；它使算法对于具有可变步长成本的问题成为最优且完整的。

应用：UCS 应用于具有不同权重的图中的路径搜索问题解决方案，例如导航或资源调度问题。

优点：确保所走路径在成本方面尽可能短。

缺点：计算成本高，因为它需要根据路径成本维护一个节点优先级队列，这在大型图问题上可能成本很高。

有信息搜索策略

有信息搜索策略应用启发式方法来决定哪些路径似乎更有可能在最短时间内到达目标。

最佳优先搜索

最佳优先搜索根据 启发式 函数从所有节点中选择最优化节点。这使其比无信息搜索更快，并且通常内存效率更高。

应用：在可以使用启发式方法将搜索引导至目标点的路径查找或其他应用中，例如任何图搜索问题，BFS 都会被采用。

优点：在能够使用出色的启发式方法的情况下，它比 BFS 或 DFS 要好得多。

缺点：如果所使用的启发式方法既不容许也不一致，它可能找不到最优路径。

A* 搜索算法

A* 搜索结合了 UCS 和最佳优先搜索的优点，使用启发式函数 f(n)=g(n)+h(n)，其中

• g(n) 表示从起始节点到节点 n 的路径成本。
• h(n) 表示从节点 n 到目标的估计成本。

A* 算法是最好、最有效的，因为在应用启发式方法时，我们假设它是可容许且一致的。

应用：A* 应用于所有需要采取最佳路线的场景，例如游戏、机器人和物流。

优点：它保证了最佳解决方案，并且由于启发式函数的指导，比 UCS 更有效。

缺点：启发式的质量决定了 A* 的性能；即使有这个算法，糟糕的启发式方法也会产生像 BFS 一样糟糕的结果。

贪婪最佳优先搜索

在此方法中，节点仅根据启发式函数 h(n) 而不是路径成本进行扩展。但是，它可能比 A* 快，但不一定是最优的。

• 局部启发式定制：还注意到，在 GBFS 中，可以根据环境的具体情况指定启发式。例如，在山区环境中，无人机导航问题的启发式方法可能是关注海拔。
• 多目标启发式：根据其公式的性质，GBFS 可以适应多个目标，包括安全性或成本等方面，以及内部结构，这使其能够适应高度非平凡的情况，例如空中交通管制。

应用：在选择不同解决方案时，如果生产快速解决方案更重要，则会应用贪婪最佳优先搜索，例如对于大多数实时策略游戏和路径查找。

优点：使用好的启发式时速度很快。

缺点：它不能保证找到两点之间的最短路径，并且不良的启发式函数会减慢其速度。

对抗性搜索

在模拟的代理人利益发生冲突的系统中，会采用对抗搜索技术。这些策略对于游戏 AI 和不利情况下的决策至关重要，目标是针对对手的行动获得最高的成功概率。

Minimax 算法

Minimax 算法假设一个玩家试图最大化得分，另一个玩家试图最小化得分。这些博弈策略包括创建游戏树、估计叶节点的值并基于评估进行决策。

应用：常见的二人游戏，如国际象棋和跳棋。

优点：它在生成零和完全信息的博弈的最佳解决方案方面非常有效。

缺点：对于涉及大型博弈树的应用来说，是不可行的。

Alpha-Beta 剪枝

Alpha-Beta 剪枝通过移除几个不会影响决策的分支来提高 Minimax 的效率。

• 多路 Alpha-Beta 剪枝：通过本质上检查高潜力或有希望的进一步移动来减少搜索树的数量，这在玩具有重要分支因子的游戏时非常有用。
• 空移动剪枝：使用跳过回合来忽略不必要的路径，适用于在战略性实时游戏中进行敏锐的决策。

应用：它在国际象棋等游戏中用于减少 Minimax 测试所考虑的节点数量。

优点：实质上提高了博弈树分析的效率，并同时获得了更深入的结果。

缺点：仍然受限于博弈树的大小，并且它不能识别概率事件。

启发式搜索和优化

有两种搜索策略；启发式搜索策略包含近似值，这使得人工智能能够在大型或复杂搜索空间的环境中更频繁地做出决策。

爬山搜索

爬山法是一种局部搜索算法，它逐步朝着具有更好启发式值（即更好的解决方案）的方向移动。这就像爬山以到达山顶。

• 随机爬山法：允许在启发式移动无助于提高启发式值的情况下进行随机移动，以避免局部最优。
• 随机重启爬山法：从各种初始解决方案执行多次搜索，以可能找到全局解决方案。

应用：应用于优化、调度和布局设计问题。

优点：简单，不需要太多大脑空间。

缺点：它可能无法摆脱局部最优，可能只会在某个最优级别之间振荡，而永远无法达到最佳解决方案。

模拟退火

与爬山法类似，模拟退火是一种概率技术，但它不将移动限制在成本更高的解决方案上。这个过程与材料退火相同，在高温下允许原子重新排列，以达到在高温下更稳定的构型。

应用：用于电路布局、规划和资源分配，其中时间因素也需考虑。

优点：避免了解决方案过于接近局部最优的问题。

缺点：性能高度依赖于冷却计划，而冷却计划相对难以设置。

遗传算法

遗传算法基于自然选择现象。它们基于潜在解决方案的种群，通过选择、交叉和变异等操作，从一代又一代地变化。

应用：这通常用于优化问题，如设计优化，动态规划在机器人学操作或神经网络训练中。

优点：可以有效地搜索给定的庞大解决方案空间，并且通常大多数时候能找到接近最优的解决方案。

缺点：它非常消耗资源，并且不总是能找到最佳解决方案。

现代方法和搜索方面的进展

然而，随着其他复杂技术（也称为搜索中的概率方法）的发展，人工智能得到了广泛应用，例如在机器人、自动驾驶汽车等领域以及实时控制系统。

蒙特卡洛树搜索 (MCTS) 在不确定环境中

MCTS 已被广泛应用于游戏和其他随机领域，比 A* 更受欢迎，因为在许多情况下无法做出确定性决策。

• 树的置信上限 (UCT)：在 MCTS 中提供探索和利用的制衡。因此，UCT 在不确定条件下（例如自动驾驶汽车的运动）选择行动方案方面发挥着至关重要的作用。
• 并行化 MCTS：也许最引人注目的特性是能够同时运行多个模拟，Tsui 的研究表明这可以提高实时搜索速度。

应用：适用于决策过程中包含概率至关重要的场景，例如金融模型。

优点：在处理复杂和不确定环境时，实现了探索与利用之间的平衡。

缺点：统计分析复杂，计算机使用采样只能给出选项或平均值。因此，结果可能并不总是准确。

强化学习 (RL) 和搜索

强化学习已在动态环境中帮助搜索，像 DQN 这样的模型能够自我学习。

• 探索与利用的平衡：强化学习使用 epsilon-greedy 或 softmax 方法来决定代理人想要多少探索或利用。
• 策略梯度方法：直接调整动作的概率，这在需要精确学习的自适应环境（如机器人肢体）中特别有用。

应用：RL 应用于实时交互式学习，包括自动驾驶、机器人控制和个性化。

优点：专为环境不断变化且问题具有反馈相互依赖性的情况而设计。

缺点：计算密集，需要大量各种方法的训练。

结论

搜索策略是人工智能问题解决的核心。从完全朴素的 BFS 和 DFS 等方法，到稍微更复杂的技术，如 A* 和 Minimax，Minimax 的各种变体，以及使用蒙特卡洛树搜索等技术，每一种方法都在特定的情况下有所帮助。因此，策略的选择取决于问题类型、计算要求以及对最优性的需求。