这两种算法都属于“最佳优先搜索”算法的范畴，这种算法可以在探索搜索空间的同时使用目前获得的知识，记为$g(n)$，和一个启发式函数，表示为$h(n)$，它估计每个节点到目标节点的距离$n$在搜索空间中（通常表示为图形）。

这些搜索算法中的每一个都为每个节点定义了一个“评估函数”$n$在图形（或搜索空间）中，表示为$f(n)$. 这个评价函数用来判断在搜索的时候哪个节点先“展开”，即先从“边缘”（或“前沿”，或“边界”）中去掉哪个节点，从而“访问”它的孩子。一般来说，“最佳优先”类别中的算法之间的区别在于评估函数的定义$f(n)$.

在贪心BFS算法的情况下，评价函数为$f(n) = h(n)$，即贪心BFS算法首先扩展估计到目标距离最小的节点。所以，贪婪的 BFS 不使用“过去的知识”，即$g(n)$. 因此它的内涵是“贪婪”。总的来说，贪心 BST 算法是不完备的，也就是说，走一条没有达到目标的路径总是有风险的。在贪心 BFS 算法中，边界（或边缘或前沿）上的所有节点都保存在内存中，已经扩展的节点不需要存储在内存中，因此可以被丢弃。一般来说，贪婪的 BFS也不是最优的，也就是说，找到的路径可能不是最优的。一般来说，时间复杂度是$\mathcal{O}(b^m)$， 在哪里$b$是（最大）分支因子和$m$是搜索树的最大深度。空间复杂度与边缘节点的数量和找到的路径的长度成正比。

在A* 算法的情况下，评估函数是$f(n) = g(n) + h(n)$， 在哪里$h$是一个可接受的启发式函数。“星”，通常用星号表示*，是指 A* 使用了一个可接受的启发式函数，这本质上意味着 A* 是最优的，即它总是找到起始节点和目标之间的最优路径节点。A* 也是完整的（除非在搜索空间中有无限多的节点要探索）。时间复杂度为$\mathcal{O}(b^m)$. 但是，A* 需要在搜索时将所有节点保留在内存中，而不仅仅是边缘节点，因为 A* 本质上执行的是“穷举搜索”（即“知情”，因为它使用启发式函数）。

综上所述，贪心 BFS 是不完整的，不是最优的，时间复杂度为$\mathcal{O}(b^m)$以及可以是多项式的空间复杂度。A* 是完备的、最优的，它的时间和空间复杂度为$\mathcal{O}(b^m)$. 所以，一般来说，A* 比贪婪的 BFS 使用更多的内存。当搜索空间很大时，A* 变得不切实际。但是，A* 也保证在起始节点和目标节点之间找到的路径是最优路径，并且算法最终会终止。另一方面，贪婪 BFS 使用较少的内存，但不提供 A* 的最优性和完整性保证。因此，哪种算法是“最好的”取决于上下文，但两者都是“最好的”——优先搜索。

注意：在实践中，您可能不会使用任何这些算法：例如，您可以使用IDA*代替。

根据 Stuart Russel 和 Peter Norvig 所著的《人工智能：现代方法》（第 3 版）一书，特别是第3.5.1 节贪婪的最佳优先搜索（第 92 页）

贪婪的最佳优先搜索试图扩展最接近目标的节点，理由是这可能会很快导致解决方案。因此，它仅使用启发式函数来评估节点；那是，$f(n) = h(n)$.

在同一部分，作者给出了一个例子，表明贪婪的最佳优先搜索既不是最优的，也不是完整的。

在第3.5.2 节 A* 搜索：最小化同一本书的总估计解决方案成本（第 93 页）中，它指出

A* 搜索通过组合来评估节点$g(n)$，到达节点的成本，以及$h(n)$，从节点到目标的成本

$$f(n) = g(n) + h(n).$$

自从$g(n)$给出从起始节点到节点的路径成本$n$， 和$h(n)$是最便宜路径的估计成本$n$为了目标，我们有$f(n)$= 最便宜的解决方案的估计成本$n$.

因此，如果我们试图找到最便宜的解决方案，首先尝试的合理方法是具有最低值的节点$g(n) + h(n)$. 事实证明，这种策略不仅仅是合理的：假设启发式函数$h(n)$满足一定条件，A* 搜索既完整又最优。该算法与统一成本搜索相同，只是 A* 使用$g + h$代替$g$

您所说的并非完全错误，但是如果启发式函数 h 是可接受的，则 A* 算法将变得最优和完整，这意味着该函数永远不会高估达到目标的成本。在这种情况下，A* 算法比贪心搜索算法要好得多。