我的问题如下:根据不同的来源,Dijkstra算法只是一种统一代价搜索的变体。我们知道,Dijkstra算法可以找到源节点到所有目标节点(单源)的最短路径。然而,我们总是可以修改Dijkstra算法以查找起始状态和目标状态之间的最短路径(当目标状态从优先级队列中弹出时,我们只需停止);但这样做,最坏情况仍将找到从起点到所有其他节点的最短路径(假设目标是图中最远的节点)。
如果我们使用最小优先级堆实现Dijkstra算法,运行时间将为O(V log V +E),其中E是边数,V是顶点数。
由于统一代价搜索与Dijkstra相同(稍有不同的实现),因此UCS的运行时间应该类似于Dijkstra,对吗?但是,根据我的AI课程,统一代价搜索在最坏情况下是指数级的,并且需要O(b1 + [C*/ε])的时间,其中C*是最优解的成本。(b是分支因子)
这两个算法如何相同,而它们具有不同的运行时间?运行时间相同,但我们看待它的方式不同吗?
我将非常感谢您的帮助:)谢谢
如果我们使用最小优先级堆实现Dijkstra算法,运行时间将为O(V log V +E),其中E是边数,V是顶点数。
由于统一代价搜索与Dijkstra相同(稍有不同的实现),因此UCS的运行时间应该类似于Dijkstra,对吗?但是,根据我的AI课程,统一代价搜索在最坏情况下是指数级的,并且需要O(b1 + [C*/ε])的时间,其中C*是最优解的成本。(b是分支因子)
这两个算法如何相同,而它们具有不同的运行时间?运行时间相同,但我们看待它的方式不同吗?
我将非常感谢您的帮助:)谢谢