fc2ブログ



最長増加部分列 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 012345678
T041628573
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 012345678
T041628573
L 0 1

index 012345678
T041628573
L 0 1 1

index 012345678
T041628573
L 0 1 1 2

index 012345678
T041628573
L 0 1 1 2 2

index 012345678
T041628573
L 0 1 1 2 2 3

index 012345678
T041628573
L 0 1 1 2 2 3 3

index 012345678
T041628573
L 0 1 1 2 2 3 3 4

index 012345678
T041628573
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 012345678
T041628573
L 0 1 1 2 2 3 3 4 3
P -1 0 0 1 2 2 4 6 4
p = 7 (LIS の最後のインデックス)
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) | ↑ページトップ |




フィボナッチ数 Fibonacci Number

2008.02.26 16:06  動的計画法

Time-Space complexity など、動的計画法と再帰による手法の違いを表すよい例がイタリアの数学者フィボナッチによって定義されたフィボナッチ数(Fibonacci number)の生成です。n 番目のフィボナッチ数 Fn

Fn = Fn-1 + Fn-2

と定義されます。

これはフィボナッチがウサギの増殖をモデル化するために定義した数です。フィボナッチは、もし1年目に1つがいのウサギがいれば、n年目に生まれるウサギのつがいの数は、その1年前と2年前のウサギのつがいの和に等しいと推量しました。従ってフィボナッチ数列の最初の数項は F0 = 0, F1 = 1 とすれば
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
.
.
となります。この数列は、自然界の現象やアプリケーションにも数多く出現します。

フィボナッチ数列は再帰的な式で定義できるので、それを以下のように簡単な再帰的なプログラムとして記述することができます。



001 int fibonacci( int i ){
002 if ( i == 0 ) return 0;
003 if ( i == 1 ) return 1;
004 return fibonacci(i - 2) + fibonacci(i - 1);
005 }



しかし、単純な再帰によるプログラムの計算量は指数関数時間になってしまいます。例えば、フィボナッチ数列の第5項を再帰で求めると以下のようになります。

再帰によるフィボナッチ数の生成


このように、最終的にはF(n)の結果がF(0)とF(1)の呼び出し回数の和になってしまいます。


以下のように、動的計画法を用いればF(n)をO(n)の多項式時間の計算量で求めることができます。


001 int F[MAX];
002
003 void makeFibonacci(){
004 F[0] = 0;
005 F[1] = 1;
006 for ( int i = 2; i < MAX; i++ ){
007 F[i] = F[i-2] + F[i-1];
008 }
009 }




動的計画法では全ての数列の値をメモリに記憶します。このプログラムはフィボナッチ数を小さい方から生成し記録していくので、F(i)を計算するときにはF(i-1)とF(i-2)がすでに計算されているのでそれを有効利用することができます。このように、小さい問題の解をメモリに記憶することにより、指数関数時間を多項式時間に改善し、計算時間を飛躍的に減少させることができます。

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




反復深化 Iterative Deepening

2008.02.22 19:02  探索 II

単純な深さ優先探索では初期状態から最終状態までの最短経路を求めることは不可能でした。しかし、深さを制限した深さ優先探索(深さ制限探索)を繰り返すことによって最短経路を求めることができます。つまり深さの制限 d を増加させながら深さ制限探索を繰り返します。このアルゴリズムを反復深化といいます。

searchIDP.gif


反復深化及び深さ制限探索では高速化を図るために探索空間(探索木)の枝を刈ることが重要になります。探索アルゴリズムでは、現在の状態 n から最終状態までの最短経路コスト h を見積もることができれば枝を刈ることができます。つまり、現在の状態の深さ g に「ここからあと最低でも h 回の状態変化は必要だろう」というコストh を加えた値が深さの制限 d を超えた場合、そこで探索を打ち切ることができます。h は見積もりであって正確な値である必要はありません。h の値が大きいほど探索の速度は上がりますが、大きく見積もりすぎると解を見逃してしまいます。h は以後必ず必要となる明確なコストを表し下限値と呼ばれます。

searchLimitCut.gif


では8パズルにおける下限値を考えてみましょう。

候補1 h1 = 最終状態の位置にないパネルの数
例えば、以下の状態で最終状態の位置にないパネルの数は 7 となります。

heuristic1.gif


