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

标签：

• Kyoto-University
• Minimum-Edit-Distance
• Tree-Metric

Author

Isidore, 祭音Myyura

Description

設問1

２つの文字列の編集コストは、文字の置換・削除・挿入により、一方を他方に変換するのに必要最小限の操作（置換・削除・挿入）の数で定義できる。 なお、２つの文字列の長さは同じとする。以下の問いに答えよ。

(1) 文字列 PARIS を PAIRS に編集するコストを答えよ。

設問2

すべての頂点の次数が１または３であり、辺に向きがない、根無し無順序木について考える。 次数が１の頂点を葉と呼ぶ。 すべての辺には正の値の長さが与えられ、葉 $X, Y$ 間の最短路の長さを $d(X, Y)$ とする。

(1) ３つの葉 $A, B, C$ を持ち、それ以外には葉を持たない木を考える。$d(A, B)=12, d(A,C)=10, d(B, C)=6$ を満たす木を重複なく全て導出して、各辺の長さとともに図示せよ。

(2) ４つの葉 $A, B, C, D$ を持ち、それ以外には葉を持たない木を考える。$d(A, B)=12, d(A,C)=10, d(A,D)=7, d(B, C)=6, d(B,D)=9, d(C,D)=7$ を満たす木を重複なく全て導出して、各辺の長さとともに図示せよ。

题目描述

1. 两个等长字符串的编辑成本定义为用字符替换、删除、插入把一个变成另一个所需的最少操作数。求将 PARIS 编辑为 PAIRS 的成本。
2. 考虑无根、无序、无向树，每个顶点度数为 1 或 3；度 1 顶点称叶，每条边长度为正，叶 $X,Y$ 间最短路长度记为 $d(X,Y)$。
   1. 树恰有叶 $A,B,C$，且 $d(A,B)=12$、$d(A,C)=10$、$d(B,C)=6$。无重复地求出所有满足条件的树，标出各边长度并画图。
   2. 树恰有叶 $A,B,C,D$，且 $d(A,B)=12$、$d(A,C)=10$、$d(A,D)=7$、 $d(B,C)=6$、$d(B,D)=9$、$d(C,D)=7$。 无重复地求出所有满足条件的树，标出各边长度并画图。

考点

• 最小编辑距离：在插入、删除、替换单位代价下求两个短字符串的最少操作数。
• 树度量重构：利用叶间成对距离的和差恢复三叉树拓扑与枝长，并检查正长度及所有可能的叶分割。

Kai

設問1

The answer is $2$.

A = ["P", "A", "R", "I", "S"]
B = ["P", "A", "I", "R", "S"]
cost = [[0]*(len(A)+1) for _ in range(len(B)+1)]

for i in range(len(A)):
    cost[i+1][0] = cost[i][0]+1
for j in range(len(B)):
    cost[0][j+1] = cost[0][j]+1

for i in range(len(A)):
    for j in range(len(B)):
        c = 0 if A[i] == B[j] else 1
        cost[i+1][j+1] = min(cost[i][j+1]+1, cost[i+1][j]+1, cost[i][j]+c)

for i in range(len(cost)):
    print(cost[i])

設問2

(1)

葉 $A,B,C$ のみを持つ根無し無順序木を考える。

すべての頂点の次数は $1$ または $3$ なので，3 つの葉を持つ木は，中央に次数 $3$ の頂点 $X$ を 1 つ持つ形に限られる。

各辺の長さを

$$XA=x,\qquad XB=y,\qquad XC=z$$

とおく。

条件より，

$$x+y=12$$

$$x+z=10$$

$$y+z=6$$

である。

これを解くと，

$$x=\frac{12+10-6}{2}=8$$

$$y=\frac{12+6-10}{2}=4$$

$$z=\frac{10+6-12}{2}=2$$

となる。

したがって，求める木は次の 1 つである。

      A
      |
      | 8
      |
      X
     / \
  4 /   \ 2
   /     \
  B       C

(2)

4 つの葉 $A,B,C,D$ を持ち，それ以外には葉を持たない木を考える。

すべての頂点の次数が $1$ または $3$ であるから，内部頂点は 2 つである。したがって，木の形は葉の分割により

$$AB|CD,\qquad AC|BD,\qquad AD|BC$$

の 3 通りを調べればよい。

与えられた距離は

$$d(A,B)=12,\quad d(A,C)=10,\quad d(A,D)=7,$$

$$d(B,C)=6,\quad d(B,D)=9,\quad d(C,D)=7$$

である。

場合 1：$AB|CD$

この場合，木の形は次のようになる。

A -- u -- v -- C
B --/     \-- D

辺の長さを

$$Au=a,\quad Bu=b,\quad uv=e,\quad Cv=c,\quad Dv=d$$

とおく。

このとき，

$$d(A,C)-d(A,D)=c-d$$

である。与えられた値を代入すると，

$$10-7=3$$

より，

$$c-d=3$$

である。

一方，

$$d(B,C)-d(B,D)=c-d$$

でもあるが，

$$6-9=-3$$

より，

$$c-d=-3$$

となる。これは矛盾である。

したがって，この場合は不可能である。

場合 2：$AC|BD$

この場合，木の形は次のようになる。

A -- u -- v -- B
C --/     \-- D

辺の長さを

$$Au=a,\quad Cu=c,\quad uv=e,\quad Bv=b,\quad Dv=d$$

とおく。

このとき，

$$d(A,B)-d(A,D)=b-d$$

である。与えられた値を代入すると，

$$12-7=5$$

より，

$$b-d=5$$

である。

一方，

$$d(C,B)-d(C,D)=b-d$$

でもあるが，

$$6-7=-1$$

より，

$$b-d=-1$$

となる。これは矛盾である。

したがって，この場合も不可能である。

場合 3：$AD|BC$

この場合，木の形は次のようになる。

A -- u -- v -- B
D --/     \-- C

辺の長さを

$$Au=a,\quad Du=d,\quad uv=e,\quad Bv=b,\quad Cv=c$$

とおく。

条件より，

$$a+d=d(A,D)=7$$

$$b+c=d(B,C)=6$$

$$a+e+b=d(A,B)=12$$

$$a+e+c=d(A,C)=10$$

$$d+e+b=d(D,B)=9$$

$$d+e+c=d(D,C)=7$$

である。

まず，

$$(a+e+b)-(a+e+c)=12-10$$

より，

$$b-c=2$$

である。

また，

$$b+c=6$$

なので，

$$b=4,\qquad c=2$$

を得る。

次に，

$$a+e+b=12$$

に $b=4$ を代入すると，

$$a+e=8$$

である。

また，

$$d+e+b=9$$

に $b=4$ を代入すると，

$$d+e=5$$

である。

さらに，

$$a+d=7$$

であるから，

$$(a+e)+(d+e)=8+5$$

より，

$$a+d+2e=13$$

となる。

$$a+d=7$$

なので，

$$7+2e=13$$

より，

$$e=3$$

である。

したがって，

$$a=8-e=5$$

$$d=5-e=2$$

となる。

よって，

$$a=5,\quad d=2,\quad e=3,\quad b=4,\quad c=2$$

である。

したがって，求める木は次の 1 つである。

      A
      |
      | 5
      |
      u
     / \
  2 /   \ 3
   /     \
  D       v
         / \
      4 /   \ 2
       /     \
      B       C

すなわち，

$$\boxed{ Au=5,\quad Du=2,\quad uv=3,\quad Bv=4,\quad Cv=2 }$$

である。

木の形は $AD|BC$ の分割に対応するものだけである。