この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

アルゴリズムと計算量の問題

難易度 4大学院入試の標準レベル大学数学アルゴリズムと計算量

文字列 $X$ に次の $3$ 種類の操作をくり返し行って、文字列 $Y$ に変換することを考える。

挿入: 任意の位置に $1$ 文字を挿入する。コストは $1$
削除: $1$ 文字を削除する。コストは $1$
置換: $1$ 文字を別の $1$ 文字に置き換える。コストは $3$

操作のコストの合計の最小値を、 $X$ から $Y$ への重み付き編集距離という。
$X = CATGACT, Y = ACGTCAGT$
のとき、 $X$ から $Y$ への重み付き編集距離を求めよ。

この問題で使うもの

最長共通部分列（説明と入口の問題）
編集距離（説明と入口の問題）

この問題を解けるようになるまで（3 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

置換のコスト $3$ と、「削除 $+$ 挿入」のコストを比べてみよう。最適な変換で使う操作の種類が絞れる。

ヒント 2

挿入と削除だけを使うとき、削除されずに残る文字は $X$ と $Y$ の共通部分列になる。コストは $∣ X ∣ + ∣ Y ∣ - 2 ℓ$ （ $ℓ$ は残る文字数）と表せる。

ヒント 3

最長共通部分列の長さ $L [i] [j]$ を、 $x_{i} = y_{j}$ なら $L [i - 1] [j - 1] + 1$ 、そうでなければ $max (L [i - 1] [j], L [i] [j - 1])$ で表を埋めて求めよう。 $X$ の最初の $3$ 文字 $CAT$ と $Y$ 全体の LCS の長さは $3$ になる。

答えと解説

答えを見る

7

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

置換を使わなくてよいこと. 置換 $1$ 回（コスト $3$ ）は、その文字の削除と新しい文字の挿入（コスト $1 + 1 = 2$ ）で置き換えられ、コストが真に下がる。したがって最適な変換は挿入と削除だけからなるとしてよい。

挿入・削除だけの場合のコスト. 挿入と削除だけで $X$ を $Y$ に変えるとき、 $X$ のうち削除されずに残る文字は、順序を保ったまま $Y$ の中に現れるので、 $X$ と $Y$ の共通部分列をなす。残る文字数を $ℓ$ とすると、削除は $∣ X ∣ - ℓ$ 回、挿入は $∣ Y ∣ - ℓ$ 回必要で、逆に長さ $ℓ$ の共通部分列があればこの回数で変換できる。よって
$(重み付き編集距離) = ∣ X ∣ + ∣ Y ∣ - 2 LCS (X, Y)$
であり、 $LCS (X, Y)$ （最長共通部分列の長さ）を動的計画法で求めればよい。

LCS の動的計画法. $X = x_{1} \dots x_{7}$ , $Y = y_{1} \dots y_{8}$ とし、 $L [i] [j]$ を $x_{1} \dots x_{i}$ と $y_{1} \dots y_{j}$ の LCS の長さとする。 $L [0] [j] = L [i] [0] = 0$ で
$L [i] [j] = {L [i - 1] [j - 1] + 1 max (L [i - 1] [j], L [i] [j - 1]) (x_{i} = y_{j}) (x_{i} \neq = y_{j})$
である。表を埋めると（行が $X$ の文字、列が $Y$ の文字 $A, C, G, T, C, A, G, T$ ）
$C A T G A C T A 0111111 C 1111122 G 1112222 T 1122223 C 1122233 A 1222333 G 1223333 T 1233334$
となり、 $LCS (X, Y) = L [7] [8] = 4$ である。実際、例えば $CTGT$ （ $X$ の第 $1, 3, 4, 7$ 文字、 $Y$ の第 $2, 4, 7, 8$ 文字）や $CAGT$ は長さ $4$ の共通部分列である。

答え.
$∣ X ∣ + ∣ Y ∣ - 2 LCS (X, Y) = 7 + 8 - 2 \cdot 4 = 7.$
具体的には、共通部分列 $CTGT$ を残し、 $X$ の第 $2, 5, 6$ 文字 $A, A, C$ の $3$ 文字を削除して $CTGT$ にし、そこへ $Y$ の第 $1, 3, 5, 6$ 文字にあたる $A, G, C, A$ の $4$ 文字を対応する位置に挿入すると
$CTGT \to A CTGT \to AC G TGT \to ACGT C GT \to ACGTC A GT = Y$
となり、コスト $3 + 4 = 7$ で変換できる。

別解

置換のコストは $3$ で、削除 $1$ 回と挿入 $1$ 回のコストの和 $2$ より大きい。よって置換は使わないとしてよく、操作は挿入と削除だけである。このとき、残す文字(共通部分列)の長さを $L$ とすると、コストは $(7 - L) + (8 - L) = 15 - 2 L$ となる。したがって $L$ は $X$ と $Y$ の最長共通部分列(LCS)の長さをとればよい。

LCS の長さを動的計画法で求める。 $X = CATGACT$ の先頭 $i$ 文字と $Y = ACGTCAGT$ の先頭 $j$ 文字の LCS の長さを $L (i, j)$ とする。 $j = 1, \dots, 8$ の順に並べると、
- $i = 1$ (C): $0, 1, 1, 1, 1, 1, 1, 1$
- $i = 2$ (A): $1, 1, 1, 1, 1, 2, 2, 2$
- $i = 3$ (T): $1, 1, 1, 2, 2, 2, 2, 3$
- $i = 4$ (G): $1, 1, 2, 2, 2, 2, 3, 3$
- $i = 5$ (A): $1, 1, 2, 2, 2, 3, 3, 3$
- $i = 6$ (C): $1, 2, 2, 2, 3, 3, 3, 3$
- $i = 7$ (T): $1, 2, 2, 3, 3, 3, 3, 4$

よって $L = 4$ である。

検算: 共通部分列 $CGCT$ は $X$ の $1, 4, 6, 7$ 文字目、 $Y$ の $2, 3, 5, 8$ 文字目にあり、長さ $4$ の共通部分列が実際に存在する。 $X$ から残りの $3$ 文字(A,T,A)を削除し、 $Y$ の残りの $4$ 文字(A,T,A,G)を挿入するとコストは $3 + 4 = 7$ になる。

コストは $15 - 2 \cdot 4 = 7$ 。

アルゴリズムと計算量の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題