导读：Russell 与 Norvig 第 3 章的搜索算法家族里，A* 的地位来自两条定理：可采纳启发式保证最优，一致性保证首次扩展即最优。
A* 与评价函数
评价函数等于已花代价加启发式估计。可采纳启发式（不高估剩余代价）保证 A* 树搜索最优；一致启发式（满足三角不等式且目标处为零）保证图搜索（closed list 剪枝）也最优。
直觉：评价函数是必经该节点的解的成本下界。最优解上任何节点其值不超过最优解成本，超过者可以安全丢弃——A* 就是在用这个下界做有序展开。
启发式的质量学
支配关系：处处更大且仍可采纳的启发式展开节点不多于较小的。有效分支因子是衡量启发式实力的实操指标。
启发式设计三源：问题松弛（滑块问题少一个约束即代价可忽略的下界问题）、子问题模式数据库（PDB）、双向搜索交集。可采纳启发式取最大值组合仍保可采纳。
工程谱系
内存紧张：IDA*（迭代加深）或 SMA*。均匀代价（每步同代价）：Dijkstra 即零启发式的 A*。地图寻路的跳点搜索与层级规划是领域加速；状态空间巨大且无可采纳启发式时转向 MCTS（第 5 章的蒙特卡洛树搜索）。
常见误区
- 图搜索（closed list）配仅可采纳（非一致）的启发式，可能错过最优路径。
- 启发式凭直觉高估（不可采纳）后仍在宣称找最优。
吃透自检
- 能证明一致则可采纳并给出反例说明逆命题不真
- 能推导 A* 最优性（一致性情形）
- 能从问题松弛构造一个可采纳启发式