1. 引言
搜索问题在人工智能与算法领域中占据核心地位。根据算法是否利用额外信息，搜索策略可分为两大类：
- 无信息搜索（Uninformed Search）：仅基于问题定义中的基本组件进行搜索，无法判断非目标状态的优劣。
- 有信息搜索（Informed Search）：利用启发式（Heuristic）信息，估计当前状态离目标的接近程度，从而优先探索更“有希望”的路径。
本文将深入探讨这两类搜索策略的区别、典型算法及其性能评估方式，重点介绍启发式函数的设计与优化。
2. 搜索问题定义
一个搜索问题通常由以下五个要素定义：
✅ 初始状态（Initial State）：搜索的起点。
✅ 可行动作（Actions）：在某个状态下可以执行的操作。
✅ 转移模型（Transition Model）：执行某个动作后状态如何变化。
✅ 目标测试（Goal Test）：判断当前状态是否为目标状态。
✅ 代价函数（Cost Function）：衡量从一个状态到另一个状态的代价。
🔍 核心目标：找到从初始状态到目标状态的最小代价路径。
3. 无信息搜索策略
无信息搜索也被称为“盲目搜索”，它不使用任何额外知识（如启发式函数），仅依赖问题定义中的基本组件来判断是否为目标状态。
常见算法：
- 广度优先搜索（BFS）
- 深度优先搜索（DFS）
- 一致代价搜索（UCS）
- 迭代加深搜索（IDDFS）
- 双向搜索（Bidirectional Search）
特点：
不能区分非目标状态之间的优劣
比如在8-puzzle问题中，以下两个状态对无信息算法来说是“等价”的：s1 = [ 8 3 7 2 6 5 4 1 ] s2 = [ 1 2 3 4 5 6 7 8 ]实际上，s2 只需一步即可到达目标状态，而 s1 则需多步。但无信息算法无法感知这一点。
效率较低：可能探索大量不必要节点。
4. 有信息搜索策略
有信息搜索利用启发式函数（Heuristic Function）来估计当前状态到目标状态的代价，从而优先探索更有可能通往目标的路径。
启发式函数的作用：
- 估计状态的“接近程度”
- 引导搜索方向，提高效率
常见算法：
- A*算法（A Search）*
- 最佳优先搜索（Best-First Search）
- 递归最佳优先搜索（RBFS）
- 简化内存受限A*（SMA*）
示例：
在8-puzzle问题中，可以使用以下两种启发式函数：
- h₁ = 错位棋子数
- h₂ = 曼哈顿距离总和
显然，h₂ 更准确，因为它不仅考虑是否错位，还考虑错位的程度。
5. 启发式函数的评估与优化
5.1 准确性与计算复杂度的权衡
- 理想启发式：返回从当前状态到目标的最优路径代价。
- 实际限制：获取最优路径本身就是一个搜索问题，因此启发式函数必须在准确性与计算开销之间取得平衡。
✅ 好启发式 = 代价估计接近真实值 + 计算快速
5.2 有效分支因子（Effective Branching Factor, EBF）
EBF 是衡量启发式函数效率的重要指标。它表示在搜索树中，平均每个节点生成的子节点数。
公式如下：
N + 1 = 1 + b + b² + ... + b^d = (b^(d+1) - 1) / (b - 1)
其中：
N：生成的节点数（不含起点）d：目标节点的深度b：有效分支因子
💡 EBF越接近1，说明启发式越高效，因为这意味着搜索空间被大大压缩。
5.3 启发式的“主导性”（Dominance）
如果对于所有状态 s，都有：
h₂(s) ≥ h₁(s)
则称 h₂ 主导 h₁。
在 A* 算法中：
✅ 主导性启发式将扩展更少节点，效率更高
例如：
h₁ = 错位数h₂ = 曼哈顿距离总和
实验表明，使用 h₂ 的 A* 算法比 h₁ 更快，EBF 更小。
6. 启发式函数的设计方法
设计高效启发式函数是提升搜索效率的关键。以下是三种常见方法：
6.1 松弛问题法（Relaxation）
通过放宽问题约束，使得问题更容易求解，从而将松弛问题的最优解代价作为启发式函数。
📌 示例：
在8-puzzle中，放宽“只能与空格交换”的限制，允许任意两个棋子交换位置。这样得到的最短路径代价可作为启发式函数。
6.2 子问题法（Subproblem）
解决一个简化版的子问题，并将其代价作为启发式函数。
📌 示例：
只关注8-puzzle中的前4个数字，计算其到达目标位置所需的最小步数。
6.3 数据驱动法（Learning from Data）
收集大量状态及其最优路径代价，使用机器学习训练模型，预测任意状态的代价。
📌 示例：
- 收集
(s, c)对，其中s是状态，c是代价 - 提取特征（如错位数、相邻错误数）
- 使用回归模型学习
c = f(features)
7. 总结对比
| 特性 | 无信息搜索 | 有信息搜索 |
|---|---|---|
| 是否使用启发式 | ❌ | ✅ |
| 搜索效率 | 通常较慢 | 更快（启发式有效时） |
| 实现复杂度 | 较低 | 高（需设计启发式） |
| 适用场景 | 问题结构简单或无先验知识 | 有启发式可用、追求效率 |
8. 结语
无信息搜索与有信息搜索是解决搜索问题的两大主流策略：
- 无信息搜索适用于问题结构简单、无额外知识可用的场景。
- 有信息搜索借助启发式函数，显著提升搜索效率，但需要精心设计启发式。
💡 启发式函数是关键：它决定了搜索方向与效率。设计高效启发式函数是提升搜索性能的核心挑战。
如果你正在处理路径规划、游戏AI、机器人导航等问题，建议优先尝试 A* 或其他有信息搜索策略，并结合问题特性设计合适的启发式函数。