候補2 h2 = 各パネルにおける最終状態までのマンハッタン距離の総和
マンハッタン距離とは「斜めに進むことができない上下左右だけの移動の総距離による2点間の距離」をいいます。例えば、以下の状態での各パネルの最終状態までのマンハッタン距離は、
パネル1 = 2
パネル2 = 1
パネル3 = 1
パネル4 = 3
パネル5 = 2
パネル6 = 3
パネル7 = 1
パネル8 = 0
となり、その総和は 13 となります。

heuristic2.gif


h1 も h2 も下限値として用いることができますが h2 の方が h1 よりも値が大きいので、優位であると言えます。

もちろんこれらの下限値は、深さ優先探索や深さ制限探索にも適用できます。



001 #include<iostream>
002 #include<cmath>
003 using namespace std;
004 #define LIMIT 30
005
006 struct Puzzle{ char cont[9]; int space; };
007
008 Puzzle puzzle;
009 int limit, path[LIMIT], MD[9][9];
010 static const int dx[4] = {-1, 0, 1, 0};
011 static const int dy[4] = {0, -1, 0, 1};
012 static const char direction[4] = {'d', 'r', 'u', 'l'};
013
014 int getHeuristic(){
015 int sum = 0;
016 for ( int i = 0; i < 9; i++ ){
017 if ( puzzle.cont[i] == 'x' ) continue;
018 sum += MD[i][puzzle.cont[i]-'1'];
019 }
020 return sum;
021 }
022
023 bool isTarget(){
024 for ( int i = 0; i < 8; i++ ){
025 if ( puzzle.cont[i] != '1' + i ) return false;
026 }
027 return true;
028 }
029
030 bool dfs(int depth, int prev){
031 if ( isTarget() ) return true;
032 if ( depth + getHeuristic() > limit ) return false;
033
034 int px, py, tx, ty;
035 Puzzle tmp;
036 px = puzzle.space / 3;
037 py = puzzle.space % 3;
038
039 for ( int r = 0; r < 4; r++ ){
040 tx = px + dx[r];
041 ty = py + dy[r];
042 if ( max(prev, r)-min(prev, r) == 2 ) continue;
043 if ( tx < 0 || ty < 0 || tx >= 3 || ty >= 3 ) continue;
044 tmp = puzzle;
045 puzzle.cont[px*3+py] = puzzle.cont[tx*3+ty];
046 puzzle.cont[tx*3+ty] = 'x';
047 puzzle.space = tx*3+ty;
048 if ( dfs( depth+1, r ) ) { path[depth] = r; return true;}
049 puzzle = tmp;
050 }
051 return false;
052 }
053
054 void solve(){
055 for ( limit = getHeuristic(); limit <= LIMIT; limit += 2 ){
056 if ( dfs(0, -100) ){
057 for ( int i = 0; i < limit; i++ ) cout << direction[path[i]];
058 cout << endl;
059 return;
060 }
061 }
062 cout << "unsolvable" << endl;
063 }
064
065 void input(){
066 for ( int i = 0; i < 9; i++ ){
067 cin >> puzzle.cont[i]; cout << puzzle.cont[i] << " ";
068 if ( puzzle.cont[i] == 'x' ) puzzle.space = i;
069 }
070 cout << endl;
071 }
072
073 main(){
074 for ( int i = 0; i < 9; i++ ){
075 for ( int j = 0; j < 9; j++ ){
076 MD[i][j] = abs(i/3-j/3) + abs(i%3-j%3);
077 }
078 }
079 input();
080 solve();
081 }




プログラムには明らかに無駄があります。高速化を図るのであれば、毎回下限値を計算するのではなく、状態変化した際にマンハッタン距離の差分を計算するとよいでしょう。

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




幅優先探索 Breadth First Search

2008.02.22 16:00  探索 II

searchBFS.gif


幅優先探索はグラフにおける幅優先探索と同様に動作し(グラフのノードを状態とみなします)、幅広く状態変化を行います。つまり、現在の状態から可能な全ての状態変化を行い新しい状態を作ります。この探索をシステマティックに行うために、状態変化によってつくられた新しい状態をキューに追加し、探索を展開するためにキューの先頭の状態からさらに状態変化を繰り返します。一度生成した状態を再び作らないために、生成された状態を全て記録する必要があります。幅優先探索は、問題に解が存在すれば初期状態から最終状態までの最短の経路を求めます。

それでは、8パズルを幅優先探索で解いてみましょう。

プログラムの説明

以下のプログラムは、例えば

2 8 3
x 1 5
4 7 6

