最好的比赛广度优先

Question

best-first-search和广度优先搜索有什么区别？我们称之为“BFS”？

Answer 1

首先回答你的第二个问题：

我们称之为“BFS”？

通常，当我们提到BFS时，我们正在讨论广度优先搜索。

best-first-search和广度优先搜索之间有什么区别

比较这些算法时我喜欢咨询的类比是机器人挖掘黄金。

鉴于山，我们的目标是简单地找到黄金。

广度优先搜索没有关于金的下落的先验知识，因此机器人只是在没有找到任何金的情况下沿着10英尺长的地方挖1英尺深，它深入1英尺深。

然而，最佳优先搜索具有内置金属探测器，因此意味着它具有先验知识。当然，有一个金属探测器的成本，并打开它的成本，并看到哪个地方是最好开始挖掘。

最好的第一次搜索是通知的，而广度优先搜索是不知情的，因为其中一个有金属探测器而另一个没有！ 广度优先搜索已完成，这意味着如果存在解决方案，它将找到解决方案，并且给予足够的资源将找到最佳解决方案。

如果启发式（成本的估算/因此先验知识）是可接受的（这意味着它高估了获得解决方案的成本），那么最佳优先搜索也是完整的。

我从http://slideplayer.com/slide/9063462/得到了BFS图像，最好的第一次搜索是我在photoshop失败的尝试！

Answer 2

这是2种算法来搜索图形（树）。

广度首先查看某个深度的所有元素（节点），尝试找到一个解决方案（搜索值或其他）然后继续更深层次并查看每个节点，依此类推。

最好先查看主要由启发式定义的“最佳”节点，检查该节点的最佳子节点，依此类推。

A *将是启发式（最佳第一次搜索）的示例，并且其方式更快。但是你需要一个启发式的东西来进行广度搜索。

创建启发式需要一些自己的努力。宽度优先是开箱即用的。