アルゴリズムとデータ構造
演習第 14 回
動的計画法

講義のときに配られたハンドアウトを参考に、以下の問題を解いてください。

問題１[印刷用PDF]
  1. 次元の列が <5, 10, 3, 12, 5> のとき、行列チェーン乗算の最小のコストを動的計画法で求めた結果を書きなさい。

  2. 2つの列 <1, 0, 0, 1, 0, 1, 0, 1> と <0, 1, 0, 1, 1, 0, 1, 1, 0> の LCS を動的計画法で求めた結果を書きなさい。

行列チェーン乗算問題

行列チェーン乗算問題は、行列の並び（チェーン） A1 , A2 , ..., An の積 A1A2...An（これを行列チェーン乗算と言います）を求めるときに、 行列の要素の乗算回数が最小になるように行列の乗算の順番を決める問題です。 行列チェーン乗算を求めるときに行った行列要素の乗算回数を、 行列チェーン乗算のコストとします。 したがって、行列チェーン乗算問題は行列チェーン乗算の最小のコストを求める問題と言えます。

問題が次元の列 < p0 , p1 , p2 , ..., pn-1 , pn> で与えられているとき、サイズがそれぞれ p0×p1 , p1×p2 , ..., pn-1×pn であるn個の行列の積について考えることを表しています（行列AとBの乗算が可能ならAの列数とBの行数が同じになるので、このような表記をすることで問題をコンパクトに表現できます）。

次元の列が <5, 2, 6, 4, 3> という例について、行列チェーン乗算問題を動的計画法で求めた結果を以下に示します。

この表をmとし、右側の添字をmの行の添字、左側の添字をmの列の添字とします。 このとき、m[i, j] の値は AiAi+1...Aj の最小コストを表します。 たとえば、A1A2A3 の最小コスト m[1, 3] = 88、 A1A2A3A4 の最小コスト m[1, 4] = 102 です。 m[i, i] は「積」 Ai の最小コストを表しますが、 Ai の値を求めるには行列要素の乗算は不要なので m[i, i] = 0 となります。

表 m の値は下から上に順に埋めていきます。ある段をすべて埋めた後に、 そのすぐ上の段を埋めていきます。 ある欄を埋めるときは、それより下にあるあらかじめ計算された値を使います。 はじめに一番下の段 m[i, i] (1≦i≦4) をすべて埋めます。 上で説明したように m[i, i] = 0 となります。

次に下から2段目の m[i, i+1] (1≦i≦3) を埋めます。 これらは積 AiAi+1 の最小コストですが、 この場合は行列の積の計算方法は１通りしかないので、 積 AiAi+1 の計算で行われる行列要素の乗算回数がそのまま AiAi+1 の最小コストとなります。 Ai と Ai+1 のサイズはそれぞれ pi-1×pi と pi×pi+1 なので、 行列要素の乗算回数は pi-1pipi+1 です（たとえば、A1A2 の最小コスト m[1, 2] の値は p0p1p2 = 5*2*6 = 60 となる）。 また、積 AiAi+1 により得られる行列のサイズは pi-1×pi+1 であることに注意してください。

次に下から３段目の m[i, i+2] (1≦i≦2) を埋めます。 A1A2A3 の最小コスト m[1, 3] の値を求めてみましょう。m[1, 3] の計算を行う時点では、 下の図のようにそれより下の段の値はすべて計算済みです。 積 A1A2A3 を求めるには、 A1(A2A3) と (A1A2)A3 の2通りの分割が考えられます。 最初の分割で得られた A1 と A2A3 の最小コスト m[1, 1] と m[2, 3] は、 下の図に示したように既に得られています（赤字の部分）。 もう１つの分割についても同様です（青字の部分）。

分割 A1(A2A3) の 最小コストを計算するには、 A1 と A2A3 の最小コストを求める部分問題の解 m[1, 1] と m[2, 3] を使って求めます。 積 A2A3 の値である行列を B とすると、A1 と B のサイズはそれぞれ p0×p1 と p1×p3 になるので、A1 と B との乗算で行われる行列要素の乗算回数は p0p1p3 になります。 このような考え方から分割 A1(A2A3) の最小コストを求める計算式 m[1, 1] + m[2, 3] + p0p1p3 が得られます。 行列チェーン乗算問題の動的計画法による解法で用いる式はこのような考え方で得られます。

