記述例

5.3 記述例 47

48 第5章 枝刈り機構のオーバヘッドの削減

ks sum cap[ ] = sum

ks sum cap items@((val,size) :rest)

|cap < 0 = 0

|cap == 0 = sum

|cap > 0 = max (ks (sum+val) (cap−size) items) (ks sum cap rest)

a. 素朴な記述

ks sum cap[ ] = sum À ε

ks sum cap items@((val,size) :rest)

|cap < 0 = 0 À ε

|cap == 0 = sum À ε

|cap > 0 = sum + (val/size)∗cap À

max_B (ks (sum+val) (cap−size) items) (ks sum cap rest)

b. IS を用いる記述

ks sum cap[ ] = sum À ε

ks sum cap items@((val,size) :rest)

|cap < 0 = 0 À ε

|cap == 0 = sum À ε

|cap > 0 = sum + (val/size)∗cap À

max_B⁰ (ks (sum+val) (cap−size) items) (ks sum cap rest)

where

max_B⁰ xs ys =max_B (spec (cap ≤size ∗2) xs) (spec (cap <size) ys)

c. 粒度を調節する記述

図5.2 ナップサック問題を解くプログラム

5.3 記述例 49 が成り立つ．（items は利得率で降順に整列してあるから v/s≤val/sizeである．）さら に，cap−size∗2≥0 のとき，

x⁰ = (sum+val ∗2) + (val/size)∗(cap−size ∗2)

となり，x⁰ =x ≥y が成り立つ．したがって，cap ≥size∗2 のとき x を間引くように すればよい．

また，cap−size <0のとき，x=−∞^{となるから，}y⁰ ≥xである．ゆえに，cap < size のとき y を間引くようにすればよい．IS を用いる従来の記述に，判定式 cap ≥size∗2 と cap < size による間引きの記述を追加して，粒度を調節する記述（図 5.2 c）を得る．

粒度を調節する記述は簡潔である．素朴な記述との類似性に注意されたい．粒度を調節 するプログラムは，素朴なプログラムの構造を完全に残している．追加した記述は，本質 的には，計算の終端，近似値，間引きの記述のみである．このように，提案手法に基づけ ば，簡潔さを失うことなく粒度の調節を記述できる．

5.3.2 8 パズル

8 パズルとは，3×3に仕切られた盤上にある 1 ∼ 8 と書かれた八つのタイルを図 5.3 のような配置に揃えるパズルである．ここでは解に至る最小の手数を求めるプログラムを 取り上げる．

まず，IS を用いない素朴なプログラムを示す（図 5.4 a）．タイルが目的の配置になっ たら手数を返して計算を終える．揃っていなければ，タイルを一つスライドした配置か ら解に至る手数を再帰的に求めて，それらの最小値を取る．cost は手数を示す累積変数，

conf はタイルの配置である．isGoal は配置を判定し，children は空白に隣接する各タ イルをスライドした各配置からなるリストを返す．

次に，IS を用いるプログラムを示す（図5.4 b）．この関数 pz は二項関係を ≤ ^とする IS を返す．近似値にはマンハッタン距離を用いる．マンハッタン距離MD は，各座標の 差の絶対値の和

MD (x₁, y₁) (x₂, y₂) =|x₁−x₂|+|y₁−y₂|

と表される．あるタイルの現在地から目的地までのマンハッタン距離は，そのタイルを目

2 5 1

7 6 3

8 4

−→

1 2

3 4 5

6 7 8

図5.3 8 パズルの初期配置と目的配置

50 第5章 枝刈り機構のオーバヘッドの削減

pz cost conf

|isGoal conf =cost

|otherwise =foldl1min [pz (cost + 1)cf |cf ← children conf ]

a. 素朴な記述

pz cost conf

|isGoal conf =cost ¿ ε

|otherwise =cost + md conf ¿

foldl1min_B [pz (cost + 1)cf |cf ← children conf ]

b. IS を用いる記述

pz cost conf

|isGoal conf =cost ¿ ε

|otherwise =cost + md conf ¿

foldl1min_B⁰ [pz (cost + 1)cf |cf ← children conf ] where

min_B⁰ (x ¿xs) (y ¿ys) = minB (spec (x + 2 ≤ y) (x ¿xs)) (spec (y+ 2 ≤ x) (y ¿ys)) c. 粒度を調節する記述

図5.4 8 パズルを解くプログラム

的地にスライドさせるのにかかる最小の手数である．ゆえに，現在の配置から目的の配 置に至るまでにかかる最小の手数は，各タイルの目的地までのマンハッタン距離の総和

md conf として表せる．この総和をそれまでの手数に加えた値を近似値とする．

提案手法に基づき，粒度調節の記述を追加する．minB (x ¿x⁰ ¿xs⁰) (y¿y⁰ ¿ys⁰) において，x⁰ ≤y のときx を，y⁰ ≤x のときy を間引くようにすればよい．間引きの判 定式を，ks とは異なる方法により求める．pz では min_B を可変長のリストに適用して

5.4 実験 51