约束求解算法

约束求解算法（constraint solving algorithm），理学-计算机科学技术-计算机科学理论-算法-组合算法，约束求解算法是用来求解约束规划（constraint programming）的算法。约束规划分为约束满足问题与约束优化问题，约束求解是指求解这两类约束问题。约束满足问题由三个部分<X,D,C>构成：X是一个有限的变量集合{x1,x2,…,xn}；D是一个值域集合{dom(x1),dom(x2),…,dom(xn)}，其中dom(xi)是变量xi的有限值域；C是一个约束的集合{c1,c2,…,ce}，其中任意一条约束cj建立在一个变量集合X(cj)上，其中X(cj)是X的一个子集，用来指定X(cj)中变量取值的可行组合，即满足约束cj的取值组合。约束满足问题的解是为X中每个变量在其值域中选择一个值，使得C中的所有约束都满足。求解约束满足问题的目的是找到一个解、找到多个解（可能是全部解）或者证明问题无解。约束优化问题在约束满足问题基础上加入优化目标（即软约束），软约束要尽可能满足，而其他约束（硬约束）必须满足。