同様にしてそれぞれの分割での最小コストを求めた結果を以下の表に示します。 この中で最小の値が積 A1A2A3 の最小コスト m[1, 3] となるので、m[1, 3] の値は 88 であることがわかります。 m[2, 4] の値も同様にして計算できます。

A1A2A3の最小コストm[1, 3]の計算
分割 左辺の行列のサイズ 右辺の行列のサイズ 各分割の最小コストを求める式 コストの値
A1(A2A3) p0×p1 p1×p3 m[1, 1] + m[2, 3] + p0p1p3 0 + 48 + 5*2*4 = 88
(A1A2)A3 p0×p2 p2×p3 m[1, 2] + m[3, 3] + p0p2p3 60 + 0 + 5*6*4 = 180

最後に一番上の段の値 m[1, 4] である 積 A1A2A3A4 の最小コストを求めます。この積を求める方法としては、 A1(A2A3A4)、 (A1A2)(A3A4)、 (A1A2A3)A4 の3つの分割が考えられます。

m[1, 3] の場合と同様にして、それぞれの分割の最小コストを計算できます。 各分割での計算で用いる最小コストは、 上の図の、分割と同じ色の欄を参照してください。

A1A2A3A4の最小コストm[1,4]の計算
分割 左辺の行列のサイズ 右辺の行列のサイズ コストを求める式 コストの値
A1(A2A3A4) p0×p1 p1×p4 m[1,1] + m[2,4] + p0p1p4 0 + 72 + 5*2*3 = 102
(A1A2)(A3A4) p0×p2 p2×p4 m[1,2] + m[3,4] + p0p2p4 60 + 72 + 5*6*3 = 222
(A1A2A3)A4 p0×p3 p3×p4 m[1,3] + m[4,4] + p0p3p4 88 + 0 + 5*4*3 = 148

この結果から m[1, 4] の値は102 であることがわかります。 したがって、最初に与えられた行列チェーン乗算問題で求めるべき積 A1A2A3A4 の最小コストは 102 となります。

LCS問題

LCS問題は、2つの列のLCS（最長共通部分列）を求める問題です。 列XとYのLCSとは、XとYの両方に共通して現れる部分列で最長のものです。 列Aから0個以上の要素を取り除いて得られる列を列Aの部分列と 呼びます。たとえば、列 ecd は列 aecbdc から1, 4, 6番目の要素 a, b, c を取り除くことで得られるので、列 ecd は列 aecbdc の部分列です。

X = < x1 , x2 , ..., xn > のとき、 Xi = < x1 , x2 , ..., xi > とします。 ただし、X0 は空列を表すとします。 c[i, j] を Xi と Yj のLCSの長さとすると、 c[i, j]の値は以下のようになります。

xi = yj のとき xi ≠ yj のとき

列 abcbdab と bdcaba のLCSの長さを動的計画法で求めた結果を以下に示します。

問題２

n個の行列 A1, A2, ..., An の次元の列 < p0 , p1 , ..., pn-1 , pn > が与えられたとき、積 A1, A2, ..., An の計算に必要な最小限の行列要素の乗算回数を出力するプログラムを作成しなさい。 (ex14-2-skel.c)

問題１で示した例に対する実行例を示します(緑がプログラムへの入力、 赤がプログラムの出力)

		% ./a.out
		4
		5 2 6 4 3
		the least cost = 102

入力の１行目が行列の個数、２行目が行列の次元の列を表します。

注意: 表mと次元の列pの添字について
問題１の例やハンドアウトの擬似コードでは表 m の添字は 1 から n まで、 次元の列 p の添字は 0 から n までですが、 C言語では配列の添字は 0 から始まります。 そのため、ハンドアウトの擬似コードとプログラムでは添字がずれるものがあります。 特に、変数 i の最大値と変数 j の値は擬似コードのままでは正しい結果が得られないので注意してください。
問題３

2つの文字列 X = < x1 , x2 , ..., xm > と Y = < y1 , y2 , ..., yn > が与えられたとき、 X と Y のLCSの長さを出力するプログラムを作成しなさい。 (ex14-3-skel.c)

問題１で示した例に対する実行例を示します(緑がプログラムへの入力、 赤がプログラムの出力)

		% ./a.out
		abcbdab
		bdcaba
		the length of LCS = 4