约束满足问题
目標的狀態需要滿足一組限制條件的數學問題 / 维基百科,自由的 encyclopedia
约束满足问题(Constraint satisfaction problem,CSPs)是种数学的问题,其定义为一组物件(object),而这些物件需要满足一些限制或条件。CSPs将其问题中的单元(entities)表示成在变数上有限条件的一组同质(homogeneous)的集合,这类问题透过“约束满足方法”来解决。CSPs是人工智慧和运筹学的热门主题,因为它们公式中的规律,提供了共同基础来分析、解决很多看似不相关的问题。通常约束满足问题具有高度复杂性(英语:Complexity of constraint satisfaction),需要同时透过启发式搜索和联合搜索(英语:Combinatorial search)的方法,来在合理的时间内解决问题。布林可满足性问题(SAT),可满足性的理论(英语:Satisfiability modulo theories)(SMT)和回答集程式设计(ASP)可以算是某种程度上的约束满足问题。
以下举例为几个简单的约束满足问题:
这些ASP是BooleanSAT和SMT教学课程的人常会使用的范例。在现实情况下,约束满足问题通常更困难,且难以用简单的范例来表达,例如自动规划(英语:Automated planning and scheduling)和资源配置。