统一成本搜索和Dijkstra算法之间有什么区别？

Question

我想知道统一成本搜索和Dijkstra算法之间有什么区别.它们似乎是相同的算法.

Answer 1

Dijkstra的算法,可能更为人所知,可以被视为统一成本搜索的变体,其中没有目标状态,并且处理继续,直到所有节点都已从优先级队列中移除,即直到到达所有节点的最短路径(不仅仅是一个目标节点)已经确定

Answer 2

Dijkstra的算法搜索从图中的根到每个其他节点的最短路径,而统一成本搜索目标节点的成本方面的最短路径.

同样,统一成本具有较少的空间需求,而优先级队列则"懒洋洋地"填充,与Dijkstra相反,后者在开始时以无限的成本将所有节点添加到队列中.

Answer 3

NotAUser,dreaMone和Bruno Calza撰写的其他答案

Dijkstra的算法找到从根节点到每个其他节点的最短路径.统一成本搜索从根节点到目标节点的成本方面的最短路径.统一成本搜索是Dijkstra的算法,该算法专注于找到到单个终点的单个最短路径,而不是到达每个点的最短路径.

UCS通过在找到终点后立即停止来完成此操作.对于Dijkstra,没有目标状态并且处理继续直到所有节点都已从优先级队列中移除,即直到已经确定到所有节点(不仅仅是目标节点)的最短路径.

UCS具有较少的空间要求,其中优先级队列逐渐填充而不是Dijkstra,后者在开始时以无限的成本将所有节点添加到队列中.

由于以上几点,Dijkstra比UCS更耗时

UCS通常在树上制定,而Dijkstra用于一般图形

Djikstra仅适用于显式图形,其中整个图形作为输入给出.UCS从源顶点开始,逐渐遍历图形的必要部分.因此,它适用于显式图和隐式图(生成状态/节点).

Answer 4

有一篇论文讨论了两者的异同。