第 4 章 枝刈り機構とメモ化機構の併用 31
4.3 記述例
本言語の有効性を検証するために，動的計画法が有効な典型問題を例として取り上げ，
提案機構により効率的なプログラムを簡潔に記述できることを示す．
動的計画法は，部分問題を互いに重複しない形に分割するのが難しい問題を解くのに有 効なアルゴリズム設計手法である．その基本的なアイデアは，重複した計算を避けるため に，部分問題の解を表に記録していき，原問題を解くのに，表を参照するというものであ る．つまり動的計画法では表を埋めることで求める解を得る．
4.3 記述例 33 本言語で提供する枝刈り機構とメモ化機構の併用により，効率的かつ簡潔な動的計画法 のプログラムを記述できる．すなわち，枝刈り機構により不要な部分問題の計算を回避で きるので，枝刈り操作を陽に記述しなくても表の必要な部分だけしか求めないプログラム になる．さらにメモ化機構により，表自身も（たとえば二次元配列のような）陽なデータ としてもつ必要がない．
本節では記述例として，動的計画法の典型的な問題である，ナップサック問題，二つの 文字列間の編集距離を求める問題，および，行列積に必要なスカラー積の回数を求める問 題を解く三つのプログラムを記述する．
4.3.1 ナップサック問題
ナップサック問題とは，数種類の品物をナップサックの容量を超えないように詰め合せ て得られる，最大の総利得を求める問題である．入力には，ナップサックの容量と，ナッ プサックに入れる品物のリストが与えられる．品物はそれぞれ大きさと利得が異なり，同 じ品物をいくつでも詰めることができる．簡単のため，品物のリストは大きさ当りの利得
（利得率と呼ぶ）の大きい順に整列してあるものとする．
まず，枝刈りもメモ化もしない，素朴なプログラムを記述する（図 4.1 a）．cap はナッ プサックの容量，items は品物のリストである．個々の品物は利得 val と大きさ size の 組として表現される．第一式は品物がない場合の記述である．第二式の cap < 0 は実現 不可能であることに対応し，cap == 0 は空きがないことに対応する．max の中の第一 項（val + ks(cap−size)items）は先頭の品物(val, size) をさらに一つ詰めた場合の総 利得であり，第二項（ks cap rest）はその品物をそれ以上詰めない場合の総利得である．
次に，枝刈り機構とメモ化機構を用いたプログラムを示す（図4.1 b）．この関数ks は，
素朴なプログラムにメモ化の宣言，計算の終端と近似値の記述を追加しただけである．
ナップサック問題は総利得に関する最大化問題であるから，二項関係を ≤ とする下降列 と，関数 maxB を用いる．近似値には利得率が最大の品物を隙間なく詰めた，いわば理 想的な総利得を用いる．品物のリストは利得率の大きい順に並んでいるので，近似値は先 頭の品物の利得率とナップサックの容量の積，すなわち (val/size)∗cap として表せる．
二つの機構を併用したプログラムは簡潔である．素朴なプログラム（図 4.1 a）と併用 したプログラム（図 4.1 b）の類似性に注意されたい．併用したプログラムは，素朴なプ ログラムの構造を完全に残しており，簡潔さを失うことなく枝刈りとメモ化を実現してい る．追加した記述は，本質的には，メモ化の宣言，計算の終端と近似値の明示のみである．
図 4.1 b のプログラムの進行の様子を図 4.2 に示す．maxB によって，近似値の大
きい（有望な）部分問題から順に計算が進められる．ks0 [C,D] を計算した時点で，
ks7 [B,C,D] の値は
34 第4章 枝刈り機構とメモ化機構の併用
ks cap[ ] = 0
ks cap items@((val,size) :rest)
|cap < 0 = −∞
|cap == 0 = 0
|cap > 0 = max (val + ks(cap−size)items) (ks cap rest)
a. 枝刈りもメモ化もしない素朴な記述
memo ks
ks cap[ ] = 0 À ε
ks cap items@((val,size) :rest)
|cap < 0 = −∞ À ε
|cap == 0 = 0 À ε
|cap > 0 = (val/size)∗cap À
maxB (val ⊕ ks(cap−size)items) (ks cap rest)
b. 枝刈り機構とメモ化機構を用いた記述
図4.1 ナップサック問題を解くプログラム
21 À (12 ⊕ (9 À (6 À (6 ⊕ (0 À ε)))))
となり，真の値が 18 に決まる．一方，15 ⊕ ks2 [A,B,C,D] の値は 15 ⊕ (6 À 6 À 4 À 2 À?)
であり，その近似値は 17 である．結果，この時点で計算が終了し，品物 B と C を一つ ずつ詰めたときの総利得 18 が求める値となる．表中の必要な部分だけを埋めることで求 める値が得られた．
ここで，さらに引き続き ks2 [A,B,C,D]を解くことを考える．この問題は，先の計算 において，ks2 [D]を計算する途中で枝刈りされた．ゆえに ks2 [D] の計算を再開するだ けで求める値を得ることができる．
二つの機構を併用したプログラムは実行効率がよい．検証のために，以下の四種のプロ
4.3 記述例 35 ks ナップサックの容量
品物の種類 7 · · · 3 2 · · · 0 [A, B, C, D] 21−−−−−−−−−−−→2 15⊕ 6
↓1 ↓5
[B, C, D] 21−−−−−−→4 12⊕ 9 6
↓3 ↓6 ↓7
[C, D] 14À? 610 4 −−−→6⊕ 0Àε
↓9 ↓8
[D] 3À? 2À?
a. ks 7 [A,B,C,D] の進行の様子 品物 大きさ 利得
A 5 15
B 4 12
C 3 6
D 2 2
b. 品物の種類 x−−−−→j v⊕ y
↓i ⇒ x À maxB (v ⊕ y)z z
ここで，i，j は計算の進行順序である．また y が
− ∞ Àεのとき −−−−→j v⊕ y を省略した．
c. 凡例
図4.2 枝刈り機構とメモ化機構を用いたプログラムの計算の進行過程
グラムについて，ks100 [A,B,C,D] の評価に引き続いてks99 [A,B,C,D] を評価した 場合の，関数 ks の適用回数を調べた（表 4.1）．
• 枝刈りもメモ化も行わない素朴なプログラム（図 4.1 a）
• 枝刈りのみ行うプログラム
• メモ化のみ行うプログラム
• 枝刈りとメモ化を併用するプログラム（図 4.1 b）
本実験では，我々が開発した，Scheme 風の文法をもち，枝刈りとメモ化を基本的な言 語機構として備えている処理系を用いた．これは，Abelson と Sussman が開発した遅延
36 第4章 枝刈り機構とメモ化機構の併用 表4.1 ks100 [A, B, C, D]の後にks99 [A, B, C, D]を
評価したときの，関数ks の適用回数
cap 素朴 枝刈りのみ メモ化のみ 併用
100 96,215 461 420 205
99 92,723 499 27 35
計 188,938 960 447 240
評価を行う Scheme 処理系 [1] を参考に，Java 言語を用いて実装した処理系である．
実験結果によれば，併用したときの適用回数が最も少ない．結果に寄与しない計算と 重複する計算を両方とも除去できたため，ks100 [A,B,C,D]を求める際には必要な計 算だけを進めることで求める解を得ることができ，ks99 [A,B,C,D]を求める際には中 断されていた後続計算を必要に応じて再開することで適用回数を抑えられた．枝刈りの みのときは重複計算を除去できないため，ks99 [A,B,C,D]を求める際に，同じ計算を 繰り返してしまった．メモ化のみのときは結果に寄与しない計算を回避できないため，
ks100 [A,B,C,D]を求める際に，部分問題をすべて計算してしまった．
ks99 [A,B,C,D]を求める際，併用したときの適用回数（35）がメモ化のみのとき（27） よりも多くなっている．これはメモ化のみのときは，ks100 [A,B,C,D]を求める際に計 算していた（実は不要だった）部分問題をたまたま再利用できたためである．併用したと きは必要になった時点で初めて計算を進めるため，cap が 99 のときの適用回数はメモ化 のみのときよりも多いが，全体では少なくなっている．
4.3.2 編集距離問題
二つの文字列間の編集距離とは，一方の文字列を他方と同じ文字列に書き換えるのにか かる，編集操作の最小の回数である．ここでの編集操作とは，一文字の置換，追加，削除 の三つとする．
まず，枝刈りもメモ化もしない，素朴なプログラムを記述する（図 4.3 a）．ed xs ys は，文字列 xs を文字列 ys に書き換えるのにかかる編集距離である．関数 ed の第一式 は，編集前の文字列 xs が空のときには，文字列 ys のすべての文字を追加するという操 作によって，編集距離を最小にできることを表している．（Haskell の文字列は文字のリ ストであることに注意されたい．）第二式は xs のすべての文字を削除するという操作に 対応する．第三式の x==y は両文字列の先頭の文字が同じであることに対応し，この場 合には後続の文字列の編集距離ed xs ys が求める編集距離となる．x6=y の場合には，x から y への置換，y の追加，x の削除という，三つの操作をした場合の編集距離のうちで
4.3 記述例 37
ed [ ]ys = length ys0 ed xs[ ] = length xs 0
ed (x :xs) (y :ys) |x == y = ed xs ys
|otherwise = 1 + minimum[ed xs ys, ed xs (y :ys), ed (x :xs) ys]
a. 枝刈りもメモ化もしない素朴な記述
memo ed
ed [ ]ys = length ys0 ed xs[ ] = length xs 0
ed (x :xs) (y :ys) |x == y = 0 ¿ ed xs ys
|otherwise = 1 ⊕ (0 ¿ minimumB [ed xs ys, ed xs(y :ys), ed (x :xs) ys])
b. 枝刈り機構とメモ化機構を用いた記述
図4.3 編集距離を求めるプログラム
最小の値が求める編集距離になる．
次に，枝刈り機構とメモ化機構を用いたプログラムを示す（図 4.3 b）．この関数 edは，
素朴なプログラムにメモ化の宣言と近似値の記述を追加しただけである．近似値にはそれ までの操作回数の累計を用いる．編集距離を求めるこの問題は，距離に関する最小化問題 であるから，二項関係を ≤ とする上昇列と，関数 minimumB を用いる．また，ここで 用いる length は，2.2 節で定義した IS を返すlength と同様の関数である．ただし，こ の length が返す上昇列の二項関係は < ではなく ≤ とする．計算の終端 ε は，IS を返
す length の中で示されることに注意されたい．
検証のため，関数 ed について，前節のナップサック問題と同様の実験を行った
（表 4.2）．枝刈り機構とメモ化機構の使用の有無を切替えた四通りのプログラムについ て，ed ”abcefghi” ”abcdefgz”を評価した後に，引き続き ed ”abdefghij” ”bcdefgyij”を 評価した場合の，関数 ed の適用回数を調べた．前節と同様，併用したときの適用回数が
38 第4章 枝刈り機構とメモ化機構の併用 表4.2 ed ”abcef ghi” ”abcdef gz” の後にed ”abdef ghij” ”bcdef gyij”を評価
したときの，関数 ed の適用回数
xs ys 素朴 枝刈りのみ メモ化のみ 併用
”abcef ghi” ”abcdef gz” 974 39 30 20
”abdef ghij” ”bcdef gyij” 227,297 63 91 25
計 228,271 102 121 45
最も少ないことが確かめられた．
4.3.3 行列積問題
行列積に必要なスカラー積の回数は，行列積の結合の仕方によって増減する．例えば，
M3,2 M2,5 M5,1 という行列積を考えよう．ここで Mi,j は i×j 行列を表す．この行 列積に必要なスカラー積の回数は，(M3,2 M2,5) M5,1 というように結合した場合には (3×2×5) + (3×5×1) 回であり，M3,2 (M2,5 M5,1) というように結合した場合には (2×5×1) + (3×2×1) 回である．ゆえに，後者のように結合すれば，前者よりもスカ ラー積を少なくすることができる．
まず，枝刈りもメモ化もしない，素朴なプログラムを記述する（図 4.4 a）．このプログ ラムにおいては，行列積を，行と列の次元からなる整数のリストとして表現する．隣り合 う行列の列と行は同次元であるから，両者を一つにまとめて表現する．例えば，このプロ グラムにおいては，上述の行列積 M3,2 M2,5 M5,1 を [3,2,5,1] と表す．したがって，行 列積 ms における，i 番目の行列の行と列を返す関数 row とcol は次のように定義され る．ここで，xs!!i は，リスト xs のi番目の要素を返す式である．
row ms i = ms !! (i−1) col ms i = ms !! i
また，行列積の結合の仕方，すなわち結合範囲を，結合する一連の行列の両端の行列の位 置によって表現する．これは直感的には，結合範囲を明示するための括弧の位置に対応す る．例えば，(M3,2 M2,5) M5,1 という結合は，1 番目から 2 番目までの行列を結合して いるので，1 と 2 という位置によって，結合範囲を表現する．
さて，関数 mm は，行列積 ms と結合範囲 l，r を引数に取る．l == r は行列積を 行わないことに対応し，l < r は二つ以上の行列からなる行列積を行うことに対応する．
l ≤i ≤ r−1 なる i を結合の境目とおくと，l から r の行列積は，l から i の行列積と i+ 1からrの行列積という，二つの行列積に分割される．このように分割した行列積全 体に必要なスカラー積の回数は，分割された二つの行列積の結果として得られる行列の行