Dijkstra 算法与统一成本搜索(时间复杂度)

Question

我的问题如下:根据不同的消息来源，Dijkstra 算法只不过是 Uniform Cost Search 的一种变体。我们知道 Dijkstra 的算法会找到源和所有目的地(单源)之间的最短路径。但是，我们总是可以修改 Dijkstra 以找到 START 和 GOAL 状态之间的最短路径(当目标从优先级队列中弹出时，我们只需停止)；但是这样做，最坏的情况仍然是找到从 START 到所有其他节点的最短路径(假设目标是图中最远的节点)。

如果我们使用最小优先级堆实现 Dijkstra 算法，则运行时间将为
O(V log V +E) ，其中 E 是边数，V 是顶点数。

既然 Uniform Cost Search 和 Dijkstra 一样(实现略有不同)，那么 UCS 的运行时间应该和 Dijkstra 差不多吧？然而，根据我的 AI 类(class)，Uniform Cost Search 在最坏的情况下是指数级的，它需要 O(b1 + [C*/ε])，其中 C* 是最优解的成本。 ( b 是分支因子)

两种算法如何在运行时间不同的情况下相同？运行时间是否相同，但我们看待它的方式不同？

我会很感激你的帮助 :):) 谢谢

Answer 1

Is the running time the same, but the way we look at it is different?

是的。统一成本搜索可用于无限大的图，Dijkstra 的原始算法永远不会终止。在这种情况下，根据 V 和 E 定义复杂性是没有用的，因为两者都可能是无限的，并且由此产生的大 O 数字毫无意义。