跳转至

CSPs

CSPs | Introduction to Artificial Intelligence

简介

CSPs: Constraint Satisfaction Problems

  • 定义：我们考虑其中的三个重要因素：

    1. Variables: \(N\)个变量构成的一个set: \(\{x_1,x_2,\cdots,x_N\}\)(each take on a single value from some defined set of values);

    2. Domain: 一个set: \(\{x_1,x_2,\cdots,x_N\}\)可以代表一个CSP情况中的所有\(x_i\)可能值构成的所有情况;

    3. Constraints: 对变量本身的约束以及变量之间关系的约束.

  • 举例：N皇后问题（在一个\(N\times N\)的棋盘上，放置N个国际象棋中的皇后，有多少种放置方法使得她们之间不能相互攻击？）

    在这个CSP问题中，可以这样定义：

    1. Variables: \(X_{ij}, 0\leq i,j \leq N\)

    2. Domain: \(X_{ij} \in \{0,1\}\)，其中\(X_{ij}=0\)指的是\((i,j)\)这个格子上没有皇后，=1表示有皇后放置.

    3. Constraints: \(\sum_{i,j}X_{i,j} = N\)，并且对于\(\forall i,j,k\)，有以下约束：

      \[ \begin{cases}(X_{ij},X_{ik})\in \{(0,0),(0,1),(1,0)\}\\(X_{ij},X_{kj})\in \{(0,0),(0,1),(1,0)\}\\ (X_{ij},X_{i+k,j+k})\in \{(0,0),(0,1),(1,0)\}\\ (X_{ij},X_{i+k,j-k})\in \{(0,0),(0,1),(1,0)\}\end{cases} \]

    N皇后问题是一个NP问题.

  • 举例：四色问题（地图染色问题）

    首先把地图上的每个区域以及他们的相邻关系抽象成无向图，比如对澳大利亚进行这样粗暴的划分：

    cs188/4color-0.png

    cs188/4color.png

    转换成常用的graph等数据类型之后再进行深入讨论.

  • Backtracking 是对DFS的优化，遵循以下两个方面的原则：

    1. 对所有元素排序并按照这样的顺序进行赋值. 由于\(\{x_1,x_2,\cdots,x_N\}\)地位相同可交换，所以不妨设排序就是\(x_1x_2\cdotsx_N\)；

    2. 选取某个变量的值时，选取不会与先前确定的变量值冲突的可能value，如果全都冲突，则回到上一个确定下来的变量并改变它的值.

  • CSPs的Backtracking算法伪代码：

    function Backtracking-Search(CSP) returns solution/failure
    return recursive-backtracking({},CSP)

function recursive-backtracking(assignment,csp)
    if assignment complete:
        return assignment
    var = Select-Unassigned-Variable
    for value in order-domain-values(var,assignment,csp):
        if value consistent with the assignment given constraints:
            add {var = value} to assignment 
            result = recursive-backtracking(assignment,csp)
            if result != failure: return result
            remove {var = value} from assignment
    return failure

    Backtracking = DFS + variable-ordering + fail-on-violation （回溯 = 深度优先搜索 + 变量排序 + 冲突即失败）

  • Backtracking的改进方法1：Filtering

    移除已知会导致回溯的值，提前剪除未分配变量的域的大小（概括一下就是剪枝）。其中的一种简单方法是前向检查，即分配给\(X_i\)值之后，剪除与 \(X_i\) 有约束且分配后会违反约束的未分配变量的域.

    用地图染色问题来举例，考虑下面的情况：

    cs188/4color.png

    先后分配WA,Q的颜色后，NT,SA,NSW的域缩小.

    前向检查的思想可以推广为弧一致性的原则. 对于弧一致性，我们将约束图中的每个无向边解释为两个指向相反方向的有向边. 这些有向边中的每一条被称为一条弧.

    弧一致性 (Arc Consistency) 算法的工作原理如下：

    1. 将所有arc存入priority queue Queue​中；
    2. 将Queue中的arc递归式地移除，保证每个被移除的弧\(X_i\rightarrow X_j\)都有：对于尾变量\(X_i\)的每个剩余值$ v\(，头变量\)X_j\(至少有一个剩余值\)w\(满足\) X_i=v \(，\) X_j=w \(不会违反任何约束。如果\) X_i \(的某个值\) v\(与\) X_j \(的任何剩余值都不兼容，就将\)v \(从\)X_i$的可能值集合中移除；
    3. 设此时所有未赋值的点构成集合为\(\{x_k\}\)，如果移除了\(X_i\rightarrow X_j\)的某个值，那么需要将所有弧\(X_k \rightarrow X_i, \forall X_k \in \{x_k\}\)放置回Queue中；
    4. 继续操作直到Queue变空，或者某个变量的域变空引发backtracking.

    Filtering一般使用AC-3算法实现，伪代码：

    function AC-3(CSP) returns the CSP
    initial queue, csp 
    // a binary CSP with variables{x1,x2,…,xn} and all arcs in queue
    while queue not empty:
        (xi,xj) = remove_first(queue)
        if remove_inconsistent_values(xi,xj): // xi is tail, xj is head
            for xk in neighbors[xi]:
                queue.append((xk,xi))

