algorithm - 需要澄清 A* 算法

我认为使用 A* 算法应该是 SAEFG，但答案是 SBEFG。现在我的教授是一个无用的人。有人可以解释为什么 SBEFG 吗？

标签： algorithm

示例中使用的启发式函数并不一致。为了使启发式一致，以下等式必须为真：

对于每个节点 x, y：h(x) + w(x, y) >= h(y)，其中 h(v) 是节点 v 的启发函数值，w(x, y) 是两个节点之间的实际距离节点 x 和 y。

在本例中，h(B) = 13, h(E) = 4 和 w(B, E) = 6。如您所见，h(E) + w(B, E) = 10 < h(B) ，所以启发式不一致。

这意味着什么？好吧，具有这种启发式的 A* 搜索在图中可能不是最优的。如果不重新访问某些节点，它可能找不到最短路径。

在这个例子中作者可能假设重新访问 E 节点，所以 A* 将首先到达 C，然后是 A、E、F、D、B，它应该从 B 再次访问 E，因为 SBE 比 SAE 短，然后再访问F 并转到 G。最后的路径将是 SBEFG。