动态规划与Dijkstra算法的区别

Question

任何人都可以澄清Dijkstra的算法是否属于动态规划。为什么我们称弗洛伊德·沃歇尔算法属于动态规划方法。我无法找出它们之间的区别。当我尝试这样做时，我实际上遇到了一个疑问，动态编程到底意味着什么？Dijkstra的也被引用为贪婪的方法，这是否意味着它并不总是正确的？此外，这两种算法的结果是否不同？任何人都可以详细解释一下。

Answer 1

动态规划是你归纳使用子问题来解决问题的地方。

另一方面，贪婪算法试图通过局部最优步骤来解决全局优化问题。有时这些局部步骤会带你达到全局最优（如Dijkstra算法的情况），有时可能不会（如在变革问题中）。

Answer 2

动态规划（DP）和贪婪方法是一种方法论 - 一个概念 - 就像递归一样;它们不是任何特定的算法。

迪亚克特拉的算法 - 引用维基百科 -

是一种图搜索算法，可为边路成本为非负的图>求解单源最短路径问题，生成最短路径树

Dijaktra的算法可能会使用DP技术来解决最短路径问题。

Answer 3

动态规划是一种编程方法，通过这种方法，我们可以通过将复杂问题分解为更简单的 sub-problems.by 将先前计算的子问题值存储在内存中而不是重新计算来解决。

 public static int fib(int n) {
 if (n < 2) {
 return n;
 }
 int[] f = new int[n];
 f[0] = 0;
 f[1] = 1;
 for (int i=2; i<n; i++) { // store the Fibonacci numbers
 f[i] = f[i-1] + f[i-2];
 }
  return f[n-1] + f[n-2];
}

而Dijkstra是图形搜索算法。

而对于动态编程的区别，贪婪的方法你可以看到这篇文章

分而治之，动态编程和贪婪的算法！ 贪婪算法