迪杰斯特拉算法的本质是贪心还是动态规划?
发布网友
发布时间：2022-04-28 21:24
共3个回答
热心网友
时间：2022-04-12 01:05
贪心是一种特殊的动态规划，动态规划的本质是独立的子问题，而贪心则是每次可以找到最优的独立子问题。
贪心和动归不是互斥的，而是包含的，贪心更快，但约束更强，适应范围更小。
动归和bfs的关系也是一样的。
展开一点讲，在求解最优化问题时，有多个解。而求解的过程类似一个树，我们称之为求解树。
一般的求解树真的是一棵树，所以我们只能用bfs来搜索，顶多剪枝。
有些特殊的求解树，中间很多结点是重合的，结点个数比所有搜索分支的个数少很多个数量级。这类问题较特殊，我们可以保存中间的搜索过程。而记忆化搜索和动态规划本质上就是一个东西，快就快在可以不用重复计算很多中间结果（所谓的最优子问题）。
还有一些特殊的求解树，更特殊，它们不止有很多重复结点，而且每次选择分支的时候，我们可以证明只要选择一个分支，这个分支的解就一定比其他选择更优。这类问题就是贪心了，
所以bfs，dp，贪心三个方法都是解决最优化问题的方法，根据问题的不同，约束越大的问题可以用越快的方法，越慢的方法可以解决的问题越普适。
动态规划的状态转移函数，可以抽象成这样一种函数：
f(x)=g(f(x1), f(x2), f(x3), ... f(xn))
其中f就是我们说的独立问题，每个f都有一个唯一值，也就是没有后效性。
贪心也是这个函数，但可以证明：
f(xi) >= f(x1|x2|...|xn)
那么我们就不用再去计算除了f(xi)以外的任何子状态了，所以就更快
而标准的bfs，虽然也有
f(x)=g(f(x1), f(x2), f(x3), ... f(xn))
但是因为对于任意的f(x)，它的子问题f(xi)的输入状态xi都不同（换一种思路也可以说f(xi)在不同的路径下值都不同，本质上是我们怎么定义xi，到底是狭义的参数还是广义的状态），所以无法使用内存去换取时间，就只能去遍历所有状态了。
热心网友
时间：2022-04-12 02:23
一般意义上的贪心算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
Dijkstra算法显然是从整体最优考虑，求出的最短路径，一定是整体最优解，这是和一般意义上的贪心算法相悖的地方。而且Dijkstra算法符合动态规划的这一特性：待求解的问题分解为若干个子问题，前一子问题的解，为后一子问题的求解提供了有用的信息。在我看来，Dijkstra算法更接近动态规划。
从维基百科也可以看到这样的说明：
From a dynamic programming point of view, Dijkstra's algorithm is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the Reaching method.
热心网友
时间：2022-04-12 03:58
我认为 Dijkstra算法 的本质是 广度优先搜索，
而此处的广度是定义在路程的cost之上的。
（就好比从圆心处向外扩散一个圆环，首次碰到的就是最近）
动态规划泛指，重叠子问题与原问题的推算关系（学名：动态转移方程），
贪心是极端情况的动态规划，子问题独一选择性。
Dijkstra算法的分解思路是
到达某节点的cost最小路径 --（从这里面选）--> { 到达其相邻节点的cost最小路径 }
独一选择性:
只挑选： Min {到达其相邻节点的最短路径}
结论：的确是贪心策略
