A* 搜索给出的次优解

Question

我不明白下图如何给出 A* 搜索的次优解决方案。

上图作为一个例子给出，其中 A* 搜索给出了一个次优解决方案，即启发式是可接受的但不一致。每个节点都有一个与其对应的启发式值，并给出遍历节点的权重。我不明白 A* 搜索将如何扩展节点。

Answer 1

启发式 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* 不需要给出最优解。

Answer 2

老实说，我不明白 A* 如何通过给定的启发式返回次优解决方案。这是出于一个简单的原因：给定的启发式是可接受的（甚至是单调/一致的）。

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

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

考虑到 A* 的最优性属性，我不知道它如何返回次优解决方案，这S -> A -> G当然应该是。

它返回次优解决方案的唯一方法是，一旦找到从边界中的节点通向目标的操作（以便有一条到达目标的路径），它就会停止，但这不会是 A*。