14

从我到目前为止所读到的。就找到目标的最短路径而言，最佳优先搜索似乎更快，因为 Dijkstra 的算法必须在遍历图形时放松所有节点。是什么让 Dijkstra 的算法比 Best First Search 更好？

4

3 回答 3

35

编辑：您的编辑表明您对Best-First Search感兴趣，而不是BFS。

最佳优先搜索实际上是一种知情算法，它首先扩展最有希望的节点。非常类似于众所周知的 A* 算法（实际上 A* 是一种特定的最佳优先搜索算法）。

Dijkstra 是不知情的算法- 当您不了解图并且无法估计每个节点到目标的距离时，应该使用它。

请注意，当您对每个 .h(v) = 0v

此外，Best First Search 不是最优的[不能保证找到最短路径]，如果不使用可接受的启发式函数，A* 也不是最优的，而 Dijkstra 的算法始终是最优的，因为它不依赖任何启发式。

结论：当您对图有一些了解并且可以估计与目标的距离时，应该首选最佳优先搜索而不是 dijkstra。如果您不这样做 - 使用h(v) = 0并且仅在已经探索的顶点上中继的不知情的最佳优先搜索会衰减到 Dijkstra 的算法。
此外，如果最优性很重要 - Dijkstra 算法始终适合，而只有在适当的启发式函数可用时才能使用最佳优先搜索算法（特别是 A*）。

原始答案 - 回答为什么选择 Dijkstra 而不是 BFS：

当涉及到加权图时，BFS 会失败。

例子：

     A
   /   \
  1     5
 /       \
B----1----C

在这里：w(A,B) = w(B,C) = 1, w(A,C) = 5。

来自 A 的 BFS 将A->C作为最短路径返回，但对于加权图，它是一个权重为 5 的路径！！！而最短路径的权重为 2: A->B->C.
Dijkstra 的算法不会犯这个错误，并返回最短的加权路径。

如果您的图表未加权 - BFS 既最优又完整- 并且通常应该比 dijkstra 更受欢迎 - 两者都因为它更简单和更快（至少渐近地说）。

于 2012-04-29T17:39:34.863 回答
1

通常是路径查找中的最佳优先搜索算法，搜索两个给定节点之间的路径： Source和Sink，但 Dijkstra 的算法查找源和所有其他节点之间的路径。所以你不能比较它们。Dijkstra 本身也是一种最佳优先搜索（ A *的变体）意味着你不能说它不是最佳优先搜索。正常的最佳优先搜索算法也使用启发式算法，它们不能保证正确性，最后在加权情况下，它们的运行时间通常取决于权重，但 Dijkstra 的算法仅取决于图形大小。

于 2012-04-29T18:09:52.253 回答
0

BFS 适用于在所有边具有相同权重的情况下找到从源到顶点的最短路径，即找到从源到顶点的最小边数。虽然 Dikjstra 适用于加权图

于 2014-06-15T07:38:55.073 回答