制約充足問題

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

制約充足問題の具体例:

• エイト・クイーン
• 四色問題
• 数独
• 充足可能性問題

制約充足問題を解くアルゴリズムとしては、AC-3アルゴリズム、バックトラッキング、制約違反最小化などがある。

参考文献

• Tsang, Edward (1993年). Foundations of Constraint Satisfaction. Academic Press. ISBN 0-12-701610-4. http://www.bracil.net/edward/FCS.html 
• Dechter, Rina (2003年). Constraint processing. Morgan Kaufmann. ISBN 1-55860-890-7. http://www.ics.uci.edu/~dechter/books/index.html 
• Apt, Krzysztof (2003年). Principles of constraint programming. Cambridge University Press. ISBN 0-521-82583-0 

関連項目

• 宣言型プログラミング
• 制約プログラミング

外部リンク

• Tomás Feder, Constraint satisfaction: a personal perspective
• Constraints archive
• Forced Satisfiable CSP Benchmarks of Model RB
• Benchmarks -- XML representation of CSP instances