LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@mori790

【解答】アルゴリズムイントロダクション：15.4 最長共通部分列

Posted at

問題15.4-1

⟨1, 0, 0, 1, 0, 1, 0, 1⟩ と ⟨0, 1, 0, 1, 1, 0, 1, 1, 0⟩ の最長共通部分列（LCS）を１つ求めよ．

解答

  • ⟨1, 0, 0, 1, 1, 0⟩
  • または ⟨1, 0, 1, 0, 1, 0⟩ (walkccc.me)

丁寧な説明

  1. 動的計画法の行列構築
    長さ m = 8 の X と長さ n = 9 の Y に対し，c[i,j] を X の長さ i プレフィックスと Y の長さ j プレフィックスの LCS 長とすると，以下の再帰式で表せます：

    c[i,j] = 0                                   (i=0 または j=0)
c[i,j] = c[i-1,j-1] + 1     if X[i] == Y[j]
c[i,j] = max(c[i-1,j], c[i,j-1])  otherwise

    これを行列 c[0..8,0..9] に対して行・列を順に埋めていけば，c[8,9] = 6 が得られます．

  2. 共通部分列の復元
    c[i,j] の値を見ながら，PRINT-LCS アルゴリズムで復元します．

    • X[i] == Y[j] の場合は両方を含めて対角に移動
    • そうでない場合は，c[i-1,j] と c[i,j-1] を比較し，大きいほうの方向へ移動

    これにより長さ6の部分列⟨1,0,0,1,1,0⟩（または別の等長解）を得られます．

  3. なぜこれが最長か

    • 例えば最初の要素 X[1]=1 を残すなら，Y の中で最初に現れる 1 の位置を j=2 とし，その後のサブ問題として X[2..8], Y[3..9] の LCS を求める．
    • 再帰的に同様の判断を行い，最適部分構造に基づいて最大長を得る．

問題15.4-2

完成済みの c テーブルと元の列 X = ⟨x₁,…,xₘ⟩，Y = ⟨y₁,…,yₙ⟩ を用い，b テーブルを使わずに O(m+n) 時間で LCS を復元する擬似コードを示せ．

解答

PRINT-LCS(c, X, Y, i, j)
    if c[i,j] == 0
        return
    if X[i] == Y[j]
        PRINT-LCS(c, X, Y, i-1, j-1)
        print X[i]
    else if c[i-1,j] > c[i,j-1]
        PRINT-LCS(c, X, Y, i-1, j)
    else
        PRINT-LCS(c, X, Y, i, j-1)

このアルゴリズムは再帰的に対角・上・左のいずれかに移動し，文字を出力する． (walkccc.me)

丁寧な説明

  1. b テーブル不要の理由
    通常，b[i,j] は c の計算時に選択した経路（↖, ↑, ←）を記録しているが，c[i,j] の値と隣接する c の値（c[i-1,j-1], c[i-1,j], c[i,j-1]）を比較するだけで，どの遷移で計算したかをその場で判断できる．

  2. 再帰フロー

    • c[i,j]=0 に到達するまで再帰
    • 対角（↖）の場合は LCS の末尾に X[i]（=Y[j]）を含める
    • 上（↑）か左（←）かを比較し，多い方へ進む

  3. 計算量

    • 一度訪問した (i,j) は必ず再帰で一度のみ出力ルーチンを通過
    • 再帰深さは高々 m+n，文字列出力を合わせて O(m+n) で完了する．

問題15.4-3

O(mn) 時間で動作する LCS-LENGTH のメモ化（トップダウン）バージョンを示せ．

解答

MEMO-LCS-AUX(X, Y, i, j)
    if c[i,j] > -1
        return c[i,j]
    if i == 0 or j == 0
        return c[i,j] = 0
    if X[i] == Y[j]
        return c[i,j] = MEMO-LCS-AUX(X,Y,i-1,j-1) + 1
    return c[i,j] = max(
        MEMO-LCS-AUX(X,Y,i-1,j),
        MEMO-LCS-AUX(X,Y,i,j-1)
    )

MEMO-LCS-LENGTH(X, Y)
    let c[0..m,0..n] be new array, 初期値を -1 に設定
    return MEMO-LCS-AUX(X, Y, m, n)

  (walkccc.me)

丁寧な説明

  1. メモ化による重複計算の排除
    再帰的 LCS-LENGTH は同じ (i,j) を繰り返し計算しうるが，c[i,j] に結果を一度だけ格納し，再利用することで各 (i,j) は最大1度しか計算されない．

  2. 時間計算量

    • 可能なサブ問題数は (m+1)(n+1)=Θ(mn)
    • 各再帰呼び出しは定数回のメモ化テーブル参照と定数時間比較
    • よって合計 Θ(mn) 時間

  3. 空間計算量

    • c テーブルに Θ(mn) 空間
    • 再帰深さは Θ(m+n) のオーバーヘッド

