外观
贪婪搜索
约 928 字大约 3 分钟
一、定义与核心思想
贪婪搜索（Greedy Best-First Search）是一种基于启发式函数的搜索算法，属于最佳优先搜索（Best-First Search）的变体。其核心思想是“优先扩展当前最接近目标的节点”，完全依赖启发式函数 h(n)（如曼哈顿距离、欧氏距离）引导搜索方向。该算法以牺牲路径最优性为代价，换取搜索速度的大幅提升，适用于实时性要求高但允许次优解的场景。
二、算法流程
- 初始化
- 创建优先级队列（Open List），将起点加入队列，初始化其启发式估值
h(n)。
- 创建优先级队列（Open List），将起点加入队列，初始化其启发式估值
- 迭代扩展
- 从队列中取出
h(n)最小的节点作为当前节点； - 若当前节点是目标，终止并回溯路径；
- 遍历其相邻节点，计算每个节点的
h(n)值，加入队列并记录父节点。
- 从队列中取出
- 终止条件
- 找到目标节点或队列为空（无解）。
三、核心特性
| 特性 | 说明 |
|---|---|
| 数据结构 | 优先级队列（按 h(n) 排序） |
| 启发式依赖 | 完全依赖 h(n)，忽略实际路径代价 g(n) |
| 时间复杂度 | O(b^m)，b为分支因子，m为最大搜索深度（可能快速逼近目标，但路径次优） |
| 空间复杂度 | O(b^m)（需存储所有扩展节点） |
| 完备性 | 不完备（若启发式函数设计不当，可能陷入无限循环或局部最优） |
| 最优性 | 不保证最优解（路径可能绕远或代价过高） |
四、应用场景
- 实时路径规划
- 游戏AI：在《魔兽世界》等MMORPG中，NPC快速生成可行路径（可能非最短但响应快）。
- 大规模状态空间探索
- 自然语言处理：优先扩展语义相关性高的候选词（如输入法联想）。
- 快速近似解需求
- 物流调度：临时生成可行路线（如快递员避开拥堵路段，但总成本未必最低）。
五、优缺点分析
优势
- 高效性：通过启发式引导快速逼近目标，搜索速度显著高于BFS、UCS等；
- 低延迟响应：适合实时交互场景（如游戏、动态地图）；
- 实现简单：仅需设计合理的启发式函数，无需复杂代价计算。
局限性
- 局部最优陷阱：若启发式函数无法正确评估剩余代价，可能生成绕远路径；
- 不完备性：在无限状态空间中可能永远找不到解；
- 路径质量不稳定：依赖启发式函数的设计质量，经验性较强。
六、改进方向
- 动态启发式调整
- 根据实时环境信息更新
h(n)，例如在交通导航中结合实时路况调整预估时间。
- 根据实时环境信息更新
- 混合策略
- 与A算法结合，初期用贪婪搜索快速缩小范围，后期切换至A保证最优性。
- 记忆化剪枝
- 记录已探索节点的局部最优路径，避免重复扩展（如爬山法的重启策略）。
七、总结
贪婪搜索通过极致的启发式引导，在实时性敏感场景中展现了独特价值。尽管其理论性质较弱（不保证最优性），但凭借低计算开销和快速响应能力，成为游戏开发、动态规划等领域的实用工具。在实际应用中需根据需求权衡效率与质量，必要时结合其他算法提升综合性能。
更新日志
2025/2/27 13:17
查看所有更新日志
fd7ad-update于d84c2-update于0e86f-update于e9284-update于
版权所有
版权归属：NateHHX