algorithm - 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。启发式搜索只是尝试加快搜索速度，但不会使搜索失败，最坏的情况是比没有启发式搜索需要更长的时间。