function remove_inconsistent_values(xi,xj):
    moved = False
    for x in domain(xi):
        if any y in domain(xj) unsatisfy the constraint xi<-xj:
            delete x from domain(xi)
            removed = True
    return removed

    最坏情况时间复杂度：\(O(ed^3), e: \text{number of the arc edges}, d: \text{the maximum size of the domain}\).

    一些限制：留下的解法数量是不确定的，可能返回0,1或N1种解法，返回0时可能是遗漏了一些方法.

  • 接下来考虑上述的顺序如何确定： 引入两个参数，minimum remaining values (MRV) 和 least constraining value (LCV)，前者针对下一个variable的选择，后者针对单个variable的value选取.

  • MRV: chooses whichever unassigned variable has the fewest valid remaining values (the most constrained variable). This is intuitive in the sense that the most constrained variable is most likely to run out of possible values and result in backtracking if left unassigned, and so it’s best to assign a value to it sooner than later.

    选取下一个进行修改的变量时，选择剩余有效值最少的那个变量，因为最容易出现backtracking，所以要先处理.

  • LCV: select the value that prunes the fewest values from the domains of the remaining unassigned values. Notably, this requires additional computation (e.g. rerunning arc consistency/forward checking or other filtering methods for each value to find the LCV), but can still yield speed gains depending on usage.

    选取值时，从域中选择本身限制最少的那个值，这样剔除的值最少.

  • 延申：k-Consistency

    \(k = 1\): Node Consistency，即每个节点的域中所有的值必须满足unary constraints.

    \(k = 2\): Arc Consistency，即弧一致性.

    对\(k\)进行归纳，k-Consistency是指对于任意\(k\)个节点，每个\(k-1\)-Consistency都能拓展到第\(k\)个节点上.

    Strong k-Consistency: 此时不需要使用backtracking，因为

  • Structures

    如果我们遇到的是无向无环图，那么可以认为是Tree，此时我们可以将寻找到solution的时间复杂度从

    \(O(d^n)\)压缩到\(O(nd^2)\)，用到的是以下的Tree-structured CSP Algorithm:

    1. 任意选取一个节点作为Root;
    2. 进行Topological Ordering； 3.
CSP eg. - Course Scheduling, regular discussion 2

cs188/csp-0.png

1.Formulate this problem as a CSP problem in which there is one variable per class, stating the domains (after enforcing unary constraints), and binary constraints. Constraints should be specified formally and precisely, but may be implicit rather than explicit.

Variables : \(C_1,C_2,C_3,C_4,C_5\)

Domains (Unary Constraints) : $\(\{A,B,C\} \Longrightarrow C_1: \{A,C\}, C_2:\{A\},C_3:\{B,C\},C_4:\{B,C\},C_5:\{A,B\}\)$

Constraints (Binary) : \(C_1 \neq C_2, C_2 \neq C_3, C_2 \neq C_4, C_3 \neq C_4\).

2.Draw the constraint graph associated with your CSP.

总之这道题不需要想复杂化，只需要考虑某几节课如果给同一个老师，时间段就不能重叠，以此来考虑Binary Constraints即可.

摘自examprep2的练习：

  1. When enforcing arc consistency in a CSP, the set of values which remain when the algorithm terminates does not depend on the order in which arcs are processed from the queue. \(\textcolor{red}{\checkmark}\)

\(\textcolor{red}{原因：AC-3算法的最终结果是唯一的}\)

  1. Once arc consistency is enforced as a pre-processing step, forward checking can be used during backtracking search to maintain arc consistency for all variables. \(\textcolor{red}{\times}\)

  2. In a general CSP with \(n\) variables, each taking \(d\) possible values, the worst case time complexity of enforcing arc consistency using the AC-3 method discussed in class is \(\textcolor{red}{O(n^2d^3)}\).

  3. In a general CSP with \(n\) variables, each taking \(d\) possible values, the maximum number of times a backtracking search algorithm might have to backtrack (i.e. the number of the times it generates an assignment, partial or complete, that violates the constraints) before finding a solution or concluding that none exists is \(\textcolor{red}{O( d^n)}\).

  4. The maximum number of times a backtracking search algorithm might have to backtrack in a general CSP if it is running arc consistency and applying the MRV and LCV heuristics is \(\textcolor{red}{O( d^n)}\).

总结：

Backtracking算法是针对CSPs的有效方法，其中