というような、'x' をスペースとみなしたパズルを読み込み、

ldruuldlu

という、l = left, r = right, u = up, d = down の方向へパネルを移動するような、パズルを解くための経路を出力します。


基本的なデータ構造や状態変化の方法などは、深さ優先探索のプログラムと同様です。幅優先探索では生成された状態を記録するためのバッファが必要です。これをmapを使って実現するためには、パズルをクラスとして定義し、異なるパズルを比較するための演算子を定義します。パズルを対応した数字に変換するハッシュ関数を用いれば演算子は必要なくさらに効率化できるでしょう。また、幅優先探索では探索を展開するために生成された状態が新しいものであればそれをキューに追加します。



001 #include<iostream>
002 #include<cmath>
003 #include<string>
004 #include<map>
005 #include<queue>
006 using namespace std;
007 #define LIMIT 30
008
009 struct Puzzle{
010 char cont[9];
011 int space;
012 string path;
013 bool operator < ( const Puzzle &p ) const{
014 for ( int i = 0; i < 9; i++ ){
015 if ( cont[i] == p.cont[i] ) continue;
016 return cont[i] > p.cont[i];
017 }
018 return false;
019 }
020 };
021
022 int limit;
023 static const int dx[4] = {-1, 0, 1, 0};
024 static const int dy[4] = {0, -1, 0, 1};
025 static const char direction[4] = {'d', 'r', 'u', 'l'};
026
027 bool isTarget(Puzzle puzzle){
028 for ( int i = 0; i < 8; i++ ){
029 if ( puzzle.cont[i] != '1' + i ) return false;
030 }
031 return true;
032 }
033
034 void bfs(Puzzle s){
035 queue<Puzzle> Q;
036 map<Puzzle, bool> V;
037 Puzzle u, v;
038 s.path = "";
039 Q.push(s);
040 V[s] = true;
041
042 while( !Q.empty() ){
043 u = Q.front(); Q.pop();
044 if ( isTarget(u) ){
045 cout << u.path << endl;
046 return;
047 } else if ( u.path.size() > LIMIT ) break;
048
049 int sx, sy, tx, ty;
050 sx = u.space/3;
051 sy = u.space%3;
052
053 for ( int r = 0; r < 4; r++ ){
054 tx = sx + dx[r];
055 ty = sy + dy[r];
056 if ( tx < 0 || ty < 0 || tx >= 3 || ty >= 3 ) continue;
057 v = u;
058 v.cont[u.space] = u.cont[tx*3+ty];
059 v.cont[tx*3+ty] = 'x';
060 v.space = tx*3+ty;
061 if ( !V[v] ){
062 V[v] = true;
063 v.path += direction[r];
064 Q.push(v);
065 }
066 }
067 }
068 cout << "unsolvable" << endl;
069 }
070
071 main(){
072 Puzzle in;
073 for ( int i = 0; i < 9; i++ ){
074 cin >> in.cont[i];
075 if ( in.cont[i] == 'x' ) {
076 in.space = i;
077 }
078 }
079
080 bfs(in);
081 }


テーマ : プログラミング - ジャンル : コンピュータ

| コメント(1) | トラックバック(0) | ↑ページトップ |




深さ優先探索 Depth First Search

2008.02.21 14:29  探索 II


searchDFS.gif


深さ優先探索はグラフにおける深さ優先探索と同様に動作し(グラフのノードを状態とみなします)、初期状態から最終状態に至るまで可能な限り状態変化を繰り返します。ただし、

  • 現在の状態からそれ以上状態変化が不可能な場合

  • 状態変化が一度生成した状態を生成してしまう場合

  • 問題の性質からこれ以上探索しても明らかに無駄があると断定できる場合


などは探索(状態変化)を打ち切って前の状態に戻ります。これをバックトラックといいます。また探索を打ち切るので、「枝を刈る」とも表現されます。

深さ優先探索の深さに制限を持たせた方法を深さ制限探索といいます。つまり、探索の深さがある定められた値 d に達したところで探索を打ち切ります。問題の性質から深さを制限することができれば探索を高速化することができます。

それでは、8パズルを単純な深さ優先探索(深さ制限探索)で解いてみましょう。

以下のプログラムは、例えば

2 8 3
x 1 5
4 7 6

というような、'x' をスペースとみなしたパズルを読み込み、

dlurdlurdlurdlurdluruldlu

