logo标签列表

"统一代价搜索"和"Dijkstra算法"有什么区别？"

graphartificial-intelligence
88

我想知道“一致代价搜索”和“迪杰斯特拉算法”的区别。它们似乎是相同的算法。

5个回答
71
2
维基百科上的这两个页面现在已经合并了。 - ostrokach
41

Dijkstra算法在图中搜索从根节点到每个其他节点的最短路径，而一致代价搜索则在成本方面搜索到目标节点的最短路径。

此外，一致代价搜索需要更少的空间要求，而优先级队列被“懒惰”地填充，相反Dijkstra算法在开始时将所有节点添加到队列中并赋予无限成本。

1
为什么在Dijkstra算法中会将节点添加为无限成本？ - HappyFace
在实际应用中，人们只会添加源节点并在发现更多节点时再添加它们。也可以在开始时添加所有节点，并在发现它们时仅更新它们的距离。然而，我不认为这是Dijkstra算法的特征之一。这只是一个实现细节，对复杂度或结果没有影响，算法的本质仍然是相同的。请注意，只有前一种方法才能处理无限图，并且空间消耗可能会更低，这就是为什么它更实用的原因。 - Tomas Wilson
26

由NotAUser、dreaMone和Bruno Calza的答案汇编而成

Dijkstra算法可以找到从根节点到其他每个节点的最短路径。Uniform Cost Search能够按照从根节点到目标节点的代价寻找最短路径。Uniform Cost Search是Dijkstra算法的变种，它专注于找到单个终点的最短路径，而不是找到每个点的最短路径。

UCS在找到终点后就停止搜索，而对于Dijkstra，则没有终点的概念，处理将继续直到所有节点都从优先级队列中被移除，即直到确定了所有节点（而不仅仅是一个目标节点）的最短路径。

UCS需要的空间更少，在遍历时逐渐填充优先级队列，而Dijkstra在开始时将所有节点添加到队列中并赋予无限代价。

由于上述原因，Dijkstra比UCS更耗时。

UCS通常用于树上，而Dijkstra则用于一般图上。

Djikstra仅适用于显式图，其中整个图作为输入提供。UCS从源顶点开始，并逐步遍历图的必要部分，因此既适用于显式图，也适用于隐式图（其中状态/节点是生成的）。

1
为什么Dijkstra算法不能使用隐式图？ - HappyFace
Dijkstra算法的定义要求在算法开始时将所有节点的成本设置为无穷大。因此，您需要先了解所有节点。在隐式图中，节点在每个步骤中生成，因此在开始算法之前无法知道所有节点。 - Mohammed Elbagoury
5
1
主要区别在于，当顶点数量有限时，Dijkstra算法被定义为将所有顶点放入队列中。但是，当顶点数量趋近于无限时，我们无法将所有顶点放入队列中。而统一代价搜索算法则是在这种情况下被定义的，其中顶点数目是未知的。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接