搜索与问题解决

搜索与问题解决是人工智能的一个分支，它将任务表述为对状态或配置空间的探索，并寻找能够达到目标的行动、赋值或移动序列。

Definition

基于搜索的问题解决将任务表示为初始状态、一组转换状态的行动、一个目标测试和一条路径成本，并通过系统地探索可达状态来解决问题，直到找到目标状态（或到达目标状态的最低成本路径）。

Scope

该领域涵盖了将问题表述为状态空间以及探索这些空间的算法：包括广度优先和深度优先等无信息（盲目）搜索，A*和贪婪最佳优先等有信息（启发式）搜索，用于双人对抗游戏的对抗搜索，以及约束满足。它探讨了如何将问题建模为状态、行动和目标测试，以及如何分析完备性、最优性、时间和空间。它不包括从数据中学习搜索启发式或评估函数，这属于独立的机器学习子领域。

Sub-topics

• adversarial search and game playing
• constraint satisfaction problems
• heuristic search and a star
• state space search

Core questions

• 如何将现实世界的任务表述为具有状态、行动和目标测试的状态空间？
• 搜索算法何时是完备的（如果存在解决方案，则保证能找到）和最优的（保证能找到成本最低的解决方案）？
• 启发式函数如何引导搜索走向目标，同时保持最优性？
• 如何通过剪枝或有信息排序来控制状态空间的组合爆炸？
• 当对手选择部分行动时，搜索会如何变化？

Key concepts

• 状态空间
• 搜索树和搜索图
• 无信息（盲目）搜索
• 启发式函数
• 可采纳性和一致性
• A*搜索
• 分支因子和搜索深度
• 完备性和最优性
• 约束满足

Key theories

可采纳启发式与A*最优性

如果启发式函数从不高估到达目标的真实成本（是可采纳的），A*搜索将以f = g + h的最佳优先顺序扩展节点，并保证返回最优解；一致性额外保证没有节点会被重复扩展。

无信息搜索与有信息搜索的权衡

盲目策略（广度优先、统一成本、深度优先、迭代加深）仅在节点排序上有所不同，并且在没有领域知识的情况下提供保证，而对剩余成本的启发式估计可以显著减少探索空间，但如果启发式不可采纳，则可能失去最优性。

问题表述为状态空间搜索

一旦将各种任务转化为通过行动连接的状态上的搜索，它们就变得可处理，因此状态表示和操作符的选择成为决定分支因子和解决方案深度的核心设计决策。

Clinical relevance

搜索是大量实际系统的基础：路线规划和导航（道路网络上的A*算法）、谜题和游戏引擎、自动化配置和调度、机器人运动规划，以及作为物流和运筹学中使用的自动化规划和约束求解器的支柱。

History

搜索自人工智能早期就一直是其核心，纽厄尔和西蒙的通用问题求解器（General Problem Solver，1950年代末）将智能定义为在问题空间中的搜索。A*算法（Hart, Nilsson, Raphael, 1968）为启发式搜索提供了严格的最优性基础，而珀尔（Pearl）1984年的专著则系统化了启发式搜索理论。该框架仍然是人工智能教科书中的标准组织视角。

Key figures

• Nils J. Nilsson
• Judea Pearl
• Peter E. Hart
• Bertram Raphael
• Allen Newell
• Herbert A. Simon

Seminal works

• hart1968
• pearl1984
• russell2020

Frequently asked questions

无信息搜索和有信息搜索有什么区别？

无信息（盲目）搜索，例如广度优先或深度优先搜索，不使用任何关于状态与目标接近程度的信息，纯粹根据状态空间的结构进行探索。有信息（启发式）搜索使用对到达目标的剩余成本的估计来优先扩展哪些状态，这可能效率更高。

为什么A*算法被广泛使用？

A*算法将从起点到当前节点的实际成本（g）与到目标的启发式估计成本（h）结合起来，当启发式函数是可采纳的时，它保证能找到最优解，同时通常比无信息搜索探索更少的状态。这种最优性和效率的平衡使其成为路径规划的默认选择。