Question

CSP的基本信息

Answer 1

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的解：每个变量有一个满足所有相关约束的值
特点：
状态的分解代表：一组变量及其值
利用状态的结构和通用启发方式
通过确定违反约束的变量与值组合可取消大部分搜索空间