問題15.4-4

長さ m, n の列の LCS 長さを求める際，c テーブルを 2·min(m,n) エントリ＋O(1) 追加空間だけで計算する方法を示せ．さらに，min(m,n) エントリ＋O(1) 空間で同様を実現する方法も示せ．

解答

  • 2·min(m,n) エントリを使う方法
    各ステップで「現在行」と「１つ前の行」のみ保持し，それ以前の行は解放する．

  • min(m,n) エントリを使う方法
    c[i,j] の計算に必要なのは c[i-1,j], c[i,j-1], c[i-1,j-1] の３つのみ．
    内部ループで，列方向（あるいは行方向）の１次元配列だけを走査し，必要なくなった要素を都度上書きすることで，Θ(min(m,n)) の配列だけで実現できる． (walkccc.me)

  • 以下、具体例 X=⟨A,B,C⟩,Y=⟨A,C⟩ での配列遷移を、prev_row／curr_row の値でステップごとに示します。

// 初期状態
prev_row = [0, 0, 0]   // j = 0,1,2
curr_row = [0, 0, 0]

// i = 1 (X[1] = A) のループ開始
// ── j = 1
//    X[1]==Y[1] (A==A) なので
//    curr_row[1] = prev_row[0] + 1 = 1
//    → curr_row = [0, 1, 0]
// ── j = 2
//    X[1]!=Y[2] (A!=C) なので
//    curr_row[2] = max(prev_row[2], curr_row[1]) = max(0,1) = 1
//    → curr_row = [0, 1, 1]

// i=1 終了後に swap
prev_row = [0, 1, 1]
curr_row = [0, 1, 1]    ←（次 i の前に通常はリセットして使う）

// i = 2 (X[2] = B) のループ開始
// curr_row を [0,0,0] にリセット
curr_row = [0, 0, 0]
// ── j = 1
//    B!=A → curr_row[1] = max(prev_row[1], curr_row[0]) = max(1,0) = 1
//    → curr_row = [0, 1, 0]
// ── j = 2
//    B!=C → curr_row[2] = max(prev_row[2], curr_row[1]) = max(1,1) = 1
//    → curr_row = [0, 1, 1]

// i=2 終了後に swap
prev_row = [0, 1, 1]
curr_row = [0, 1, 1]

// i = 3 (X[3] = C) のループ開始
// curr_row を [0,0,0] にリセット
curr_row = [0, 0, 0]
// ── j = 1
//    C!=A → curr_row[1] = max(prev_row[1], curr_row[0]) = max(1,0) = 1
//    → curr_row = [0, 1, 0]
// ── j = 2
//    C==C → curr_row[2] = prev_row[1] + 1 = 2
//    → curr_row = [0, 1, 2]

// i=3 終了後に swap
prev_row = [0, 1, 2]
curr_row = [0, 1, 2]

// 最終的に LCS 長さ = curr_row[2] = 2

丁寧な説明

  1. 行単位スライディングウィンドウ

    • 通常，c テーブルは (m+1)×(n+1) だが，各 i 行を計算するときは i-2 行より前は二度と参照しない．
    • よって常に直前２行のみメモリ上に残し，i 行目を計算後に i-2 行を解放すれば，必要セル数は 2·(n+1)．

  2. １次元配列の in-place 更新

    • 列を j=1…n と走査しながら 1 次元配列 C[j] を更新
    • C[j] ← max(prev_C[j], C[j-1], prev_C[j-1]+1 など) の形で，必要な情報を一時変数 prev に持たせる
    • これにより min(m,n) の配列長さだけで計算可能

  3. 計算量

    • 各セルの更新は O(1)
    • 全セル数 mn に比例して計算：Θ(mn) 時間

問題15.4-5

長さ n の数列に対し，最長単調増加部分列（LIS）を O(n²) 時間で求めるアルゴリズムを示せ．

解答

最長単調増加部分列（LIS：Longest Increasing Subsequence）とは，次のように定義される問題です。

単調増加部分列とは？