という、l = left, r = right, u = up, d = down の方向へパネルを移動するような、パズルを解くための経路を出力します。

このプログラムでは、8パズルを9つの要素を含むchar型の配列で表現しています。生成した状態を保存していないので、一度生成した状態へ状態変化する場合がありますが、深さを30と制限し、状態変化のとき1つ前の状態へ戻らないようにする(プログラム033行目)ことで、探索の空間を狭めています。



001 #include<iostream>
002 #include<cmath>
003 using namespace std;
004 #define LIMIT 30
005
006 struct Puzzle{ char cont[9]; int space; };
007
008 Puzzle puzzle;
009 int cost, path[LIMIT];
010 static const int dx[4] = {-1, 0, 1, 0};
011 static const int dy[4] = {0, -1, 0, 1};
012 static const char direction[4] = {'d', 'r', 'u', 'l'};
013
014 bool isTarget(){
015 for ( int i = 0; i < 8; i++ ){
016 if ( puzzle.cont[i] != '1' + i ) return false;
017 }
018 return true;
019 }
020
021 bool dfs(int depth, int prev){
022 if ( isTarget() ) { cost = depth; return true;}
023 if ( depth > LIMIT ) return false;
024
025 int px, py, tx, ty;
026 Puzzle tmp;
027 px = puzzle.space / 3;
028 py = puzzle.space % 3;
029
030 for ( int r = 0; r < 4; r++ ){
031 tx = px + dx[r];
032 ty = py + dy[r];
033 if ( max(prev, r) - min(prev, r) == 2 ) continue;
034 if ( tx < 0 || ty < 0 || tx >= 3 || ty >= 3 ) continue;
035 tmp = puzzle;
036 puzzle.cont[px*3+py] = puzzle.cont[tx*3+ty];
037 puzzle.cont[tx*3+ty] = 'x';
038 puzzle.space = tx*3+ty;
039 if ( dfs( depth+1, r ) ) { path[depth] = r; return true;}
040 puzzle = tmp; // backtracking

041 }
042 return false;
043 }
044
045 main(){
046 for ( int i = 0; i < 9; i++ ){
047 cin >> puzzle.cont[i];
048 if ( puzzle.cont[i] == 'x' ) puzzle.space = i;
049 }
050 if ( dfs(0, -100) ){
051 for ( int i = 0; i < cost; i++ ) cout << direction[path[i]];
052 cout << endl;
053 } else {
054 cout << "unsolvable" << endl;
055 }
056 }




単純な深さ優先探索の特徴

  • 最短の解を求めるとは限らない

  • 無駄な探索をしてしまうため計算量が大きい

  • 枝を刈らなければ最悪の場合(解がない場合など)は全探索してしまう

  • 深さを制限しなければ、解を見逃し堂々巡りに陥ってしまう

  • など


テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




探索アルゴリズム

2008.02.19 16:17  探索 II


8puzzle.gif



与えられた問題が解析的に解くことが困難な(不可能な)場合には、試行錯誤を繰り返すことによって解を探さなくてはなりません。しかし多くの場合、探索しなければならない空間は膨大であり、どのような経路が解へと導くかは不明です。従って、無駄な探索を避けたり、より速く解を見つけるための工夫が必要です。それらを体系的に行う方法が探索アルゴリズムであり、問題や状況に応じて様々なアルゴリズムが考えられます。

探索のアルゴリズムは、与えられた初期状態から最終状態への状態変化の列を求めます(このような列の長さをコストと言うことにします)。従って探索アルゴリズムでは「状態」そして「状態変化」という概念が重要になります。

例えば、8パズルを探索アルゴリズムで解くことを考えましょう。8パズルとは上図のような1つの空白を含む3×3のパネルを上下左右にスライドさせることによって、パズルを完成させます。

ここで、全てのパネルと空白の位置情報が「状態」であり、パネルを上下左右に動かすことが「状態変化」に相当します。

stateTransition.gif


多くの探索アルゴリズムでは、一度生成した状態を再度生成しないようにするために、探索の空間は木構造になります。木(またはグラフ)のノードが状態を表し、エッジが状態変化を表します。

探索アルゴリズム

  • 深さ優先探索 Depth First Search(DFS)

  • 幅優先探索 Breadth First Search(BFS)

  • 反復深化 Iterative Deepening

  • A*アルゴリズム A* Algorithm

  • 双方向幅優先探索 Bidirectional BFS



探索で解く問題の例

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |