組合せ問題を高速に解くための論理型言語の設計,実現及び応用

点击翻译按钮获取中文摘要

1.まず、Prologの拡張であるBeta-Prologの設計と実現を行なった.PrologにBoolean tableというバツクトラック可能なデータ構造を導入し,Boolean tableに対して,状態が真である組を選ぶ(select),状態をテストする(test),状態を更新する(up-date)及び状態が真である組を数える(count)などの述語を備えた.実際に,Beta-Prologのコンパイラを試作した.2.Beta-Prologを基本的なグラフ問題,制約充足問題,プラニング問題,TSP問題などへ応用した.結果として,これらの組合せ問題を全部状態遷移問題として定式化でき,Beta-PrologがPrologより遥かに有効であることが実証された.3.しかし,まだたくさんの問題が困難あるいは解決不能のままとなっている.例えば,108-queen問題の最初の解を求めるのに,10時間もかかってしまった.また,Deutshの四段層の配線問題は,一週間でも解けなかった.今後,コンパイラの最適化及び言語の並列化によって,さらに高速化を図る必要がある.