23 
Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
   (a) max_ending_here = max_ending_here + a[i]
   (b) if(max_ending_here < 0)
         max_ending_here = 0
   (c) if(max_so_far < max_ending_here)
          max_so_far = max_ending_here
 return max_so_far

上記のアルゴリズムで、最適なサブ構造とオーバーラップの問題(DPのパンとバター)を理解するのを手伝ってくれる人はいますか?

4

2 に答える 2

24

重なり部分問題のこの定義によれば、Kadane のアルゴリズム ( ) の再帰的な定式化は、この特性を示しません。単純な再帰的な実装では、各副問題は 1 回だけ計算されます。f[i] = max(f[i - 1] + a[i], a[i])

ただし、ここでの定義に従って最適な部分構造を示します。与えられた問題 ( uses )の解を見つけるために、より小さな部分問題の解を使用します。f[i]f[i - 1]

ここで動的計画法の定義を検討してください。

数学、コンピューター サイエンス、経済学では、動的計画法は、複雑な問題をより単純な部分問題に分解することで解決する方法です。これは、部分問題1と最適な部分構造 (後述)の重複の特性を示す問題に適用できます。該当する場合、部分問題の重複を利用しない単純な方法 (深さ優先探索など) よりもはるかに短い時間で済みます。

動的計画法の背後にある考え方は非常に単純です。一般に、特定の問題を解決するには、問題のさまざまな部分 (サブ問題) を解決し、サブ問題のソリューションを組み合わせて全体的なソリューションに到達する必要があります。多くの場合、より単純な方法を使用すると、副問題の多くが生成され、何度も解決されます。動的計画法のアプローチでは、各部分問題を 1 回だけ解こうとするため、計算回数が削減されます。

これは、Kadane のアルゴリズムが DP アルゴリズムと見なすことができるかどうかについて、解釈の余地を残しています。問題をより簡単な部分問題に分割することで問題を解決しますが、コアの再帰的アプローチは重複する部分問題を生成しません。これが DP の目的です。効率的に処理するため、これは DP の専門外になります。

一方、基本的な再帰的アプローチが部分問題の重複につながる必要はないと言うこともできますが、これは再帰的アルゴリズムを DP アルゴリズムにすることになり、私の意見では DP の範囲が広すぎます。ただし、これを確実に解決する文献は何も知らないので、学生を評価したり、本や記事を無視したりすることはありません。

したがって、実装によっては、DPアルゴリズムではなく、貪欲および/または再帰的なアルゴリズムであると言えます。上記の理由により、アルゴリズムの観点からは貪欲であるとラベル付けしますが、客観的には他の解釈も同様に有効であると考えます.

于 2013-05-01T18:43:03.983 に答える