制約充足問題とは?

Weblio 辞書 > 学問 > OR事典 > 制約充足問題の意味・解説 

制約充足問題

読み方せいやくじゅうそくもんだい
【英】:constraint satisfaction problem

概要

与えられたすべての制約満たすような各変数への値の割当て求め問題.多く組合せ問題定式化することができ,問題解決一般的な枠組み位置付けられる.主に人工知能分野で, 基盤技術1つとして研究されている.

詳説

 制約充足問題 (constraint satisfaction problem, CSP) は,一般に, n\, 個の変数 X_i\, (i = 1, 2, \ldots, n)\, と各変数 X_i\, がとり得る有限個の値から成る領域 D_i\, ,及び m\, 個の制約


C_j(X_{j_1},X_{j_2}, \ldots, X_{j_{t_j}}) \subseteq D_{j_1} \times D_{j_2} \times \cdots \times D_{j_{t_j}} (j = 1, 2, \ldots, m)\,


で定義される.制約 C_j\, は,変数 X_{j_1}, X_{j_2}, \ldots, X_{j_{t_j}}\, 対すt_j\, 制約であり,これらの変数同時にとることのできる値の組の集合である.ここで, すべての制約満たす値の組(d_1, d_2, \ldots, d_n) \in D_1 \times D_2 \times \cdots \times D_n\, CSPの解と呼び, (存在するならば) 一つ, あるいはすべての解を求めることがCSP目的である.

 なお, 人為的新たな変数加えることで,多項制約複数二項制約記述することができ,制約二項制約限定した形で定式化することも多く, 二項CSP (binary CSP) と呼ばれる.また, 上の定義では, 制約は値の組の集合与えられるが, それらすべてを陽に記述する必要はなく,等式論理式などを用いて表現することもできる.

 CSPの高い定式化能力を活かして汎用問題解決器 (general problem solver) の開発が可能である.すなわち, 与えられた問題CSPとして定式化し, その解を求めることで元の問題を解くことができる.この考え制約プログラミング通ずるものである. 制約プログラミングでは, 制約充足システムが行うものとし, それゆえ, 制約記述することのみがプログラマ (ユーザ) の仕事であり, それ自体プログラミング考えられる [1].

 CSP解法としては,バックトラッキング法 (backtracking method) が代表的である. これは制約違反が起こらないように, ある順序に従って, 変数への値の割当て順次行っていく方法であり, 木探索 (tree search) とも呼ばれる.変数に値を割当てる際, すべての制約満たす値が存在なければ, 一つ前変数に戻ってその値を取消し, 他の値を試みる (バックトラック) という操作繰り返す. この方法により, CSP厳密に解くことが可能であるが, バックトラック頻繁に発生する場合には効率的ではない. そこで, 木探索効率的に行うための手法が種々提案されている. フォワードチェッキング (forward checking) は, 変数に値を割当てる度に, まだ値が割当てられていない変数値域から, 制約矛盾する値を予め削除しておく方法である. このとき, ある変数値域が空になれば, 木探索を進めることなく, 現在の割当てが解の一部とはなり得ない結論けられる. このように, 制約矛盾する値を変数値域から削除する方法は, 一般に制約伝播 (constraint propagation) と呼ばれ, 問題縮小のための前処理としても用いられる. また, バックジャンピング (backjumping) では, 木探索において変数に値を割当てる際, そのすべての値が, 変数 X\, 以前に値が割当てられた変数制約矛盾起こす場合, 一つ前変数に戻るのではなく, 変数 X\, まで戻ってその値を変更する. いずれも無駄な探索を防ぐために刈りを行うものであり, この他, バックマーキング (backmarking) やバックチェッキング (backchecking) などの手法が提案されている. また, バックトラックの数は, 値を割当てる変数順序変数割当てる値の順序依存する. これらの順序発見的手法用いて定め方法提案されている [3].

 上述の手法を用いることにより, 多少探索効率化が可能であるが, CSPが解を持つかどうか決定する問題はNP完全であり, 多項式時間CSPを(厳密に)解くアルゴリズム存在しない考えられる. そこで, バックトラックなしの木探索で(すなわち多項式時間で)解を一つ求めることができるCSP部分クラスが,k\, -整合 (k\, -consistency) や k\, -木 (k\, -tree) といった概念用いて定義されている [2, 3].

 CSP対す近似アルゴリズム研究数多くなされている.その多くは,すべての制約満たすとは限らない変数の値の組 (d_1, d_2, \ldots, d_n)\, に対して, 値の変更繰り返していくことで解を求めようとするものであり, 反復改善法 (iterative improvement) や山登り法 (hill climbing method) などと呼ばれている.厳密性は保証されないが, 実用上, 非常に有効であることが計算実験により確かめられている. これらの最も初期のものとしては, MCHC法 (min-conflict hill climbing) が挙げられる. これは,制約違反している変数一つ任意選び, その値を制約違反数が最も少なくなる値に変更するという操作を, どの変数の値を変更しても制約違反数を減らすことができなくなるまで繰り返すのである. もちろんこれだけでは高い性能は望めず, 初期割当てを変えて何度試行繰り返すなどの工夫が必要である. ニューラルネットワーク (neural network) による近似解法研究比較古く, 代表的なものとして GENET呼ばれるものがある. その他多数の手法が提案されており, アニーリング法 (simulated annealing) や遺伝アルゴリズム (genetic algorithm) など, 組合せ最適化問題対す一般的な枠組みとして近年盛んに研究されている, メタ戦略 (meta-heuristics) の適用行われている [3].

 制約充足最適化問題 (constraint satisfaction optimization problem, CSOP) は, 解 (d_1, d_2, \ldots, d_n) \in S\, に対してその評価値を定め関数 f: S \rightarrow Z\, 与えられ, それを最小化(あるいは最大化)する問題である(ここで, S\, 解集合, Z\, 整数集合). CSOPはCSP拡張であり, スケジューリング問題など多く現実問題を含む. CSOPの厳密解法としては, 分枝限定法一般的である. 基本的にCSPバックトラッキング法と同じであり, 無駄な探索を省くため, いかに効率良く刈りを行うかが重要となる.



参考文献

[1] 渕一博 監修, 溝口文雄, 古川康一, J-L. Lassez 編, 『制約論理プログラミング』, 1989.

[2] 西原清一, 「制約充足問題の基礎と展望」, 『人工知能学会誌』, 12 (3) (1997), 351-358.

[3] E. Tsang, Foundations of Constraint Satisfaction, Academic Press, 1993.


制約充足問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2014/08/22 21:58 UTC 版)

制約充足問題(せいやくじゅうそくもんだい、: Constraint satisfaction problem, CSP)は、複数の制約条件を満たすオブジェクトや状態を見つけるという数学の問題を指す。CSPは特に人工知能オペレーションズ・リサーチで研究されている。多くのCSPでは、それなりの時間内に解くのにヒューリスティクス組合せ最適化手法を組み合わせる必要がある。




「制約充足問題」の続きの解説一覧


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「制約充足問題」の関連用語

制約充足問題のお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング



制約充足問題のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2020 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの制約充足問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2020 Weblio RSS