一致（单调）启发式下，A*搜索f(n)=g(n)+3∗h(n)能否得到最优解？

你的理解有一定道理，但需要结合A*最优性的核心条件来完整分析：

核心前提回顾 #

标准A*搜索（f(n)=g(n)+h(n)）能保证找到最优解的关键条件是：

• 启发式函数h(n)是可采纳的（即对于所有节点n，h(n) ≤ h*(n)，其中h*(n)是n到目标的真实最小代价）；
• 如果h(n)还满足一致性（单调），即对于任意节点n和它的后继节点m，h(n) ≤ c(n,m) + h(m)（c(n,m)是n到m的代价），那么A*在第一次扩展节点n时就找到了到n的最优路径。

分析f(n)=g(n)+3h(n)的情况 #

当原h(n)是一致的，那么：

1. 原h(n)必然是可采纳的，但3h(n)可能不再可采纳（比如h(n)=h*(n)/2，此时3h(n)=1.5h*(n) > h*(n)）。
2. 是否能得到最优解？分两种情况：
   • 标准A*实现（目标节点弹出队列时返回）：即使3h(n)不可采纳，只要原h(n)一致，加权A*仍然能找到最优路径。原因是：
     对于最优路径上的任意节点n，加权f值为f(n)=g(n)+3h(n) ≤ g(n)+3h*(n) = g(n)+3*(h*(s)-g(n))（h*(s)是起点到目标的最优代价）。而对于非最优路径到达目标的路径，其总代价g_non_optimal > h*(s)，对应的f值f_non_optimal = g_non_optimal > h*(s)；而最优路径到达目标的f值就是h*(s)，因此当目标节点被从优先级队列中弹出时，必然是最优路径对应的条目。
   • 非标准实现（目标节点加入队列时就返回）：这种情况下可能会返回次优解，但这不符合标准A*的设计逻辑。

补充说明 #

通常我们说加权A*（k>1）可能返回次优解，是当h(n)仅可采纳但不一致的时候。而当h(n)一致时，加权A*仍然能保证最优性——只是它会更“贪心”地优先探索启发式值高的节点，减少扩展的节点数量，提升搜索效率。

内容的提问来源于stack exchange，提问作者Tian Zhong