Dijkstra的算法VS均匀成本搜索（时间自适应）

我的问题如下：根据不同的消息来源，Dijkstra的算法只不过是一个统一成本搜索的变种。我们知道Dijkstra的算法找到了源和所有目的地（单一来源）之间的最短路径。然而，我们总是可以修改Dijkstra以找到START和GOAL状态之间的最短路径（当目标从优先级队列中弹出时，我们简单地停止）;但是这样做，最糟糕的情况是仍然会找到从START到所有其他节点的最短路径（假设目标是图中最远的节点）。Dijkstra的算法VS均匀成本搜索（时间自适应）

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

由于统一成本搜索与Dijkstra相同（略有不同的实现），那么UCS的运行时间应该与Dijkstra类似，对吧？然而，根据我的AI类，统一成本搜索在最坏的情况下呈指数形式，它需要O（b ^{1 + [C * /ε]}），其中C *是最优解的成本。（b是分支因子）

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

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

来源

2012-10-19 John

是运行时间相同，但我们看它的方式是不同的？

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

来源

2012-10-19 15:04:09

让我们坚持有限的图（可能需要很大，但仍然完成）。那么我怎么能证明两种算法具有相同的运行时间？ – John

@John：通过重写任一算法的伪代码直到找到其他代码。这可能非常棘手，因为Dijkstra通常用于存储完全存储在内的有限图，但UCS用于可能无限的表示为边生成函数。 –

我同意你所说的，但在我的情况下，这里我想证明的是：给定城市地图（图），我想证明两种算法具有相同的时间复杂度以找到最优解 – John

Dijkstra的算法VS均匀成本搜索（时间自适应）

回答

相关问题