问A*搜索给出的次优解

EN

启发式h(n)不一致。

让我首先定义一个启发式函数什么时候是一致的。

h(n) is consistent if  
– for every node n
– for every successor n' due to legal action a 
– h(n) <= c(n,a,n') + h(n')

这里很明显'A‘是节点'B’的后继者，但是h(B) > h(A) + c(A,a,B)

因此，启发式函数不是一致的/单调的，因此A*不需要给出最优解。

老实说，我不明白A*怎么能用给定的启发式返回一个次优解。原因很简单:给定的启发式是可接受的(甚至是单调/一致的)。

h(s) <= h*(s) for each s in the graph

您可以自己检查这一点，将每个节点中的h值与到g的最短路径的成本进行比较。

考虑到A*的最优性，我不明白它如何返回次优解，当然，次优解应该是S -> A -> G。

它可能返回次优解的唯一方法是，一旦找到通向目标的前沿节点的操作，它就会停止(因此有一条通往目标的路径)，，但这不是A*。