［ＦＴＰ］
- README
- ソースプログラム、マニュアル [106K]
www-admin@icot.or.jp
| 平成９年度 委託研究ソフトウェアの 成果ソフトウェア |
| 研究代表者： | 井上 克已 助教授 |
| 神戸大学 工学部 電気電子工学科 |
（機能）本ソフトウェアは，MGTP の持つボトムアップ型モデル生成機能
と，non-Horn 節でのケース分割機能を活かして，与えられた探索
問題を効率良く解くためのものである．
本ソフトウェアが対象とする探索問題には以下のものがある．
(a) 定理証明問題
(b) モデル生成問題とその応用
(c) 組合せ問題（コストなし）
(d) コスト付き決定問題・最適化問題
このうち，(a) については，これまで MGTP では停止性が保証されて
いなかった問題の一部を扱うことができる．(b) では充足可能な節
集合のモデルを有限の極小モデルに関して計算することができる．
(c) は生成したモデルにより，制約充足問題の解を与える問題であり，
各モデルにコストを付け，あるコスト以下（以上）のモデルが存在
するかどうかの決定問題，および最小または最大のコストを持つ
モデルを生成することで最適化問題を解くものが (d) である．
本システムが対象とする知識ベースは，可能な場合分けを表現する
ために選言を許した節集合から構成されるが，各選言肢にはその重み
やペナルティを表現するためのコストが付加されているものとする．
問題によっては，解くべきゴールの述語が指定され，そのリテラルを
含むモデルでコスト最小のものを求めることになる．
（役割）本ソフトウェアは，より高度な知識処理を実現する知識ベースシス
テムの基礎となる推論制御機構と探索機能を提供している．知識情報
処理システムにとって，探索処理の処理能力はシステムの性能を左右
する大きな要因の一つである．その探索処理の最適化は，実現する
システムに依存する形で行われるべきであり，本ソフトウェアでも
MGTP のケース分割に適したヒューリスティック探索を実現することで，
MGTP が本来持っている高速性を損なうことなく利用している．
（特徴）MGTP における推論戦略を，従来の深さ優先探索に基づくものから
DFID (反復深化深さ優先) 探索に変更したことにより，MGTP の停止性
を向上させている．また，探索問題を宣言的に記述するために，コスト
を持つ一階言語を提供し，これを処理するために MGTP を拡張してい
る．さらに，最適化問題を効率良く解くために，Non-Horn Magic Set
(NHM) 法を併用して，ゴール（目標述語）に関係するボトムアップ
推論のみに絞り込み，コストに基づく BFID (反復深化型最良優先)
探索を行う．このようにして，ゴールのコストが最小となるモデルを
効率良く発見することができる．なお，DFID/BFID 探索は問題における
コストの有無によって切替える．
・使用言語
Prolog
（SICStus Prolog v.2.1#9 で開発したが，他の Prolog でも動くように
SICStus に特有のユーティリティプログラムは使用していない．ただし
動作は SICStus 以外では未確認）
・OS 等の環境
UNIX
・ソースプログラムの分量
「MGTP-BF」 (約290KB): MGTP-BF のソフトウエァ本体．評価用の例題を含む． 「MGTPにおける推論制御と探索問題への適用」 (約360KB): MGTP-BF の探索方式の説明・処理系の機能・実験結果を含む解説書に， 付録としてユーザーズマニュアルを添付したもの．
・ファイル構成
以下のファイルとディレクトリを含む．
www-admin@icot.or.jp