ダイクストラのアルゴリズムが動的プログラミングの下にあるかどうかを明確にしてください。Floyd warshall アルゴリズムが動的プログラミング アプローチの下にあると呼ぶのはなぜですか。それらの違いを追跡することはできません。私がこれをやろうとしたとき、私は実際に動的プログラミングが正確に何を意味するのかという疑問に遭遇しました? また、貪欲なアプローチとしてダイクストラが引用されているのは、それが常に正しいとは限らないことを意味しますか? さらに、この 2 つのアルゴリズムの結果は異なりますか? 誰か詳しく説明してください。
質問する
5276 次
3 に答える
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];
}
ダイクストラはグラフ検索アルゴリズムですが。
動的プログラミング、貪欲なアプローチの違いについては、この投稿を見ることができます
分割統治、動的プログラミング、貪欲なアルゴリズム！ 貪欲なアルゴリズム
于 2012-12-07T07:19:18.913 に答える