定義

  • 与えられた長さ $n$ の数列

    $$
    A = \langle a_1, a_2, \dots, a_n\rangle
    $$

  • その「部分列」（subsequence）とは，元の数列からいくつかの要素を取り出して，元の順序を保ったまま得られる新しい列のこと。
    例えば，$\langle a_2, a_5, a_7\rangle$ や $\langle a_1, a_3, a_4, a_6\rangle$ など。

  • 「単調増加」は各要素が前より大きい（厳密増加）ことを意味する：
    部分列 $\langle b_1, b_2, \dots, b_k\rangle$ が単調増加なら

    $$
    b_1 < b_2 < \dots < b_k
    $$

    を満たします。

  • 最長単調増加部分列（LIS） は，すべての単調増加部分列の中で最も長いものを指し，その長さを求めたり，実際の部分列を復元したりする問題です。

例

たとえば，

$$
A = \langle 3,, 1,, 8,, 2,, 5,, 6,, 4,, 7\rangle
$$

このときの単調増加部分列の例としては

  • $\langle 3,, 8\rangle$（長さ2）
  • $\langle 1,, 2,, 5,, 6,, 7\rangle$（長さ5）
  • $\langle 1,, 5,, 6,, 7\rangle$（長さ4） などがあります

この中で最も長いものは長さ5の

$$
\langle 1,, 2,, 5,, 6,, 7\rangle
$$

ですから，この列の LIS の長さは 5，LIS のひとつの具体例は上記の部分列になります。

  1. 元の数列 L をコピーしてソートし，L′ を得る（昇順）
  2. L と L′ の LCS を求める（DP を使えば Θ(n²)）
  3. その共通部分列は単調増加かつ最長である (walkccc.me)
PRINT-LCS(c, X, Y)
    n = c[X.length, Y.length]
    let s[1..n] be a new array
    i = X.length
    j = Y.length
    while i > 0 and j > 0
        if x[i] == y[j]
            s[n] = x[i]
            n = n - 1
            i = i - 1
            j = j - 1
        else if c[i - 1, j] ≥ c[i, j - 1]
            i = i - 1
        else j = j - 1
    for i = 1 to s.length
        print s[i]

MEMO-LCS-LENGTH-AUX(X, Y, c, b)
    m = |X|
    n = |Y|
    if c[m, n] != 0 or m == 0 or n == 0
        return
    if x[m] == y[n]
        b[m, n] = ↖
        c[m, n] = MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y[1..n - 1], c, b) + 1
    else if MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y, c, b) ≥ MEMO-LCS-LENGTH-AUX(X, Y[1..n - 1], c, b)
        b[m, n] = ↑
        c[m, n] = MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y, c, b)
    else
        b[m, n] = ←
        c[m, n] = MEMO-LCS-LENGTH-AUX(X, Y[1..n - 1], c, b)

MEMO-LCS-LENGTH(X, Y)
    let c[1..|X|, 1..|Y|] and b[1..|X|, 1..|Y|] be new tables
    MEMO-LCS-LENGTH-AUX(X, Y, c, b)
    return c and b

walkccc.me

丁寧な説明

  • L′ は L の昇順ソートなので，L′ の任意の部分列は単調増加．
  • LCS(L, L′) は両方に現れる最長の共通部分列，故 L′ の性質からその間で最長単調増加部分列を得る．
  • ソートは O(n log n) だが，LCS 部分が Θ(n²) を支配するため全体は O(n²)．

問題15.4-6 ★

長さ n の数列に対し，最長単調増加部分列を O(n log n) 時間で求めるアルゴリズムを示せ（ヒント：長さ i の候補部分列の「末尾」を管理し，二分探索を用いる）．

解答

LONG-MONOTONIC(A[1..n])
    let B[1..n] ← +∞      // B[i] は長さ i の部分列の末尾の最小値
    let P[1..n] be new array  // 連結リストで復元用ポインタを保持
    L ← 0
    for i = 1 to n
        // 長さ 1..L の中で，B[j] < A[i] となる最大 j を二分探索
        j ← BinarySearchLargest( B[1..L], < A[i] )
        B[j+1] ← A[i]
        P[i] ← end index of 値 B[j] に対応する要素
        if j+1 > L
            L ← j+1
    // 復元：末尾が長さ L の要素から P ポインタでたどる
    return 再構築した部分列
  • 各要素ごとに B の二分探索で O(log n)
  • 全体で O(n log n) 時間 (walkccc.me)

丁寧な説明

  1. 配列 B の意味
    B[i] は「長さ i の増加部分列」のうち，末尾が取りうる最小値を保持する．

  2. 二分探索の活用
    A[i] を読むごとに，B[1..L] から A[i] を挿入すべき位置 j+1 を二分探索で決定．

  3. 部分列の復元
    P ポインタで，A[i] を B[j+1] に更新したときの直前要素の位置を記録し，最後に長さ L の末尾要素から逆順にたどって出力．

  4. 計算量

    • 各 i で二分探索 O(log n)
    • 復元も O(n)
    • 合計 O(n log n)
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?