制約充足問題の木探索法による高速化手法の検討
スポンサーリンク
概要
- 論文の詳細を見る
木探索法を用いた制約充足問題の高速化手法の1つとして、不要な探索枝をあらかじめ刈り込むフォワード・チェッキング(forward checking以下、FCと略記する)による手法がある。FCは、論理型言語を用いた制約充足問題解決のための推論機構としてCHIPやBeta-Prolog等において採用されており、木探索法を用いて制約充足問題を解く際の、効率の良いアルゴリズムの1つであることが知られている。本稿では、FCにおける制約式の評価をあらかじめ行い、変数の値域に関する評価結果を蓄積しておくことにより、同一制約の重複評価の回避と実行時の速度向上を可能とするFFC(full forward checking)法について提案し、簡単な例題(N-Queens問題)への適用結果について述べる。
- 一般社団法人情報処理学会の論文
- 1994-09-20
著者
関連論文
- WWW上の電子新聞における記事ナビゲーションシステムの実現
- 意味ネットワークを用いたURL情報の整理方法に関する研究(1)
- WWWにおける情報の分類/体系化に関する研究
- 制約充足問題の木探索法による高速化手法の検討
- 部分解を利用した制約充足問題の解法について
- 交通状態予測システムにおける定量データの定性データへの取り込み
- 動的制約充足問題のための制約維持機構について
- 知識表現システムFracks/TPと交通信号制御への適用について