京都大学 情報学研究科 知能情報学専攻 2020年8月実施 情報学基礎 F2-1

Author

祭音Myyura

Description

削除、挿入、置換により数列 \(A\) を数列 \(B\) に変形する編集操作列を考える。\(A\) と \(B\) の各要素は以下の通りである。

\[ A[1] = 8, \; A[2] = -4, \; A[3] = 1, \; A[4] = -6 \]

\[ B[1] = 7, \; B[2] = 2, \; B[3] = -4, \; B[4] = 3 \]

任意の \(A\) の要素 \(a\) と \(B\) の要素 \(b\) に対し、\(a\) を削除するコストは \(|a|\), \(b\) を挿入するコストは \(|b|\), \(a\) から \(b\) へ置換するコストは \(|a - b|\) とする。 なお \(A\) の左端や右端にも挿入操作は可能である。 以下では2つの編集操作列において、編集操作の順序がのみ異なる場合は、同一の編集操作列とみなす。 例えば図1のように、\(A\) の左端に \(7\) を挿入、\(8\) を \(2\) に置換、\(-4\) を削除、\(1\) を \(-4\) に置換、\(-6\) を \(3\) に置換する編集操作列のコストは \(7 + 6 + 4 + 5 + 9 = 31\) となるが、これは最小ではない。

図1: 編集操作列の例（順不同）

     8    -4    1    6
|    |     |    |    |
7    2         -4    3

\(A[i:j]\) を \(A\) の \(i\) 番目から \(j\) 番目の連続する要素で構成される数列とし、\(B[i:j]\) も同様に定義する。 \(M(m, n)\) を \(A[1:m]\) を \(B[1:n]\) に変形するコスト最小の編集操作列のコストとする。 動的計画法に基づくアルゴリズムに関する以下の設問に答えよ。

設問1 \(M(1, 1), M(1, 2), M(1, 3), M(1, 4)\) の値をそれぞれ求めよ。

設問2 \(M(2, 1), M(3, 1), M(4, 1)\) の値をそれぞれ求めよ。

設問3 \(M(4, 4)\) を \(M(3, 3), M(3, 4), M(4, 3)\) を用いて表現せよ。

設問4 \(M(4, 4)\) の値を求めよ。

設問5 \(A\) を \(B\) に変形するコスト最小の編集操作列をすべて図1のように示せ。

Kai

\[ M[i][j] = \min \begin{cases} M[i-1][j]+|A_{i}|\\ M[i][j-1]+|B_{j}|\\ M[i-1][j-1]+|A_{i}-B_{j}| \end{cases} \]

設問1

\[ M(1,1) = 1, \ M(1,2) = 3, \ M(1,3) = 7, \ M(1,4) = 10 \]

設問2

\[ M(2,1) = 5, \ M(3,1) = 6, \ M(4,1) = 12 \]

設問3

\[ M(4,4) = \min \begin{cases} M(3,3) + 9\\ M(3,4) + 6\\ M(4,3) + 3 \end{cases} \]

設問4

\[ M(4,4) = 11 \]

設問5

 8        -4    1   -6
 |    |    |    |    |
 7    2   -4    3

 8   -4    1   -6   
 |    |    |    |    |
 7         2   -4    3