著者

大和田 勇人 溝口 文雄

雑誌

全国大会講演論文集

巻号頁・発行日

vol.49, pp.45-46, 1994-09-20

---

制約充足問題はAIの中心的問題の一つであり,例として設計,レイアウト問題等がある.制約充足問題とは,制約集合を充足する変数への値の割り当てを決定することであり,NP-完全なクラスに属する.そのため,近似的ではあるが効率のよい解法が求められている.例えば,制約充足問題の代表的な手法であるアーク無矛盾は局所的なものであり,後戻り探索を実施する前に局所的に矛盾するものを除去する.さらに,実問題を考えると,必要十分な制約集合を与えることは困難で,できるだけ多くの制約を充足するものを求めるといった部分制約充足問題も考慮しなければならない.我々は,住宅間取り問題に対して,このような手法を導入してきたが,満足のいく解法を得ることはできず,新たなアプローチを模索している.本研究はこのような問題意識から,制約充足だけでは解決できない部分を過去の事例を利用して,帰納学習により補完するという方法を考える.特に,正,負事例から論理プログラムを生成する帰納論理プログラミングを用いて,制約充足問題の近似解を求めるための規則を生成することを目指す.現状では,帰納論理プログラミングで用いられている相対最小汎化を制約論理プログラミングの枠組みから拡張し,システム化した.本稿ではその概要を報告する.