差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン最新のリビジョン両方とも次のリビジョン | ||
programming_algorithm:dynamic_programming:longest_common_subsequence [2017/10/08] – ↷ programming:algorithm:dynamic_programming:longest_common_subsequence から programming_algorithm:dynamic_programming:longest_common_subsequence へページを移動しました。 ikatakos | programming_algorithm:dynamic_programming:longest_common_subsequence [2019/01/09] – ikatakos | ||
---|---|---|---|
行 12: | 行 12: | ||
- | =====最長増加部分列===== | + | =====最長増加部分列の長さ===== |
数列の部分列のうち、隣接する2要素を見ると常に右の方が大きいものを増加部分列という。同じ値を許すかは定義によるが、ここでは許さないとする。 | 数列の部分列のうち、隣接する2要素を見ると常に右の方が大きいものを増加部分列という。同じ値を許すかは定義によるが、ここでは許さないとする。 | ||
行 30: | 行 30: | ||
- $A$ の要素を1つずつ順番に処理する。現在処理中の要素を $a_j$ とする。 | - $A$ の要素を1つずつ順番に処理する。現在処理中の要素を $a_j$ とする。 | ||
- $L[i]$ を、「$a_1$~$a_j$ の要素から長さが $i+1$ の増加部分列を作ったとき、末尾要素が取り得る最小値」とし、更新していく。 | - $L[i]$ を、「$a_1$~$a_j$ の要素から長さが $i+1$ の増加部分列を作ったとき、末尾要素が取り得る最小値」とし、更新していく。 | ||
- | - 最後まで処理した後の $L$ の長さが、最長増加部分列長となる。 | + | - 最後まで処理した後の $L$ の値が埋まっている所の長さが、最長増加部分列長となる。 |
<sxh python> | <sxh python> | ||
行 52: | 行 52: | ||
</ | </ | ||
- | =====最長共通部分列===== | + | =====最長共通部分列の長さ===== |
* [[http:// | * [[http:// | ||
行 69: | 行 69: | ||
- Bの要素を1つずつ順番に処理する。現在処理中の要素を$b_k$とする。 | - Bの要素を1つずつ順番に処理する。現在処理中の要素を$b_k$とする。 | ||
- $L[i]$を、「" | - $L[i]$を、「" | ||
- | - Bを最後まで処理した後の $L$ の長さが、最長増加部分列長となる。 | + | - Bを最後まで処理した後の $L$ の値が埋まっている所の長さが、最長共通部分列長となる。 |
<sxh python> | <sxh python> | ||
行 117: | 行 117: | ||
* Aにおいて、'' | * Aにおいて、'' | ||
* 延長できる場合、$L$ に追加する | * 延長できる場合、$L$ に追加する | ||
+ | |||
+ | =====具体的な最長共通部分列===== | ||
+ | |||
+ | * [[wp> | ||
+ | |||
+ | $|S| \times |T|$ の配列上でDPを行い、途中の計算結果を保存しておくことで、最長共通部分列と共に、その具体例を構築することが出来る。 | ||
+ | |||
+ | $S_{1 ... i}$ と $T_{1 ... j}$ のLCSの長さを $L_{i,j}$ とする。 | ||
+ | |||
+ | ==$S_{i+1}=T_{j+1}$ の時== | ||
+ | |||
+ | LCS長は1文字拡張できる。$L_{i+1, | ||
+ | |||
+ | ==それ以外の時== | ||
+ | |||
+ | LCS長は、片方の末尾を1文字削った2通りの長い方となる。 $L_{i+1, | ||
+ | |||
+ | これで、$i=1 .. |S|$、$j=1 .. |T|$ の2重ループでDPテーブルを小さい方から埋めていくことで、$DP[|S|][|T|]$ が最終的なLCS長となる。 | ||
+ | |||
+ | で、具体的な文字列は、$DP[|S|][|T|]$ から逆向きに復元する。 | ||
+ | |||
+ | ==$DP[i][j]=DP[i][j-1]$ または $DP[i][j]=DP[i-1][j]$ の時== | ||
+ | |||
+ | 同じである数字の方に移動する。両方同じ場合は、具体例が1つ構築できればいい場合は適当に1つ選んで移動する。 | ||
+ | |||
+ | ==それ以外の時== | ||
+ | |||
+ | $S_i=T_j$ であるはずなので、それをLCSに加え、$(i-1, | ||
+ | |||
+ | < | ||
+ | 0 1 2 3 4 5 6 7 | ||
+ | M Z J A W X U | ||
+ | 0 | 0 0 0 0 0 0 0 0 | ||
+ | 1 X |⓪ 0 0 0 0 0 1 1 | ||
+ | 2 M | 0❶① 1 1 1 1 1 | ||
+ | 3 J | 0 1 1❷ 2 2 2 2 | ||
+ | 4 Y | 0 1 1② 2 2 2 2 | ||
+ | 5 A | 0 1 1 2❸③③ 3 | ||
+ | 6 U | 0 1 1 2 3 3 3❹ 丸付きの数字を辿っていき、 | ||
+ | 7 Z | 0 1 2 2 3 3 3④ 黒丸の数字を拾っていくと、LCS(の1つ)は MJAU と復元できる | ||
+ | </ | ||