一、定义与核心思想

启发式搜索（Informed Search）是一种利用启发信息（Heuristic Information）指导搜索方向的算法策略，旨在减少盲目遍历的无效路径，提升搜索效率。其核心思想是通过设计估价函数（Evaluation Function）对搜索分支进行优先级排序，优先扩展更接近目标的节点。

1. 核心要素

• 启发函数（h(n)）：估计节点n到目标节点的代价（如曼哈顿距离、欧几里得距离）；
• 实际代价（g(n)）：从起点到节点n的实际路径代价；
• 估价函数（f(n)）：综合g(n)和h(n)的优先级函数，常见形式为f(n) = g(n) + h(n)。

2. 与无信息搜索的对比

特性	无信息搜索	启发式搜索
搜索方向	盲目遍历（如BFS/DFS）	基于启发信息引导方向
效率	低（指数级复杂度）	高（多项式级复杂度）
适用场景	小规模、结构简单的问题	大规模、复杂优化问题
最优性	部分算法保证（如BFS/UCS）	可保证（需h(n)满足可采纳性）

3. 各算法详解

• 1.贪婪搜索
• 2.A星算法

版权所有

版权归属：NateHHX

许可证：署名 4.0 国际 (CC-BY-4.0)