CSP（约束满足问题）：由一个变数集合和一个约束集合组成。问题的一个状态是由对一些或全部变数的一个赋值定义的完全赋值：每个变数都参与的赋值。问题的解是满足所有约束的完全赋值，或更进一步，使目标函式最大化。

CSP={V,D,C}

变数：V={V1,…,VN}

例如：图中结点的值

域：每个变数能取的d个值的集

例如：D={R,G,B}

约束：C={C1,…,CK}

每个约束由一组变数与一列该组变数允许取的值组成

例如：[(V2,V3),{(R,B),(R,G),(B,R),(B,G),(G,R),(G,B)}]

通常隐式地定义约束，即，定义一个函式来测试一组变数是否满足该约束

例如：对每条边(i,j)，有ViVj

CSP的解：每个变数有一个满足所有相关约束的值

特点：

状态的分解代表：一组变数及其值

利用状态的结构和通用启发方式

通过确定违反约束的变数与值组合可取消大部分搜寻空间

约束满足问题(CSP-Constraint Satisfaction Problem)是人工智慧研究领域的一个重要分支,现实生活中的很多问题,都可以用约束满足问题来建模,如视觉(Vision),调度中的资源分配(Resource allocation),时序推理(Temporal reasoning)等.约束满足问题通常都是NP-hard问题,在其众多求解算法中,基于回溯的搜寻算法(BT-backtracking algorithm)是一个完备的核心算法.该算法在选择实例化变数时,採用深度优先策略,若相容性检查失败则启动回溯机制,并通过引入展望(look-ahead)和回顾(look-back)两种模式,显着地提高了搜寻效率[1].基于冲突的向后跳转[2]和动态的回溯算法[3]等是回顾模式类的搜寻算法;基于相容性技术的算法是展望模式类的搜寻算法.而弧相容(AC-arc consistency)则是众多相容性算法中一个高效的相容性技术[4],如算法AC3[5],AC4[6],AC2001[7]等.由于弧相容维护(MAC-maintaining arc consistency)，具有高效的求解效率和低额空间代价的特点,所以MAC是求解约束满足问题的一个主流搜寻技术.