搜索是人工智能的一个核心基础领域,它的本质是：在一个可能的状态空间中，系统地探索，以找到从初始状态到达目标状态的最佳路径或解决方案。
（图片来源网络，侵删）
可以把它想象成在一张巨大的地图上,从起点（初始状态）出发，寻找通往终点（目标状态）的最佳路线，这里的“最佳”可以定义为路径最短、成本最低、用时最少等。
为什么搜索技术在AI中如此重要？
搜索是许多AI任务的基石,
- 路径规划：GPS导航、机器人行走、游戏中的角色寻路。
- 问题求解：下棋（国际象棋、围棋）、解谜（如八数码难题）。
- 定理证明：在数学逻辑中寻找一个证明序列。
- 自动规划：为机器人或生产线规划一系列动作。
- 自然语言处理：在句法分析中，寻找符合语法的句子结构。
可以说,任何可以被建模为“状态-动作”序列的问题，都可以用搜索技术来解决。
搜索技术的核心要素
一个搜索问题通常包含以下几个关键部分：
（图片来源网络，侵删）
- 状态空间：问题所有可能状态的集合，在国际象棋中，一个状态就是当前棋盘上所有棋子的位置。
- 初始状态：问题开始时的状态，棋局的初始布局。
- 目标测试：用于判断一个状态是否是目标状态的条件，国际象棋中的“将死”对方。
- 动作/算子：可以执行的操作，它能将一个状态转变为另一个状态，国际象棋中的“移动马”。
- 路径成本：从一个状态通过一系列动作到达另一个状态所付出的代价，通常用路径长度或每步的成本之和来衡量。
搜索算法的分类
搜索算法主要分为两大类：无信息搜索和有信息搜索。
无信息搜索
这类算法不利用任何关于问题的额外信息（目标在哪个方向”），仅根据搜索策略来探索状态空间，它们也称为“盲目搜索”。
| 算法名称 | 策略 | 特点 | 适用场景 |
|---|---|---|---|
| 广度优先搜索 | 按层次的“先来后到”，逐层扩展。 | - 最优完备：如果每步成本相同，一定能找到最短路径。 - 空间复杂度高：需要存储所有已生成的节点，内存消耗巨大。 |
当状态空间不大，或需要找到绝对最短路径时。 |
| 深度优先搜索 | 沿着一个分支一直探索到底，再回溯。 | - 空间复杂度低：只需要存储当前路径的节点，内存消耗小。 - 不完备：可能陷入无限循环。 - 非最优：找到的路径不一定是最短的。 |
当状态空间非常大，且已知解在较深处时，常用于图遍历。 |
| 深度受限搜索 | 为DFS设置一个深度限制，防止无限深入。 | 解决了DFS的无限循环问题，但限制设置不当可能导致找不到解。 | 对DFS的改进，用于防止搜索过深。 |
| 迭代加深深度优先搜索 | 从深度限制为0开始，逐步增加限制，直到找到解。 | - 结合了BFS的最优性和DFS的低空间复杂度。 - 完备且最优（在单位成本下）。 - 对于某些问题，会重复访问节点，效率略低。 |
当最短解的深度未知，且状态空间较大时，是一个非常实用的算法。 |
有信息搜索
这类算法利用一个启发式函数来评估哪个状态“更有希望”通向目标，这使得搜索更有方向性，效率更高，启发式函数通常记作 h(n)，表示从节点 n 到目标状态的估计成本。
| 算法名称 | 策略 | 特点 | 启发式函数示例 |
|---|---|---|---|
| 贪心最佳优先搜索 | 总是扩展 h(n) 值最小的节点。 |
- 速度快，通常能快速找到一个解。 - 不完备：可能陷入局部最优，找不到全局最优解。 - 非最优：找到的路径不一定是最短的。 |
八数码难题：h(n) = 当前状态中，数字错位的格子数。导航： h(n) = 当前位置到目标位置的直线距离（曼哈顿距离）。 |
| *A 算法** | 最强大、最常用的搜索算法之一，它综合了路径成本和启发式估计，扩展 f(n) 值最小的节点，f(n) = g(n) + h(n)。- g(n)：从初始状态到节点 n的实际成本。- h(n)：从节点 n到目标状态的估计成本。 |
- 完备：在大多数情况下能找到解。 - 最优：如果启发式函数是可采纳的（即从不高估实际成本），则一定能找到最优解。 - 效率非常高，是路径规划领域的黄金标准。 |
八数码难题：曼哈顿距离（每个数字到其目标位置的水平+垂直距离之和）。 导航：欧几里得距离或曼哈顿距离。 |
| *A 的变体** | - 权重A** (`f(n) = g(n) + w h(n)w > 1`)：通过提高启发式函数的权重，加快搜索速度，但牺牲了最优性，IDA**迭代加深的A，结合了迭代加深和A*的优点，内存占用低。 | 在速度和最优性之间进行权衡。 |
关于启发式函数的重要概念：
（图片来源网络，侵删）
- 可采纳性：一个启发式函数
h(n)如果是可采纳的，意味着它永远不会高估到达目标的真实成本，即h(n) ≤ h*(n)，h*(n)是从n到目标的实际最小成本，这是A*算法找到最优解的关键。 - 一致性：比可采纳性更强的条件，如果对于任意节点
n及其后继节点n'，满足h(n) ≤ cost(n, n') + h(n')，则称该启发式函数是一致的，一致性一定保证可采纳性，并且能避免A*算法在某些情况下的重复扩展。
搜索技术的挑战与发展
- 状态空间爆炸：对于复杂问题（如围棋），状态空间极其庞大，甚至超过了宇宙中的原子数量，传统的搜索算法完全无法应对。
- 局部最优陷阱：贪心算法和A*算法都可能因为启发式函数的误导而陷入局部最优解，无法找到全局最优解。
- 启发式函数的设计：一个好的启发式函数是搜索成功的关键，但设计一个好的启发式函数本身就是一项挑战。
现代发展与结合
为了应对这些挑战,现代AI将搜索技术与其它方法结合，发展出更强大的技术：
- 局部搜索：不关心路径，只关心当前状态，通过不断改进当前状态来寻找解，例如爬山算法、模拟退火、遗传算法，它们非常适合优化问题。
- 博弈树搜索：专门用于双人博弈（如象棋、围棋），其核心是极小化极大算法，并结合Alpha-Beta剪枝来大幅剪掉不会成为最优选择的分支，极大提高了效率。AlphaGo的成功，就是将蒙特卡洛树搜索与深度学习网络（策略网络和价值网络）结合的典范。
- 与机器学习结合：使用机器学习模型来学习一个更好的启发式函数
h(n)，或者直接学习从状态到动作的映射策略，从而指导搜索过程，大大减少搜索空间。
| 类别 | 算法 | 核心思想 | 优点 | 缺点 |
|---|---|---|---|---|
| 无信息搜索 | BFS | 逐层扩展 | 最优完备 | 空间复杂度高 |
| DFS | 沿一个分支深挖 | 空间复杂度低 | 不完备，非最优 | |
| IDDFS | 逐步增加深度限制 | 结合BFS和DFS优点 | 可能重复计算 | |
| 有信息搜索 | 贪心最佳优先 | 选“看起来最近”的 | 速度快 | 不完备，非最优 |
| **A*** | f(n) = g(n) + h(n) |
完备、最优（可采纳时）、高效 | 需要一个好的启发式函数 | |
| 现代发展 | 局部搜索、MCTS、与深度学习结合 | 摒弃穷举，利用智能和概率 | 能解决极其复杂的问题 | 算法复杂，需要大量训练 |
搜索技术是AI领域的基石,它为我们提供了一种系统化解决问题的通用框架，从简单的BFS/DFS到强大的A*，再到与机器学习结合的现代方法，搜索技术不断演进，持续推动着人工智能解决更复杂、更现实问题的能力。
