まとめ

instance (Ord c, Eq p) => Ord (CostPath c p) where x < y = cost x < cost y

cost (CP (c,p)) = c

まず，8 パズルを解くための，IS を用いない全探索プログラムを，5 章同様，次のよう に定義する．

pz (CP (cost,path), conf)

| isGoal conf = CP (cost,path)

| otherwise = minimum [pz (CP (cost+1, mv:path), cf) | (mv,cf) <- children conf]

関数 children は前章とわずかに異なり，配置 cf のリストではなく，スライドした手

mv と cf からなる組のリストを返す．

次に，IS を用いるように計算の終端と近似値を明示し，pzの再帰呼び出しと minimum をパラメータ化することにより，以下の定義を得る．

pz rec min (CP (cost,path), conf)

| isGoal conf = CP (cost,path) <=? E

| otherwise = CP (cost + md conf, path) <=?

min [rec (CP (cost+1, mv:path), cf) | (mv,cf) <- children conf]

三つのアルゴリズムを実装した探索プログラムを構成するには，単に toBF，toDFBB， toID を，上限の初期値 uinit とともに，pzに適用するだけでよい．

pzB = toBF pz

pzD = toDFBB pz uinit pzI = toID pz

6.7 まとめ

本章では，主要な探索アルゴリズムである最良優先，深さ優先分枝限定，反復深化を純 関数的に実装した．本実装を用いれば，素朴な全探索プログラムの簡潔なプログラム構 造を保ったまま，実行効率のよい探索プログラムを構成することができる．我々は，後 続計算の必要性を判定するために，計算の中間結果の参照を可能にする IS を用いた．ま

66 第6章 枝刈り機構における探索アルゴリズムの実装 た，再帰呼び出しと最小値（あるいは最大値）を求める関数を仮引数にした高階関数を定 義し，最小値（最大値）を求めるための IS 上の適切な関数を実引数として与えることに より，全探索プログラムの簡潔さを保ったまま，三種類の効率的な探索プログラムを構成 した．我々の実装は，最良優先のみを対象とする従来の実装 [5] よりも包括的であり，深 さ優先分枝限定と反復深化による探索プログラムを，最良優先探索プログラムと同様の方 法により構成することができる．IS を用いる我々の実装手法は，例えば不一致限定探索

（limited discrepancy search）[11] など，他の探索アルゴリズムにも適用できるものと考 えられる．本手法に基づく様々な探索アルゴリズムのライブラリの構築が今後の課題で ある．

第 7 章 結論

本研究では，問題の定義式（仕様）と解き方（実装）を分離できるという枝刈り機構の 高いモジュール性を活用するプログラミング手法の確立を目指し，メモ化機構との併用 法，オーバヘッドの削減法，探索アルゴリズムの実装法という，三つの手法を提案した．

これらの提案により，枝刈り機構の適用範囲の拡大，効率化，ライブラリの拡充を実現し た．提案手法を実現するにあたり問題の定義式の形を完全に保つことを方針とした結果，

提案手法を用いることにより，問題の定義式を記述するだけで，従来よりも広い範囲の問 題を実行効率よく解くプログラムが構成できるようになった．以下，本研究の三つの成果 について各論を述べる．

本研究の一つめの提案である，メモ化機構との併用法の実現により，動的計画法を行う ようなプログラムの記述においても，枝刈り機構が有効であることを明らかにした．本研 究では，枝刈り機構とメモ化機構を併せもつよう，遅延評価を行う関数型言語を拡張する ことにより，両機構の併用を実現した．従来研究においては，枝刈り機構だけをもつ言語 やメモ化機構だけをもつ言語が提案されていたが，本研究においては，枝刈りとメモ化の 併用による相乗効果に着目し，両機構を一つの言語の評価機構の中に積極的に採り入れ た．そのように拡張した言語は，枝刈りとメモ化の併用の記述を簡潔にするというだけで なく，遅延評価よりも一般化された評価戦略を実現するという特徴をもつことを示した．

これは両機構に備わる次のような性質によるものであった．すなわち，枝刈り機構は，値 に至る途中の中間結果（近似値）をもとに枝刈りを行うので，通常の遅延評価のように値 を最後まで求める必要がないという性質を備える．また，メモ化は，同じ場所の式の評価 を高々一回にするという遅延評価の方式に加え，プログラム中の異なる場所に現れる同じ 式の値を求めるような重複計算を除去することができるという性質を備える．この両機構 の性質を同時に備えることにより，遅延評価よりも一般化された評価戦略を実現すること ができた．そして，この特徴により，この言語を用いれば，必要な計算だけを進め，必要 に応じて中断した計算を再開する漸次計算を簡潔に実現できることを明らかにした．

二つめの提案である，オーバヘッドの削減法の実現により，枝刈り機構を用いるプログ

