部分解を利用した制約充足問題の解法について
スポンサーリンク
概要
- 論文の詳細を見る
スケジューリング問題をはじめとする人工知能のさまざまな分野で扱われる、古典的かつ重要な問題の1つに制約充足問題(Constraint Satisfaction Problem)がある。このような制約充足問題を繰り返し解く場合、同一問題を最初から解き直すことは非効率的であり、繰り返し回数分の計算時間が必要となる。一方、あらかじめあらゆる入力値を想定して列挙し、解いた解を蓄積しておくことにより、同一入力値に対する解を瞬時に得ることができる。この場合、あらゆるパターンを想定して解くために、十分な計算機資源と処理時間が必要となる。そこで本稿では、両者の欠点を補う方法として、一度解いた制約充足問題の部分解を蓄積し、その蓄積した解を利用して制約充足問題を解くことについて説明する。また、このような制約充足問題が繰り返し行われる例の一つである、定性推論の状態遷移に本方法を適用する場合について述べる。
- 一般社団法人情報処理学会の論文
- 1992-09-28
著者
関連論文
- WWW上の電子新聞における記事ナビゲーションシステムの実現
- 意味ネットワークを用いたURL情報の整理方法に関する研究(1)
- WWWにおける情報の分類/体系化に関する研究
- 制約充足問題の木探索法による高速化手法の検討
- 部分解を利用した制約充足問題の解法について
- 交通状態予測システムにおける定量データの定性データへの取り込み
- 動的制約充足問題のための制約維持機構について
- 知識表現システムFracks/TPと交通信号制御への適用について