(92) 制約 MGTP ( Prolog版 / KL1版 / KLIC版)


	マ シ ン：PIM/UNIXマシン
	環　　境：PIMOS/UNIX, KLIC
	言　　語：Prolog/KL1
	ソース量：0.2 MB
	文　　書：マニュアル (日本語・英語)

概要

有限領域の制約充足問題を解くための MGTP 処理系

特徴

負の制約伝搬を実現するために、negative atom を用いたルール表現が可能。
unit refutation ルール、を導入。
といったルールに関して、それと論理的に等価であるやといった負の制約伝搬ルールが記述可能。
モデル候補集合に含まれるアトムとモデル拡張候補集合に含まれる選言の間で unit simplification が行ない、冗長な枝を削除する。

機能

オリジナルの MGTP は有限領域の制約充足問題に対して非常に簡易な一階述語形式での記述を可能にしたが、反面、負の情報を扱わないため、枝刈り効果が十分ではなく、探索木が爆発してしまうという欠点を持っていた。

CMGTP はこのような欠点を補うため、MGTP に負アトムを導入し、また、以下に示すような unit refutation、unit simplificationのメカニズムを導入することによって、負の情報による制約伝搬を可能にした。ここで、$M, D$ はそれぞれモデル候補集合、モデル拡張候補集合を表す。

CMGTP では、有限領域の制約充足問題の制約式をダイレクトに記述できるという意味で、制約記述のためのメタ言語として考えることができる。

例題として扱った有限代数分野の準群問題に関しては、非常に効率良く解が求められることがわかっている。

ＦＴＰ

README.
制約 MGTP ( Prolog版 / KL1版 / KLIC版) [597K]

www-admin@icot.or.jp