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

Author

祭音Myyura

Description

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

任意の の要素 と の要素 に対し、 を削除するコストは , を挿入するコストは , から へ置換するコストは とする。 なお の左端や右端にも挿入操作は可能である。 以下では2つの編集操作列において、編集操作の順序がのみ異なる場合は、同一の編集操作列とみなす。 例えば図1のように、 の左端に を挿入、 を に置換、 を削除、 を に置換、 を に置換する編集操作列のコストは となるが、これは最小ではない。

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

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

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

設問1 の値をそれぞれ求めよ。

設問2 の値をそれぞれ求めよ。

設問3 を を用いて表現せよ。

設問4 の値を求めよ。

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

Kai

設問1

設問2

設問3

設問4

設問5

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

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