アルゴリズム学習のための動的プログラミング戦略の紹介

1. コンセプト

動的プログラミング戦略、分割統治戦略。貪欲戦略と同様に、通常は最適解問題を解決するために使用されます。分割統治とは、問題をいくつかのサブ問題に分解して解決することです。動的計画法の特徴は、分解されたサブ問題の中から毎回最適な解決策を選択することです（サブ問題はサブ問題に分解できます）。

動的プログラミングの主な特徴は、決定を下す前にすべてのサブ問題の情報を知っていることです。

動的プログラミングの 2 つの重要な要素は次のとおりです。1) ***サブ構造。 2) 重複するサブ問題。

1) ***サブ構造。これは、動的プログラミング戦略を使用して***問題を解決した後に実行される最初のステップです。いわゆる最適なサブ構造とは、問題に対する最適な解決策にサブ問題に対する最適な解決策が含まれている場合、その問題には最適なサブ構造があることを意味します。これは、動的計画法を採用するための十分な条件です（もちろん、この条件は貪欲戦略も満たします）。この条件が発生した場合、動的計画法を検討できます。

通常考慮される要素は次のとおりです。

1.1) ソリューションではいくつのサブ問題を解決する必要がありますか?

1.2) どのサブ問題を使用するかを決定するには、どの程度の選択が必要ですか?

2) 重複するサブ問題とは、再帰的なソリューションにおいて、多数の同一のサブ問題が生成される場合、同じサブ問題が何度も繰り返し計算され、アルゴリズムの効率が大幅に低下することを意味します。この要素は動的プログラミングの利点です。動的プログラミングはこのような問題を解決するために生まれたと言えます（実際、メモリを備えた再帰アルゴリズムでも同様のアルゴリズムの改善を実現できます）。

2. 問題解決戦略

問題を解決するための一般的な考え方は次のとおりです。

1) 問題の解決には、1つ以上のサブ問題を残す選択が必要であることを証明する

2) サブ問題の再帰的記述を設計する（一般的には、問題とアルゴリズムを解決するための鍵となる、転送方程式とも呼ばれる再帰式があります）

3) 元の問題に対する最善の解決策には、すべての部分問題に対する最善の解決策が含まれていることを証明する

4) サブ問題間に重複があることを証明する

1、3、4 は、サブ問題の構築を動的計画法戦略に準拠させることが目的であることがわかります。それらの目的は、合理的で適切なサブ問題を構築できるようにすることです。ただし、異なる問題に対してサブ問題を構築するという考え方は同じではありません。 1.1 と 1.2 の問題を考慮することに加えて、通常は、このサブ問題をできるだけ単純にし、必要に応じて拡張するという、より効果的な方法があります。

3. 例

より古典的な最長共通部分列問題 (LCS) を使用します。

問題は次のように定義されます: 2 つの部分列 S1[1..m] と S2[1..n] について、それらの最長共通部分列を見つける必要があります (部分列は必ずしも連続している必要はありません)。

解決策1: ブルートフォース法

アイデア:

1) S1[1..m]内のすべてのサブシーケンスをチェックします。

2)それがS2[1..n]内の部分列でもあるかどうかを確認します。

3) 各ステップで、サブシーケンス内で見つかった最長のサブシーケンスを記録します。

明らかに、これは非常に非効率的です。各サブシーケンスは O(n) 時間でチェックする必要があり、チェックするサブシーケンスは 2^m 個あるため、時間の計算量は O(n*2^m) になります。

では、どのように改善すればよいのでしょうか? LCS には *** サブ構造があるため、つまり、必要な最長共通サブシーケンスには最長共通サブシーケンスが含まれているため、動的プログラミングを使用して問題を解決できます。

解決策2: 動的プログラミング

問題解決戦略によれば、まず適切なサブ問題を構築する必要があります。2 番目のポイントに従って、できるだけ単純なサブ問題を構築し、それを拡張します。LCS では、次のようになります。

1) まず、最長共通部分列の長さを求めます。

2) 長さを見つけるアルゴリズムを拡張して、最長共通部分列を取得します。

上記から、再帰式を得ることができます。

（c[i,j]は長さiのS1と長さjのS2の最長共通部分列を表す。xiは文字列Sのi番目の文字を表す。）

上記の再帰的演繹は、図を描くことで簡単に得ることができます。

コード：

  charb[50][50]; //LCS出力を容易にするためにパス図を記録する 
  intc[50][50]; //c[i][j]は長さiのx文字列と長さjのy文字列のLCSの長さを格納します 
  charx[50], y[50]; //x,yは比較する2つの文字列を格納する 
  voidLCS()
  {
  intm = strlen(x+1);
  intn = strlen(y+1);
　　//初期化 
　　(int i = 1; i <= m; ++i)の場合
  c[i][0] = 0;
　　(intj=1;j<=n;++j)の場合
  c[0][j] = 0;
　　(int i = 1; i <= m; ++i)の場合
　　(intj=1;j<=n;++j)の場合
  {
　　(x[i] == y[j])の場合
  {
  c[i][j] = c[i-1][j-1] + 1;
  b[i][j] = '\' ;
  }
  そうでない場合(c[i-1][j] >= c[i][j-1])
  {
  c[i][j] = c[i-1][j];
  b[i][j] = '|' ;
  }
　　それ以外 
  {
  c[i][j] = c[i][j-1];
 b[i][j] = '-' ;
  }
  }
  }
　　// 出力LCS  
  void printLCS(inti, intj)
  {
　　(i == 0|| j == 0)の場合
　　戻る;
　　b[i][j] == '\'の場合
  {
  printLCS(i-1, j-1);
  x[i] + ""を印刷します。
  }
  そうでない場合は(b[i][j] == '|' )
 printLCS(i-1, j);
　　それ以外 
  printLCS(i, j-1);
  }

IV. 要約

LCS には、最長増加/減少サブシーケンス、編集距離など、さまざまなバリエーションがあります。

動的プログラミングの鍵となるのは、上で述べた 2 つの重要な要素、すなわち *** サブ構造と繰り返されるサブ問題です。*** 問題に関連情報がある場合、またはそのような問題に変換できる場合は、動的プログラミングを使用してみることができます。ただし、サブ問題の構築には、再帰方程式の構築という、ある程度の思考が必要です。

ただし、動的プログラミングは最も「賢明な」決定を下すことができますが、それを行う前にすべてを知る必要があり、明らかに「保守的」であるため、すべての問題に適用できるわけではありません。現時点では、他の最適化アルゴリズムを検討することができます。

オリジナルリンク: http://www.cnblogs.com/Quains/archive/2011/11/09/2241879.html

【編集者のおすすめ】