最佳优先搜索和广度优先搜索有什么区别？我们所说的”BFS”是指哪一种？

回答：

先回答你的第二个问题：

我们所说的”BFS”是指哪一种？

通常当我们提到BFS时，我们指的是广度优先搜索。

最佳优先搜索和广度优先搜索有什么区别

当比较这类算法时，我喜欢用机器人挖金的比喻来解释。

给定一个山丘，我们的目标是找到金子。

广度优先搜索对金子的位置没有先验知识，因此机器人只是沿着10英尺长的地带挖1英尺深，如果没有找到金子，它会再挖1英尺深。

然而，最佳优先搜索有一个内置的金属探测器，这意味着它有先验知识。当然，使用金属探测器是有成本的，还有开启它并确定从哪里开始挖掘的最佳位置的成本。

最佳优先搜索是有信息的，而广度优先搜索是无信息的，就像一个有金属探测器而另一个没有！

广度优先搜索是完整的，意思是如果存在解决方案，它会找到一个解决方案，并且在资源足够的情况下会找到最优解。

最佳优先搜索在启发式——成本/先验知识的估计器是可接受的——即它高估了到达解决方案的成本的情况下也是完整的。

BFS的图片来自http://slideplayer.com/slide/9063462/，最佳优先搜索的图片是我尝试使用Photoshop的失败作品！