68 第7章 結論 ラムの実行効率の安定的な向上を達成した．枝刈り機構を用いるプログラムの主たるオー バヘッドとは，計算の必要性を調べるための近似値（値に至る途中の中間結果）に伴う計 算であり，本研究では，近似値を間引くという投機的評価を行うことによりオーバヘッド を削減した．近似値を間引くことは，計算の必要性を調べる回数を減らすことを意味する ため，不要な計算を進めてしまうかもしれないというリスクが，間引きには伴う．しか し，枝刈り機構が実現する細粒度な要求駆動計算においては，このような投機的評価に伴 うリスクが少ないという特徴があるため，適切に間引きを行えば，安定的にオーバヘッド を削減できる．本研究では，以上のようなオーバヘッドの原因と特徴を明らかにし，適切 な間引きの方法を提案した．提案手法は，既存の言語の枠組みの中で記述できる単純な関 数（spec）を用いるものである．この関数に与える間引きの判定式は，ナップサック問題 を解くプログラムのように，最大値を求める関数（max_B）を二者択一で用いるようなプ ログラムであれば，プログラムの展開という半ば機械的な作業によって導けることを明ら かにした．また，構造の異なる二つのプログラムに対して提案手法を適用し実験を行うこ とで，実行効率の安定的な改善が得られることを実証した．

三つめの提案である，探索アルゴリズムの実装法の実現により，全探索プログラムを記 述するだけで実行効率のよい探索プログラムの構成を可能にするような，探索アルゴリズ ム・モジュールの実装を達成した．本研究では，最もよく知られた探索アルゴリズムであ る最良優先，深さ優先分枝限定，反復深化を純関数的に実装した．枝刈り機構を用いる探 索プログラミングにおいては，探索空間を網羅的に探索する全探索プログラムは，探索問 題の定義式とみなせるから，探索問題の解き方，すなわち探索アルゴリズムは，定義式と は別の関数定義として記述できる．さらに，全探索プログラムにおいて，再帰呼び出しと 最小値を求める関数をパラメータ化すれば，個々の探索アルゴリズムに基づいて最小値を 求める関数（minimumB，minimumD，minimumI）を与えることで，全探索プログラムの簡 潔さを保ったまま，実行効率のよい探索プログラムを構成できることを明らかにした．こ のように，本研究で実装した三つのモジュールは，差し替えが可能であり，したがって，

探索アルゴリズムの容易な使い分けを可能にする．提案する実装法は，他の探索アルゴリ ズムにも適用できるものと考えられ，枝刈り機構における探索アルゴリズム・ライブラリ 構築の礎となるものである．

謝辞

本論文をまとめるまでには，多くの方々からご指導とご支援を賜わりました．お世話に なったすべての方々に心から感謝の意を表します．

博士後期課程において主任指導教員をしていただいた岩崎英哉教授（電気通信大学）に は，あらゆる面において親身のご指導と暖かいご支援をいただくとともに，関数プログラ ミングの奥深さを教えていただきました．深く感謝いたします．

学部 4 年から博士後期課程 2 年まで主任指導教員をしていただいた竹内郁雄教授（東 京大学大学院）には，プログラミングの楽しさを教えていただくとともに，様々な活動の 場を与えていただきました．深く感謝いたします．

博士後期課程において指導教員をしていただいた尾内理紀夫教授（電気通信大学）に は，学部 4 年から今日に至るまで長年に渡って研究活動を暖かく見守っていただきまし た．深く感謝いたします．

本論文を審査していただき，ご指導とご助言をいただきました電気通信大学の野下浩平 教授，笠井琢美教授，岩田茂樹教授，中山泰一助教授に深く感謝いたいます．

学部 4 年から博士後期課程までご指導いただいた河野健二助教授（慶應義塾大学）に は，研究の楽しさを教えていただくとともに，あらゆる相談について親身なご助言をいた だきました．深く感謝いたします．

博士後期課程においてご指導いただいた大山恵弘助教授（電気通信大学）には，本研究 について的確なご意見をいただきました．深く感謝いたします．

電気通信大学情報工学科の岩崎研究室ならびに竹内研究室（2005 年度から東京大学大 学院情報理工学系研究科創造情報学専攻）の方々には，活気に満ちた刺激的な研究環境を 支えていただき，また，多くのご助言をいただきました．ここに感謝いたします．特に，

高野保直氏と田村知博氏には，細粒度な要求駆動計算機構を中心とする，日々の議論につ きあっていただきました．山下伸夫氏（株式会社タイムインターメディア）と牧大介氏に は，関数型言語を中心とするプログラミング言語について議論していただきました．ま た，明石良樹氏（株式会社野村総合研究所）には，研究に関する議論はもとより，日々の 雑事を手伝っていただきました．

最後に，暖かく見守ってくれた両親，姉兄，祖父母に感謝します．