algorithm
動的プログラミング
サーチ…
前書き
ダイナミクスプログラミングは広く使われているコンセプトであり、しばしば最適化に使用されます。これは、複雑な問題を単純なサブ問題に再帰的に分割することによって、複雑な問題を単純化することを指します。通常、ボトムアップアプローチです。動的プログラミングを「最適な基礎構造」および「重複するサブ問題」に適用するためには、問題が持つべき2つの重要な属性があります。最適化を達成するために、ダイナミクスプログラミングでは、記憶
備考
ダイナミックプログラミングはブルートフォースの改良です。ブルートフォースからどのようにダイナミックプログラミングソリューションを得ることができるかを理解するこの例を参照してください。
動的プログラミングソリューションには2つの主な要件があります。
重複問題
最適な下部構造
問題が重複しているということは、元の問題の解決策に到達するために、問題のより小さなバージョンの結果が複数回再利用されることを意味します
最適部分構造とは、そのサブ問題から問題を計算する方法があることを意味します。
動的プログラミングソリューションには、2つの主要コンポーネント、 状態と遷移があります
国家は、元の問題のサブ問題を指す。
遷移は、問題をそのサブ問題に基づいて解決する方法です
ダイナミックプログラミングソリューションによる時間は、[状態数] No. of States * Transition Timeとして計算できます。したがって、解がN^2状態を持ち、遷移がO(N)ならば、解はおおよそO(N^3)時間かかるだろう。
ナップザック問題
0-1ナップザック
ナップザック問題は、それぞれが重み、値、 正確に1つのコピーを持つ一連のアイテムが与えられ、コレクションに含めるアイテムを決定して、合計の重みが与えられたものよりも小さいか等しい最大値は可能な限り大きくなります。
C ++の例：
実装 ：
int knapsack(vector<int> &value, vector<int> &weight, int N, int C){
int dp[C+1];
for (int i = 1; i <= C; ++i){
dp[i] = -100000000;
}
dp[0] = 0;
for (int i = 0; i < N; ++i){
for (int j = C; j >= weight[i]; --j){
dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
}
}
return dp[C];
}
テスト ：
3 5
5 2
2 1
3 2
出力 ：
3
これは、最大値が達成されることを意味する3であり、これは（2,1）および（3,2）を選択することによって達成される。
無限のナップザック
無限ナップザック問題は、それぞれが重み、値、 無限コピーを持つアイテムのセットを与え、コレクションに含める各アイテムの数を決定し、合計重量が所定の制限値以下になる問題合計値は可能な限り大きくなります。
Python（2.7.11）例：
実装 ：
def unbounded_knapsack(w, v, c): # weight, value and capactiy
m = [0]
for r in range(1, c+1):
val = m[r-1]
for i, wi in enumerate(w):
if wi > r:
continue
val = max(val, v[i] + m[r-wi])
m.append(val)
return m[c] # return the maximum value can be achieved
この実装の複雑さはO(nC)です.nはアイテム数です。
テスト ：
w = [2, 3, 4, 5, 6]
v = [2, 4, 6, 8, 9]
print unbounded_knapsack(w, v, 13)
出力 ：
20
つまり、（5,8）、（5,8）、（3,4）を選択することで最大値が20に達することを意味します。
加重ジョブスケジューリングアルゴリズム
加重ジョブスケジューリングアルゴリズムは、加重アクティビティ選択アルゴリズムとも呼ばれます。
問題は、開始時間と終了時間を持つ特定のジョブと、仕事を終えたときに得た利益を考慮すると、2つのジョブを並行して実行することはできないので、最大利益はいくらですか？
これは、Greedy Algorithmを使ったActivity Selectionのように見えますが、追加されています。つまり、終了したジョブの数を最大にする代わりに、最大の利益を上げることに集中します。実行されたジョブの数はここで重要ではありません。
例を見てみましょう：
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | A | B | C | D | E | F |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (2,5) | (6,7) | (7,9) | (1,3) | (5,8) | (4,6) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 6 | 4 | 2 | 5 | 11 | 5 |
+-------------------------+---------+---------+---------+---------+---------+---------+
ジョブは、名前、開始時刻と終了時刻、および利益で示されます。数回反復した後、私たちがJob-AとJob-Eを実行するかどうかを調べると、最大利益は17になります。アルゴリズムを使用してこれをどのように見つけるか？
私たちが最初にやることは、仕上げ時間を非降順で並べ替えることです。なぜ我々はこれを行うのですか？終了する時間が短いジョブを選択すると、他のジョブを選択するのに最も時間がかかります。我々は持っています：
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
私たちは、サイズnの追加の一時配列Acc_Profを持つでしょう（ここで、 nはジョブの総数を表します）。これには、ジョブを実行する最大の累積利益が含まれます。それを取得しないでください？待って、見てください。配列の値を各ジョブの利益で初期化します。つまり、 Acc_Prof [i]はi番目の仕事を実行する利益を最初に保持します。
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
さて、 位置2をi 、 位置1をjとする 。私たちの戦略は、 jを1からi- 1まで繰り返し、各反復の後、 iがn + 1になるまで、 iを1だけ増分する。
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
ジョブ[i]と仕事[J]の重複、つまり、 仕事[J]の終了時刻が 仕事よりも大きい場合は、[I]の開始時間は、これら2つのジョブが一緒に行うことができない場合我々は確認してください。ただし、重複しない場合は、 Acc_Prof [j] + Profit [i]> Acc_Prof [i]かどうかを確認します。この場合、 Acc_Prof [i] = Acc_Prof [j] + Profit [i]を更新します。あれは：
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
ここで、 Acc_Prof [j] + Profit [i]は、これらの2つのジョブを累積した利益を表します。私たちの例を見てみましょう：
ここでJob [j]はJob [i]と重複しています 。だからこれらを一緒にすることはできません。私たちのjは I-1に等しいので、我々は3であるI + 1にiの値をインクリメントします。そして、 j = 1とする 。
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
今、 Job [j]とJob [i]は重複しません。これらの2つのジョブを選択することによって得られる利益の総量は、 Acc_Prof [j] +利益[i] = 5 + 5 = 10であり、 Acc_Prof [i]より大きい。そこで、 Acc_Prof [i] = 10を更新します。また、 jを1ずつ増やします。
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
ここで、 Job [j]はJob [i]と重なり、 jもi-1と等しい。したがって、 iを1だけ増やし、 j = 1にします。我々が得る、
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Job [j]とJob [i]は重なり合わないので、 Acc_Prof [i]より大きい累積利益5 + 4 = 9を得る。 Acc_Prof [i] = 9を更新し、 jを1増加させる。
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 9 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
ここでもJob [j]とJob [i]は重複しません。累積利益は、 6 + 4 = 10であり、 Acc_Prof [i]よりも大きい。 Acc_Prof [i] = 10を再び更新する。 jを1ずつ増やします。
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 10 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
このプロセスを続けると、 iを使ってテーブル全体を反復した後、テーブルは次のようになります。
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 14 | 17 | 8 |
+-------------------------+---------+---------+---------+---------+---------+---------+
*ドキュメントを短くするために、いくつかの手順が省略されています。
配列Acc_Profを繰り返し処理すると、最大利益が17になることがわかります。擬似コード：
Procedure WeightedJobScheduling(Job)
sort Job according to finish time in non-decreasing order
for i -> 2 to n
for j -> 1 to i-1
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
endfor
endfor
maxProfit = 0
for i -> 1 to n
if maxProfit < Acc_Prof[i]
maxProfit = Acc_Prof[i]
return maxProfit
Acc_Prof配列を生成する複雑さはO（n 2 ）です。配列トラバースはO（n）をとります。したがって、このアルゴリズムの全体の複雑さはO（n 2 ）である。
我々は最大の利益を得るために実行されたジョブを知りたい場合は今、私たちは逆の順序で配列を横断する必要があるとAcc_Profは maxProfitに一致した場合、我々は、 スタック内のジョブの名前を押しての利益を差し引きますその仕事はmaxProfitから。 maxProfit> 0になるか、 Acc_Prof配列の始点に達するまでこれを行います。擬似コードは次のようになります。
Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit):
S = stack()
for i -> n down to 0 and maxProfit > 0
if maxProfit is equal to Acc_Prof[i]
S.push(Job[i].name
maxProfit = maxProfit - Job[i].profit
endif
endfor
この手順の複雑さは、 O（n）です。
一つのことを覚えておきましょう。最大の利益をもたらすことができる複数のジョブスケジュールがある場合、この手順では1つのジョブスケジュールしか見つけることができません。
距離の編集
問題文は、2つの文字列str1とstr2が与えられた後、str2に変換されたstr1に対して実行可能な最小数の操作があるかのようなものです。
Javaでの実装
public class EditDistance {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "march";
String str2 = "cart";
EditDistance ed = new EditDistance();
System.out.println(ed.getMinConversions(str1, str2));
}
public int getMinConversions(String str1, String str2){
int dp[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
if(i==0)
dp[i][j] = j;
else if(j==0)
dp[i][j] = i;
else if(str1.charAt(i-1) == str2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
}
}
}
return dp[str1.length()][str2.length()];
}
}
出力
3
最長共通サブシーケンス
2つの文字列が与えられている場合、それらの両方に存在する最も長い共通のサブシーケンスを見つけなければなりません。
例
LCS for input Sequence "ABCDGH"と "AEDFHR"は長さ3の "ADH"です。
LCS for input Sequences "AGGTAB"と "GXTXAYB"は長さ4の "GTAB"です。
Javaでの実装
public class LCS {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "AGGTAB";
String str2 = "GXTXAYB";
LCS obj = new LCS();
System.out.println(obj.lcs(str1, str2, str1.length(), str2.length()));
System.out.println(obj.lcs2(str1, str2));
}
//Recursive function
public int lcs(String str1, String str2, int m, int n){
if(m==0 || n==0)
return 0;
if(str1.charAt(m-1) == str2.charAt(n-1))
return 1 + lcs(str1, str2, m-1, n-1);
else
return Math.max(lcs(str1, str2, m-1, n), lcs(str1, str2, m, n-1));
}
//Iterative function
public int lcs2(String str1, String str2){
int lcs[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
if(i==0 || j== 0){
lcs[i][j] = 0;
}
else if(str1.charAt(i-1) == str2.charAt(j-1)){
lcs[i][j] = 1 + lcs[i-1][j-1];
}else{
lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
}
}
}
return lcs[str1.length()][str2.length()];
}
}
出力
4
フィボナッチ数
動的プログラミングを使用してn番目のフィボナッチ数を印刷するボトムアップアプローチ。
再帰ツリー
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
重複するサブ問題
ここで、fib（0）、fib（1）、fib（3）は重複するサブ問題です.fib（0）は3回繰り返され、fib（1）は5回繰り返され、fib（3）は2回。
実装
public int fib(int n){
int f[] = new int[n+1];
f[0]=0;f[1]=1;
for(int i=2;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
時間の複雑さ
に）
最長共通部分文字列
2つの文字列str1とstr2が与えられたとき、それらの間の最も長い共通部分文字列の長さを見つけなければなりません。
例
入力：X = "abcdxyz"、y = "xyzabcd"出力：4
最長共通部分文字列は "abcd"で長さは4です。
入力：X = "zxabcdezy"、y = "yzabcdezx"出力：6
最も長い共通部分文字列は "abcdez"で長さは6です。
Javaでの実装
public int getLongestCommonSubstring(String str1,String str2){
int arr[][] = new int[str2.length()+1][str1.length()+1];
int max = Integer.MIN_VALUE;
for(int i=1;i<=str2.length();i++){
for(int j=1;j<=str1.length();j++){
if(str1.charAt(j-1) == str2.charAt(i-1)){
arr[i][j] = arr[i-1][j-1]+1;
if(arr[i][j]>max)
max = arr[i][j];
}
else
arr[i][j] = 0;
}
}
return max;
}
時間の複雑さ
O（m * n）
