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

$X=x_1{x}_2{x}_3=\mathrm{TEA}$、$Y=y_1{y}_2{y}_3{y}_4=\mathrm{EAST}$ とし、$D[i][j]$ を「$X$ の先頭 $i$ 文字を $Y$ の先頭 $j$ 文字に変換する最小コスト」と定める。コストは $c_{\mathrm{ins}}=1$、$c_{\mathrm{del}}=2$、$c_{\mathrm{sub}}=2$ である。

手順 1（初期値） 空文字列にするには削除だけ、空文字列から作るには挿入だけを使うので
$$D[i][0]=2i(0,2,4,6),D[0][j]=j(0,1,2,3,4).$$

手順 2（漸化式） 最後の操作が削除・挿入・置換（一致なら $0$）のどれかで場合を分けて
$$D[i][j]=\min (D[i-1][j]+2,D[i][j-1]+1,D[i-1][j-1]+2\cdot [x_i\ne y_j]).$$

手順 3（表を埋める）

$i=1$（$x_1=\mathrm{T}$）:
- $j=1$（E）: $\min (1+2,2+1,0+2)=2$
- $j=2$（A）: $\min (2+2,2+1,1+2)=3$
- $j=3$（S）: $\min (3+2,3+1,2+2)=4$
- $j=4$（T, 一致）: $\min (4+2,4+1,3+0)=3$

$i=2$（$x_2=\mathrm{E}$）:
- $j=1$（E, 一致）: $\min (2+2,4+1,2+0)=2$
- $j=2$（A）: $\min (3+2,2+1,2+2)=3$
- $j=3$（S）: $\min (4+2,3+1,3+2)=4$
- $j=4$（T）: $\min (3+2,4+1,4+2)=5$

$i=3$（$x_3=\mathrm{A}$）:
- $j=1$（E）: $\min (2+2,6+1,4+2)=4$
- $j=2$（A, 一致）: $\min (3+2,4+1,2+0)=2$
- $j=3$（S）: $\min (4+2,2+1,3+2)=3$
- $j=4$（T）: $\min (5+2,3+1,4+2)=4$

表にまとめると（行が $i=0,1,2,3$、列が $j=0,\dots ,4$）
$$\begin{array}{cccccc}& \epsilon & \mathrm{E}& \mathrm{A}& \mathrm{S}& \mathrm{T}\\ \epsilon & 0& 1& 2& 3& 4\\ \mathrm{T}& 2& 2& 3& 4& 3\\ \mathrm{E}& 4& 2& 3& 4& 5\\ \mathrm{A}& 6& 4& 2& 3& 4\end{array}$$

手順 4（答え） 求める値は $D[3][4]=4$ である。実際、先頭の T を削除（コスト $2$）し、末尾に S と T を挿入（コスト $1+1$）すれば合計 $4$ で TEA → EA → EAS → EAST と変換できる。

よって答えは $4$。

重み付き編集距離を、アラインメント（対応のつけ方）で考えて最小コストを調べる。

まず、$X=\mathrm{TEA}$ の長さは $3$、$Y=\mathrm{EAST}$ の長さは $4$ なので、挿入は少なくとも $1$ 回必要である。

最長共通部分列は $\mathrm{EA}$（長さ $2$）で、$\mathrm{T}$ を含む長さ $2$ 以上の共通部分列はない。

1. $\mathrm{E},\mathrm{A}$ を対応させる場合: $X$ の先頭の T は対応先がないので削除する（コスト $2$）。$Y$ の末尾の S, T は挿入する（コスト $1+1=2$）。合計は $4$。
2. $\mathrm{E}$ だけを対応させる場合: T の削除に $2$、A を S に置換して T を挿入するのに $2+1=3$、合計 $5$ 以上になる。ここでは A→S 置換と T 挿入で $5$、A→A とせず削除・挿入にするとさらに増える。
3. $\mathrm{T}$ を末尾の T に対応させる場合: Y の EAS を挿入し（$3$）、$X$ の E, A を削除する（$4$）ので合計 $7$。
4. 何も一致させない場合: 置換 $3$ 回（$6$）と挿入 $1$ 回（$1$）で合計 $7$。

置換のコスト $2$ は削除と挿入の和 $3$ より小さいが、上の比較では 1 が最小である。

よって最小値は $4$ である。具体的な操作列は、TEA → (T を削除) EA → (S を挿入) EAS → (T を挿入) EAST で、コストは $2+1+1=4$。

検算として、長さの差から挿入が $1$ 回以上必要で、これだけでは変換できない（T が余る）ので、最低でもコスト $1$ に加えて T の処理（削除なら $2$、置換でも $2$）が必要となる。したがって下限は $3$ であるが、置換で T を使う場合は他の文字の整合が崩れて上の場合分けのとおり $4$ を下回れない。