约束满足问题

定义约束满足问题
约束满足问题(Constraint satisfaction problems, CSP)是一种简单的形式化表示语言。当一组变量的一种取值满足所有变量约束时,问题就得到了解决。

约束满足问题包含三个成分:\(X,D,C\).
X是变量集合\(X_1,\cdots,X_n\);
D是值域集合\(D_1,\cdots,D_n\);
C是描述变量取值的约束集合。每个约束\(C_i\)是有序对\(\langle scope, rel\rangle\), scope是约束中的变量组,rel定义了这些变量取值应满足的关系。

问题的状态由对部分或全部变量的一个赋值来定义。一组不违反约束的赋值称为相容的(consistent), 每个变量都有值的赋值称为完全的(complete). CSP的解即为相容且完全的一组赋值。

约束条件的种类:一元(Unary) 、二元(Binary) 或多元(Higher-order).
使用对偶图可以将任意n元CSP转换成二元CSP。变量个数人意的约束称为全局约束,如AllDiff.

现实世界中还会有一些偏好约束(Preferences), 指出在不违反所有(绝对)约束的情况下,哪些解是更好的。这样的问题称为约束优化问题(constrained optimization)

CSP中的推理
推断(Inference)选择使用约束来减少某个变量的合法取值范围,从而进一步减少其他变量的合法取值范围。这一过程称为约束传播(constraint propagation). 其核心思想是局部相容性。

1. 弧相容(Arc consistency)
单个变量满足一元约束称为结点相容(容易解决,这里不讨论),两个变量满足二元约束称为弧相容。弧\(X\to Y\)是相容的,当且仅当对每个X的取值\(x\), 都有一个Y的取值\(y\)使得\((x,y)\)满足约束。如果每个变量X相对其他变量Y都是弧相容的,称网络是弧相容的(此处默认只有二元约束)。

如果利用弧相容\(X\to Y\)删去了X的一部分取值,则与X相容的变量\(Z\to X\)也需要被重新检查。弧相容可以视为求解CSP问题的预处理。可以采用AC-3算法来解决弧相容:维护一个弧相容队列,每弹出一组\((Xto Y)\), 如果X发生变化,则所有指向X的弧需要被重新加入队列中。

2. 路径相容(Path consistency)
路径相容通过观察变量得到隐式约束并以此来加强二元约束。两个变量的集合\(\{X_i,X_j\}\)相对于第三个变量\(X_m\)是相容的,如果对\(X_i,X_j\)的每一组二元相容赋值\((a,b)\), \(X_m\)都有一个取值\(c\)使得\((a,c),(c,b)\)同时是相容的。

3. k-相容(k-consistency)
以上相容的概念可以推广到k个变量中:如果对任何\(k-1\)个变量的一组合法取值,都存在第k个变量的一个取值与之相容,称这个CSP是k相容的。弧相容、路径相容分别是\(k=2,k=3\)的特例。如果一个图是\(1,2,\cdots,k\)-相容的,称其为强k相容的。

CSP的回溯搜索
CSP的赋值具有可交换性,不必考虑赋值顺序。因此只需要考虑搜索树一个结点的单个变量。回溯搜索用于深度优先搜索中,每次为一个变量选择一个赋值,当没有变量合法取值时就回溯。

高效回溯搜索,需要考虑的问题:
1. 下一步选择哪个变量赋值?
采取最少剩余值(MRV, minimum remaining values)启发式,选择合法值域个数最少的变量。也可以采用度启发式(Degree heuristic),选择与未赋值变量约束最多的变量。

2. 按什么顺序尝试当前变量的赋值?
采取最少约束值(LCV, least constraining value)启发式,优先选择给邻居提供更多选择的值。

3. 每步搜索通过什么样的推理约简搜索空间?
前向检验(FC, Forward Checking), 当X被赋值x时,对所有与X弧相容的Y值进行检验,删去其中与x不相容的值。
FC不能检验出所有不相容,因为它使当前变量弧相容,但并不向前看使其它变量弧相容。算法MAC(maintaining arc consistency)用于解决这一问题,在一个变量X被赋值之后,利用AC-3进行推断,从与X邻接的所有弧\(Y\to X\)出发进行约束传播。

CSP局部搜索
使用完整状态的形式化,初始状态是每个变量(随机)赋一个值。最简单的启发式是最小冲突启发式。这样可以采取一些局部搜索算法(如爬山法,模拟退火)。

    所属分类:人工智能     发表于2022-05-20