0

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

4

3 回答 3

3

动态编程是您归纳地使用子问题来解决问题的地方。

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

于 2012-12-07T06:57:29.910 回答
0

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

Dijaktra 的算法 - 引用维基百科 -

是一种图搜索算法，用于解决具有非负边路径成本的图 > 的单源最短路径问题，生成最短路径树

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

于 2012-12-07T06:53:12.833 回答
0

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

 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 是图搜索算法。

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

分而治之，动态规划和贪心算法！ 贪心算法

于 2012-12-07T07:19:18.913 回答