はじめに  H27 情報数学特論動的計画法 (DP: Dynamic Programming)   第2回：動的計画法最適性の原理 : 最適解へ至る途中計算も最適である DPはこの性質を満たす問題に対して有効ある問題の計算木 ―出来るだけ長い部分列を求める― 初期状態坂本比呂志九州工業大学大学院情報工学研究院最適解の計算経路途中計算もそこまでの解の中で最適 DPの応用 (部分列に関する二つの問題) 最適性の原理が成立する例   グラフ上の最短経路問題部分列とは  2点間 (例えばa~c) の最短経路がわかっており、それが b を経由するとき、a~b までの部分経路は a~b 間の最短経路でもある L(a,b)   b  L(b,c) c L’(a,b) e d 九州工業大学情報工学部坂本比呂志 3 配列から値が増加している部分を取り出すスケジューリングなどに応用最長共通部分列 (LCS)  もしそれ以外の最短経路L’(a,b)が存在するなら、L’(a,b)+L(b,c) < L(a,b)+L(b,c) = L(a,c) となり、L(a,c)が最短であることに反する    (オブジェクトの)列からいくつかの要素を取り出した列最長増加部分列 (LIS)  a 2 LIS   1,4,2,5,6,8,7,8,1,2,9 LCS  1,3,2,5,7,8 of 2,3,1,3,4,2,5,8,7,8 and 1,4,3,1,2,5,5,7,8 二つの配列の共通部分を取り出す DNA配列の類似性を決定編集距離の問題とほぼ等しい 4 1 最長増加部分列  最長増加部分列 [マトリョーシカの問題]     高さと幅を持つ人形がいくつか与えられている(マトリョーシカ) 高さと幅がともに大きい人形の内部に小さい方を格納できる入れ子にできる最大個数を求めよ配列 S= s1, s2, …, snの部分列 (Subsequence)   S のいくつかの要素を取り出して、元の順番を保って並べたもの例：S = 8,2,9,4,7,3,5,6 のとき   通常のマトリョーシカ（右図）では人形は相似形なので、単に体積でソートすれば、すべてのものを入れ子にできる。しかし、上の問題はパラメータが二つあるため単純ではない。   部分列として 8,4,3 や 9,3,5,6 などがある配列 S に対して S も自分自身の部分列である部分列の可能な場合は 2|S| 通りある増加部分列 (Increasing subsequence)   右に行くほど値が増加している部分列 (2,4,7 など) 減少部分列も同様 http://www.sankei.co.jp 5 最長増加部分列  最長増加部分列(LIS)の解法 ‘マトリョーシカの問題’は高さと幅のどちらかでソートし、残りの値の配列から最長増加部分列 (LIS: Longest Increasing Sequence) を求めることと同じ高さでソート高さ 1, 3, 4, 7, 8, 11, 12, 13 6, 7, 10, 9, 1, 2, 4, 5 幅    この一組の数が1個のマトリョーシカを決めるパラメータ  簡略化のため、すべての値は異なると仮定  失敗する戦略   この配列では、1,2,4,5が最長増加部分列しらみつぶしは困難 (可能な場合は指数的) この問題を効率よく計算する方法は？  左から順番に値を取り出す i+1番目の値を i番目までに得られた最長増加部分列に加えて新しい増加列が得られるかどうかをチェック最終的に得られた部分列を出力 6, 7, 10, 9, 1, 2, 4, 5 7 九州工業大学情報工学部坂本比呂志 6 失敗 8 正解 2 演習問題2-1 LISの解法  戦略の修正：     戦略１：同じ長さの部分列はどちらかを残す例：6,7,10,9,1,2,4で4文字目まで読んだとき、(6,7,10)と (6,7,9)のうち必要なのは末尾の値が小さい方のみ   戦略２：i 文字目まで読んだとき、1～i の各長さの部分列をひとつ覚えておく    [問題] 与えられた配列から、LISを計算するアルゴリズムを完成させよ  例：3,4,9,5,6,7,8 で、i = 3 までで記憶する増加部分列は、 (3), (3,4), (3,4,9), 最長の(3,4,9)だけでは、以下に続く 5,6,7,8 を増加部分列として加えることができないため失敗する実際は、(3,4) に 5,6,7,8 を加えたものが全体の最長  仮定：配列中のすべての値は異なるとしてよい目標：なるべく効率的なアルゴリズムを設計補足：アルゴリズムは手順がわかれば概略でよいそのアルゴリズムが、例えば以下の入力に対して正しく動作することを確かめよ (LIS長は 5 ) 10, 3, 2, 5, 8, 12, 6, 13, 9, 4 9 補足：LISの数学的性質 [発展的課題]  10 [問題] 最長増加部分列問題は、入力長 n に対して O(n log n) 時間、O(n) 領域で計算可能であるが、どうすればよいか？ (二分探索を使う) [定理] (Paul Erdös) 任意の配列 S (|S|=n)に対して、少なくとも以上の長さを持つ増加部分列または減少部分列のいずれかが存在する [証明] 与えられた配列をS= s1, s2, …, snとするの長さの増加部分列がないと仮定すると、以上の減少部分列が存在することを示す http://www.sankei.co.jp 11 九州工業大学情報工学部坂本比呂志 12 3 [証明つづき] [証明つづき] 定義： k∈Ki ⇔ skで終わるLISの長さがi その他の値は以下のようにKiに配分される括弧内は実際の値    以下の例を考える。i=3 とする 5番目を末尾に持つLISの長さは 3 であるので 5∈K3 7番目についても同様で、 K3={5,7} (それ以外は異なる) i 1 2 3 4 5 6 7 si 10 3 2 5 8 12 6 8 9 13 9 i 1 2 3 4 5 6 si 10 3 2 5 8 12 6 7 8 9 13 9 10 4 6を末尾に持つ最長増加部分列の長さは3 よって7→K3 10 4 この値を末尾に持つ最長増加部分列 (3,5,8など)の長さは3 よって5→ K3 13 K1 = {1(10), 2(3), 3(2) } K2 = { 4(5), 10(4)} K3 = {5(8),7(6), } K4 = {6(12), 9(9)} K5 = {8(9),} K6 = {∅} … このとき一般に次が成り立つ  任意の1~nはあるKi (1≤ i ≤n) に含まれる (その値で終わるLISが少なくともひとつは存在する)  i ≠ j ならば Ki ⋂ Kj = ∅ 14 (ある値で終わるLISが二つ以上存在するのはi=jに限る) [証明つづき] [証明つづき] ここで仮定より、K = ∅であるので、 1~nはすべてK1 ~K －1のいずれかに含まれるこのとき、ある j に対して |Kj|≥ であるあるjに対して|Kj|≥ であるこの要素をi1<i2<…<imとすると、これらが示す配列の値はこの順に小さくなっているはず(そうでなければ、jより長い増加部分列がとれてしまいKjの定義に反する) 11 12 13 5 7 2 3 6 15 8 1 14 4 鳩ノ巣原理よって、長さ 9 10 以上の増加または減少部分列が存在する 16 K1 ~K どれかが－1 の箱に１～ｎを詰めるとを超える 15 九州工業大学情報工学部坂本比呂志 16 4 最長共通部分列 (LCS)  LCSの応用例最長共通部分列 (LCS: Longest Common Subsequence) の発見     塩基配列のアライメント  共通部分列：ある配列が、二つの配列に共に現れる部分列であること LCSは最長の共通部分列を見つける問題この問題もDPを用いてO(n2)時間で計算可能(ただし、 nは二つの配列の長い方の配列長)  二つの塩基配列に適当にギャップ(空白)を挿入して、対応する塩基をなるべく一致させる操作赤い文字の部分は二つの配列のLCS 入力 GAGGTTATCAAAAGCTACTAGTCCA GAGGATAACAAGGCTACTATCACA 出力 GAGGTTATCAA AA GCTACTAGTC CA GAGG AT AACAAGGCTACTA TCACA 17 18 http://www.dna.bio.keio.ac.jp/ LCSの解法  LCSの解法接頭辞のLCS      配列 S の i 番目の文字を S[i] と表す配列 S の先頭から連続する k 文字の並びを、 S の長さ k の接頭辞という二つの配列 S,S’ のそれぞれのある接頭辞(長さi,j)について、それらのLCSの長さを LCS(i,j) とする例：S=abcde, S’=adbbcd に対して、 LCS(3,4)=LCS(abc,adbb)=2, LCS(3,5)=LCS(abc,adbbc)=3 19 九州工業大学情報工学部坂本比呂志 LCSの性質：LCS(i,j)は末尾の文字 S[i] と S’[j] によって場合分けできる (i,jのどちらかが0のときはLCS(i,j)=0)   S[i] = S ’[j]のとき：LCS(i,j) = LCS(i-1,j-1)+1 s[i-1] s[i] s’[j-1] s’[j] ... ... 末尾を一致させ、残りの色つきの部分のLCSと結合したものが最長 S[i] ≠S ’[j]のとき：LCS(i,j) = max{ LCS(i-1,j), LCS(i,j-1) } s[i-1] s[i] s’[j-1] s’[j] ... ... 末尾が一致しないので、色つきの部分が一致するのが限度（LCS(i-1,j)の場合） 20 5 演習問題2-2 LCSの解法  LCSの計算：S=bcbd, S’=adbdcd のとき、以下の行列の各成分のうち、最大値が求めるLCS a d b (i,j)成分の計算 d c d b i c [問題] 以下の配列のLCSを計算し、さらに長さだけではなく実際のLCSの配列を求める方法を述べよヒント：まず i=0 や j=0 と固定して求める j 初期状態  a d b d c b d b (i,j) c b b d d d a c d a b b a (i,j) c c a b LCS(i,j)の値を格納するセル：この場合はLCS(bc,adb)=1 九州工業大学情報工学部坂本比呂志末尾が等しいときの計算それ以外のときの計算 d 21 22 6