最長増加部分列 Longest Increasing Subsequence
2008.02.26 17:14 動的計画法

東西に並んだ高さの異なるn本の木があります。あるキコリがこれらの木を、西から東の方向へ木の高さが小さい順に並ぶように、いくつかの木を切り倒すことにしました。木の数を最大にするにはどの木を切れ(残せ)ばようでしょうか?
このような単純な(くだらない)問題でも、考えられる組み合わせを全て調べようとすると、それは各木を選ぶか選ばないかの組み合わせになるので、計算量はO(2n)となってしまいます。
この問題は、与えられた数列の最長増加部分列 Longest Increasing Subsequence (LIS) を求めることに帰着します。
最長増加部分列とは、与えられた数列 S
S = a1, a2 , , , an
の増加部分列 ( すべてのi, j (i < j)について ai < aj を満たす部分列 )
の中で長さが最大のものをいいます。
例えば、
S = 4 1 6 2 8 5 7 3
の増加部分列には
4 8
1 6 8
4 6 7
1 6 7
.
.
などがありますが、長さが最大のものは
1 2 5 7
です。
動的計画法によって与えられた数列の最長増加部分列をみつけることができます。
ここでは、n を数列の長さとすれば O(n2) の効率のアルゴリズムを紹介します。
与えられた数列を T とし、インデックスが 1 から始まるとします。また
L を、L[i] が「T[1]からT[i]までの要素でT[i]を最後に選んだときの LIS の長さ」を示す配列とします。
L[0] を 0 に初期化します。また T[0] は 0 (通常は非常に小さい値)に初期化します。
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
T | 0 | 4 | 1 | 6 | 2 | 8 | 5 | 7 | 3 |
L | 0 |
以下 L[i] ( i が 1 から n まで)を計算します。
L[i] の計算:
j が 0 から i - 1 について、T[j] < T[i] を満たしかつ L[j] が最大である j を k とすると
L[i] = L[k] + 1 とします。
以下、計算の流れです。
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
T | 0 | 4 | 1 | 6 | 2 | 8 | 5 | 7 | 3 |
L | 0 | 1 |
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
T | 0 | 4 | 1 | 6 | 2 | 8 | 5 | 7 | 3 |
L | 0 | 1 | 1 |
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
T | 0 | 4 | 1 | 6 | 2 | 8 | 5 | 7 | 3 |
L | 0 | 1 | 1 | 2 |
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
T | 0 | 4 | 1 | 6 | 2 | 8 | 5 | 7 | 3 |
L | 0 | 1 | 1 | 2 | 2 |
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
T | 0 | 4 | 1 | 6 | 2 | 8 | 5 | 7 | 3 |
L | 0 | 1 | 1 | 2 | 2 | 3 |
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
T | 0 | 4 | 1 | 6 | 2 | 8 | 5 | 7 | 3 |
L | 0 | 1 | 1 | 2 | 2 | 3 | 3 |
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
T | 0 | 4 | 1 | 6 | 2 | 8 | 5 | 7 | 3 |
L | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 |
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
T | 0 | 4 | 1 | 6 | 2 | 8 | 5 | 7 | 3 |
L | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 3 |
L の要素で最大のものが、与えられた数列の LIS となります。
また、実際のLISを求めるためには、
P を P[i] が「T[1]からT[i]までの要素でT[i]を最後に選んだときのLISの1つ前の要素のインデックス」を示す配列とし、
各 L[i] を計算するときに、
P[i] = k
とすれば P の要素を辿ることで実際の LIS を求めることができます。
例えば、上記の例で P は以下のようになるので、
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
T | 0 | 4 | 1 | 6 | 2 | 8 | 5 | 7 | 3 |
L | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 3 |
P | -1 | 0 | 0 | 1 | 2 | 2 | 4 | 6 | 4 |
p = P[p] = P[7] = 6
p = P[p] = P[6] = 4
p = P[p] = P[4] = 2
よって、インデックスの列が 2 4 6 7 なので対応する LIS は
1 2 5 7
となります。
001 #include<iostream> 002 #define MAX 2000 003 using namespace std; 004 005 int size, length; 006 int T[MAX+1], L[MAX+1], P[MAX+1]; 007 008 void printLIS(int i){ 009 if ( P[i] == -1 ) return; 010 printLIS(P[i]); 011 cout << T[i] << endl; 012 } 013 014 int LIS(){ 015 T[0] = 0; 016 L[0] = 0; 017 P[0] = -1; 018 for ( int i = 1; i <= size; i++ ){ 019 int k = 0; // max index 020 for ( int j = 0; j <= i - 1; j++ ){ 021 if ( T[j] < T[i] && L[j] > L[k] ){ 022 k = j; 023 } 024 } 025 L[i] = L[k] + 1; 026 P[i] = k; 027 } 028 029 // print result 030 int maxv = 0; 031 int maxi; 032 for ( int i = 1; i <= size; i++ ){ 033 if ( maxv <= L[i] ){ 034 maxv = L[i]; 035 maxi = i; 036 } 037 } 038 039 cout << maxv << endl; 040 cout << "-" << endl; 041 printLIS(maxi); 042 } 043 044 main(){ 045 cin >> size; 046 for ( int i = 1; i <= size; i++ ) cin >> T[i]; 047 LIS(); 048 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |