研究の内容

本研究において，MGTPの推論制御機能の充実と探索問題への応用を図る． 研究内容は，以下の流れに沿ったプログラム開発が中心である．

1. Depth-First Iterative-Deepening 探索による MGTP の停止性の向上
   MGTPにおける推論の流れは証明木によって表すことができる．この証明木を 探索する際，既存のMGTPでは３つの戦略[1]のいずれもが， 深さ優先探索によって探索を進めていくので， 証明木が無限長の枝をもつ場合などには停止性が保証されない． そこで，MGTPの探索戦略を今までの深さ優先探索から， DFID探索 (Depth-First Iterative-Deepning search, 反復深化深さ優先探索) [5] に変更することにより，推論の効率化を図りMGTPの停止性を向上させた． また，従来のMGTP (ALP-MGTP)とDFID探索を用いたMGTP (DFID-MGTP)を 比較し，停止性の向上および，実行時間の変化を確認した．
2. 最適化問題への応用
   DFID探索を用いた応用として，これまでの MGTPでは取り扱われていない コストのついた探索問題を解決するためにMGTPを拡張する． 拡張MGTPでは，入力節のシンタックスとして，選言肢にコストを付加した コスト付non-Horn節を採用し，これを汎用の論理型プログラミング言語と して考える．探索問題や最適化問題はこのプログラミング言語上で宣言的に 記述される．この応用として，最短経路問題を始めとして，巡回セールスマン 問題などのグラフの組合せ最適化問題を解く．
3. 最適化問題の効率化
   上記最適化問題を効率良く解くためには，コスト最小の最適解を発見できる 探索方式を実現するだけでは不十分である．そこで，MGTP上の推論制御方式 として既に提案されている Non-Horn Magic Set (NHM) 法[2]を 併用する．NHMを用いることで，ゴール(目標述語)に関係するボトムアップ 推論のみに絞ることができ，そこで発生するサブゴールに対して， コストに基づいて BFID 探索(Best-First Iterative-Deepening search; 反復深化型最良優先探索)を行う．BFID 探索はIDA* (Iterative-Deepening A*) のように，DFID探索のメモリ効率・停止性と最良優先探索の最適性の両方の 利点を兼ね備えた探索方式として提案する．この探索方式を用いて， ゴールのコストが最小となる推論パスを効率良く発見するための拡張MGTPが 整備される．