ブール代数を用いた制約充足問題の定式化と解法についての検討

概要

論文の詳細を見る
制約充足は人工知能や画像理解の分野をはじめ,グラフの問題やパズルなどの探索問題,いわゆる組み合わせ問題を対象として研究がおこなわれている.制約充足問題の代表的な解法として,探索法や整合化手法を用いる方法が知られている.われわれは,このような探索主体のアプローチとは対照的な位置付けにある代数的アプローチについて論じる.本アプローチでは,制約論理型言語の探索機構を利用した制約充足問題に対する研究とは異なり,制約論理型言語におけるブール制約評価系を用いて代数的に制約充足をおこなう.本論文では,ブール代数により制約充足問題を定式化し,得られたブール方程式の求解を制約論理型言語CALにおけるブール制約の評価とみなすことにより,解であるブーリアン・グレブナ基底を求める方法について述べる.さらに,ブール制約評価系を用いた制約充足問題の効率化手法として,1)ブール制約の簡単化方式,2)制約ネットワークの構造情報に基づいた制約の評価順序の決定方式,について提案する.そして,本効率化手法の有効性を確認するために,ブール制約を用いて記述された問題に対して適用実験をおこなう.その結果,制約充足問題の解法として探索法がよく知られているが,それとは異なるあらたなブール代数評価系を用いた代数的な方法ならびに効率化手法が有効であることを示す.
1995-04-15

ブール代数を用いた制約充足問題の定式化と解法についての検討

スポンサーリンク

概要

著者

関連論文

スポンサーリンク