algorithm - 具有单一来源、单一目标点的修改后的 Dijkstra 和统一成本搜索之间有什么区别?

标签 algorithm comparison updates dijkstra ucs

如果我们将Dijkstra算法从“单一源点到所有节点的最短路径”修改为寻找“单一源点到单个目的点的最短路径”,那么这个修改后的Dijkstra算法和uniform cost search有什么区别呢?任何帮助将不胜感激。谢谢。

最佳答案

可以在 Dijkstra’s Algorithm versus Uniform Cost Search or a Case Against Dijkstra’s Algorithm 中看到对两种算法之间差异的很好剖析。 .我只是引用了 Arial Felner 的一些结论:

The two algorithms have many similarities and are logically equivalent. The most important similarity is that they expand exactly the same nodes and in exactly the same order.

正如我们所怀疑的,从理论的角度来看,这两种算法是等价的。

However, there are many differences between these algorithms as described in text books and taught in classes. The main difference is the identity of the nodes in the priority queue. In modified Dijkstra, all nodes are initially inserted into the queue. In UCS, nodes are inserted to the queue lazily during the search.


因此

  1. 在内存需求方面它们是不同的,UCS 的OPEN 比修改后的Dijkstra 的Q 小很多。在任何给定的时间步长,修改后的 Dijkstra 的内存需求都大于 UCS。
  2. 就运行时间而言,同样的推理适用于操作OPENQ 的时间开销。修改后的 Dijkstra 在操作这些结构时有更大的开销,因为它存储了 dist[] = ∞ 的节点,这些节点永远不会被扩展。相比之下,在 UCS 中,OPEN 仅包含 dist ≠ ∞ 的节点,即,仅包含逻辑上需要且可能被选择用于扩展的节点

综上所述,UCS和修改后的Dijkstra在大O复杂度上是等价的,扩展相同的节点和相同的顺序,但从实用的角度来说UCS应该是首选而且它更在没有启发式信息的情况下处理单一来源 - 单一目的地问题时广泛使用。

关于algorithm - 具有单一来源、单一目标点的修改后的 Dijkstra 和统一成本搜索之间有什么区别?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51799313/

相关文章:

java - 复杂性与实际调用函数 n 次或放入迭代 n 次的循环有何不同?

Mysql比较逗号分隔的字段与单个字符串

sql - 当我一次又一次用相同的值更新表时会发生什么?

prolog - Prolog中@<和<之间的算术差异

mysql - 当 Select 中的同一个表具有附加联接时更新

ios - 在Apple App Store上的应用更新之间更改国家/地区可用性

c++ - 如何识别股市中的矩形价格拥塞? (C++)

algorithm - 支持快速下一个高元素和下一个低元素的数据结构是什么?

algorithm - 用功能语言了解此多项式除法算法

c# - 字符串比较 - strA.ToLower()==strB.ToLower() 或 strA.Equals(strB,StringComparisonType)?