A*算法搜索

Question

我有一棵像下面这样的树。边缘上的数字是成本 (g)，节点中的数字是启发式函数 (h) 与目标的估计距离。目标以灰色阴影显示。

如果我从S开始，路线A星搜索（

f(x) = g(x) + h(x)

）的遍历是否如下：

S>B>H>M

？

这是一个有趣的问题，因为如果我们查看贪婪搜索算法，其中确定下一步移动的函数 =

f(x) = h(x)

，我们将仅考虑节点中的值并选择最少的一个。基于此，我们将从 S 开始，然后继续到 A（最低值最佳），但最左边的分支是不正确的，因为它不会通向任何目标节点。我假设贪婪搜索会因这棵树而失败，这是正确的吗？

Answer 1

首先，这不是一棵树，它是一个DAG，因为有些节点有多个父节点。

其次，是的，A* 将通过此启发式返回正确的结果，因为该启发式是 可接受的 （即它永远不会高估真实成本）。如果不是这样，A* 可能不会返回正确的结果。

Answer 2

不，贪心搜索会遍历S->A->D->B->F。 启发式搜索只是尝试加快搜索速度，但不会导致搜索失败，最坏的情况只是比没有启发式搜索花费的时间更长。

Answer 3

它是 S->B->A，因为 B 的 f(n) = g(n) + h(n) 是 4，A = 5 是该图中的最小值。所以它会先到B，然后到A