启发式搜索与A*算法

启发式搜索利用对到达目标所需剩余成本的问题特定估计来指导优先探索哪些状态；A*是其典型的算法，它按照已花费成本与估计剩余成本之和的顺序扩展状态。

Definition

启发式搜索是一种知情搜索，它使用结合了从起点已知成本和剩余成本启发式估计的评估函数来排序边界；当h可采纳时，A*使用f(n) = g(n) + h(n)并且是最优的。

Scope

本主题涵盖了知情（启发式）搜索策略，以最佳优先搜索和A*算法为核心，包括启发式函数的设计和属性（可采纳性、一致性/单调性），这些属性所赋予的最优性和效率保证，以及内存受限的变体，如迭代加深A*（IDA*）。它讨论了启发式如何构建（松弛问题、模式数据库）以及它们如何在准确性和计算之间进行权衡。从数据中学习启发式属于机器学习子领域。

Core questions

• 什么使启发式可采纳，以及为什么可采纳性保证A*算法的最优性？
• 一致性（单调性）如何增强保证并防止节点重新扩展？
• 如何设计好的启发式，例如从问题的松弛版本中设计？
• IDA*等内存受限变体如何在有限空间内保持最优性？

Key concepts

• 评估函数 f = g + h
• 可采纳启发式
• 一致（单调）启发式
• 贪婪最佳优先搜索
• A*搜索
• 迭代加深A* (IDA*)
• 启发式支配
• 松弛问题和模式数据库

Key theories

可采纳启发式下的A*最优性

当启发式h从不高估真实的剩余成本时，A*会按f = g + h递增的顺序扩展节点，并保证返回成本最低的路径；在所有使用相同启发式信息的算法中，A*是最优有效的。

通过松弛设计启发式

可采纳启发式可以通过解决问题的松弛版本（即对行动限制较少的版本）系统地推导出来，因为较简单问题的精确成本是原始问题的下界；支配性（信息更丰富）的启发式会扩展更少的节点。

内存受限的启发式搜索

迭代加深A*通过增加f成本阈值进行连续的深度优先搜索，以解决方案深度线性增长的内存实现类似A*的最优性。

Clinical relevance

启发式搜索为地图和游戏中的路线查找、机器人中的运动规划以及自动化规划器和解谜器内部的搜索引擎提供了动力；启发式设计的实践艺术直接决定了大型问题是否能在可接受的时间内解决。

History

A*算法由Hart、Nilsson和Raphael（1968）引入，为启发式搜索提供了形式化的最优性基础。Pearl于1984年出版的专著《Heuristics》提供了权威的理论处理，Korf于1985年提出的IDA*解决了A*的内存成本问题。这些成果仍然是人工智能教育的核心内容。

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

什么是可采纳启发式？

如果启发式从任何状态到达目标的真实成本从不被高估，则称其为可采纳的。可采纳性是A*算法保证找到最优（成本最低）解决方案的条件。

贪婪最佳优先搜索和A*有什么区别？

贪婪最佳优先搜索仅根据启发式（h）扩展看起来离目标最近的状态，这种方法速度快但可能远非最优。A*则加上了迄今为止实际发生的成本（g），通过f = g + h进行扩展，当启发式可采纳时，这能保持最优性。