しばらくは暇が多くなるので,いろいろと書いていきます.UVaでのランキングは順調に上がっていますが,当面 5位を目標にしています.そのハードルを乗り越えれば,2位になることや,もしかしてナンバーワンになるのかもしれません.努力だけは誰にも負けないので,楽しみに見ていきましょう.

さて,アルゴリズムを探しているひとが多いと思いますが,もっとも高速な O(N logN) の LIS プログラムを公開します.

LIS (Longest Increasing Subsequence) とは最長単調増分シーケンスのこと.数字列 (あるいは文字列等.互いに大きさの比較ができるものなら何でもOK) の中から,値が大きく(あるいは小さく)なっていく,もっとも長いシーケンス(数字列)を見つけ出すアルゴリズムのことです.

 -7, 10, 9, 2, 3, 8, 8, 1

例えば,上の数字列では,LIS は -7 2 3 8 になります.数字列の長さ(つまりデータの個数)を N とすると,DP(ダイナミック・プログラミング)による O(N2) のアルゴリズムと,より高速な O(N logN) のアルゴリズム、少なくとも 2種類あることが知れています.

LIS のアルゴリズムについて,ネット上探せば当然色々と見つかります.以下のページもその一例.

http://www.windowsitpro.com/Files/23/24814/Figure_02.gif

ページが削除される可能性もあるので,コピーしておきます.

<Adapted algorithm for finding longest increasing subsequences>
 Let S = ( a1, a2, …, an ) be a sequence of n numbers. The length of the longest increasing subsequence of S is the number of elements in the list of numbers that the following procedure generates.

 Let K = 1, and let L be an empty list of numbers.

 While K <= n
  Inspect L for numbers greater than or equal to ak. If any exist, replace the smallest of them with ak. Otherwise ( when ak is greater than every number in L ), insert ak into the list L.
  Increase K by 1.

書いていることを、上のシーケンスでシミュレーションしてみましょう.

  S = ( -7, 10, 9, 2, 3, 8, 8, 1). N = 8.
 初期状態では, K = 1. リスト(集合) L を空 (Null) とする.
 以下を K <= 8 まで繰り返す.
   K = 1: a1 = -7. リスト L に何もないので,a1 を L に追加します.
   K = 2: a2 = 10. リスト L にある要素 -7 と比較します. a2 のほうが大きいので, L に追加します.これで,リスト L = ( -7, 10 ) になります.
   K = 3: a3 = 9. 同様にリストLにあるすべての要素と比較しますが,10よりも小さいので,10 を a3 に書き換えます.リスト L = ( -7, 9 ) に変わりますが,長さは K=2 のときと同じです.
   K = 4: a4 = 2. 上の9のケースと同様です.9を書き換えて,L = ( -7, 2 ) になります.
   K = 5: a5 = 3: リスト L の中のすべての要素よりも大きいので、L に追加します.追加した結果として, L = ( -7, 2, 3 ) になります.
   K = 6: a6 = 8: こちらも追加になります. L = ( -7, 2, 3, 8 ).
   K = 7: a7 = 8: リスト L に同じ要素が存在しているので,なにもしません.あるいは,同じ書き換え動作をしても構いません.結果は同じなので.
   K = 8: a8 = 1: リストにある要素のうち、a8よりも大きな最小値が 2 ですので,2 を書き換えます.これで、リスト L = ( -7, 1, 3, 8 ) に変わります.

  ここで終了.最終的に得られたリストは L = ( -7, 1, 3, 8 ). L の長さは 4 でした.

さて,丁寧に見てきたように,上のアルゴリズムは正確には LIS を探すものではなく,LIS の長さを探すものでした.つまり,LIS を見つけ出すことには間違っていますが、LIS の長さは正しく算出している と断言していいでしょう.本来ならば,このことを証明しないといけないけれど.

で,計算量を見てみます.リストLへの追加(その時点でのリストの最大値)は最後の位置にのみ行われていること,途中の書き換えも前後の順番を変えるものではないことから,リストは常に昇順でソートされた状態を保っていることが分かります.

ソートされた状態のリスト(配列)から値を探す方法として,2分検索(バイナリサーチ) というアルゴリズムがあります.それに従えば,検索時間は 最悪でも O(log N) で済みます.

個々の ai について O(log N) のバイナリサーチで検索し,ai よりも大きい値の最小値を O(1) で書き換えるか, リストの末尾に O(1) で追加する、という手続きなので,全体的にアルゴリズムの計算時間は O(N log N) になります.

一方、使用するメモリ領域は,入力データのリスト S 以外に, LIS を格納するリスト L も必要なのですが,Lの長さは最悪の場合でも N なので, メモリ領域(空間計算量)は O(N) になります.

両方合わせて、LIS の長さを O(N log N) で算出できるわけです.

以下はC言語によるプログラムです.

LISの長さを求める関数 LIS()

入力データを 配列 S に、データの長さを size にセットして、LIS() 関数を呼び出せば、LISの長さがリターン値として得られます.(配列の長さやデータ型は必要に応じて変えて下さい.)

<LISの長さを求める関数>
 int LIS(void)
   関数値: LISの長さ ( >= 0)
   入力データ: 配列 S.(添え字 0 からデータを入れてください.)
   入力データの長さ: size

汎用性を考えれば,関数のスペックを
  int LIS(int size, int *S)
にし,関数の内部に,LISを格納するためのリスト(配列)L用のメモリ領域をcalloc関数を使って動的に確保するほうがいいかもしれませんが,UVa のプログラムというものは汎用性を考えるよりも,信頼性や,スピードのほうが大事なので,手抜きします.

なお,上記の自作関数のなかでは,少しでも高速になるよう,バイナリサーチをかける前に,まずリストL内の最大値(つまり最後の要素)と比較し,入力データ aiが大きければ,そのまま追加手続きを取ることにしています.

LISの長さはこれで求まるわけですが,肝心のLISそのものを探し出すプログラムについては次回書きます.リストLの書き換えをする前に,その前任の記録を取るだけで済みます.理屈は簡単ですが,プログラムにすると少々判りにくくなるかもしれません.

Comments are closed.

Post Navigation