Dijkstra算法的启发式函数是否满足可采纳性?(面试题)
Dijkstra算法的启发式函数是否具有可采纳性?
好问题!先明确核心概念:可采纳性(admissibility)的定义是:一个启发式函数h(n)是可采纳的,当且仅当对于所有节点n,h(n) ≤ h*(n)——这里的h*(n)是从节点n到目标节点的实际最小路径成本,而且路径成本必须是非负的(这也是Dijkstra算法能正确运行的前提)。
回到你的问题:Dijkstra算法确实是A*的一个特例,它使用的启发式函数是h(n) = 0。那这个函数满足可采纳性吗?
答案是肯定的。因为对于任何节点n,从它到目标的实际最小成本h*(n)不可能是负数(毕竟路径里的边权重都是非负的),所以0 ≤ h*(n)的关系必然成立,完全符合可采纳性的定义。
其实还可以延伸一点:这个h(n)=0的启发式不仅可采纳,还是**单调(一致)**的启发式——不过这是额外的知识点,面试里如果能提一句,说不定能加分哦。
本质上,面试问这个问题,是在考察你对A*和Dijkstra的底层关联,以及可采纳性核心定义的理解,很多人知道两者的从属关系,但未必能直接把启发式和可采纳性挂钩验证。
内容的提问来源于stack exchange,提问作者Sparsh




