CSP过滤

• 15 min read • 2835 words
Tags: CSP
Categories: Introduction to Artificial Intelligence

CSP过滤

1. 相关概念

在约束满足问题中,过滤(Filtering) 是通过约束传播来缩小变量域的技术。过滤的核心思想是在搜索过程中主动推理,提前发现和消除不可能的赋值,从而显著减少搜索空间。

过滤不同于盲目的回溯搜索,它利用约束的结构信息进行局部推理,在赋值之前就排除明显不可行的选择,避免了大量无意义的搜索尝试。

2. 一致性层次

过滤基于不同层次的一致性概念,这些一致性条件越强,过滤效果越好,但计算成本也越高。

a.a. 节点一致性(Node Consistency)

节点一致性要求每个变量的域都满足所有涉及该变量的一元约束。

对于变量XiX_i,如果其域DiD_i中的每个值都满足所有一元约束C(Xi)C(X_i),则称XiX_i是节点一致的。

例:如果约束是 X ≠ 红色,那么红色必须从X的域中移除

b.b. 弧一致性(Arc Consistency)

弧一致性是最重要和最常用的一致性概念。对于约束C(Xi,Xj)C(X_i, X_j),如果对于XiX_i域中的每个值aa,在XjX_j的域中都存在至少一个值bb使得约束(a,b)(a,b)得到满足,则称弧(Xi,Xj)(X_i, X_j)是一致的。

形式化定义: aDi,bDj s.t. C(Xi=a,Xj=b) is satisfied\forall a \in D_i, \exists b \in D_j \text{ s.t. } C(X_i = a, X_j = b) \text{ is satisfied}

关于弧一致性的详细内容CSP算法章节有详细介绍,这里略去。

4. 前向检查

a.a.相关概念

与弧一致性不同,前向检查并不是在搜索前的预处理,而是在搜索过程中、有一个变量被赋值时触发。

前向检查具有局部性。只检查刚刚被赋值的变量的直接邻居,不会产生连锁反应,只能发现由当前赋值直接导致的冲突。

a.a. 算法实现

def forward_check(self, var: Variable, value: Any, 
                     assignment: Dict[Variable, Any]) -> Optional[Dict[Variable, Set[Any]]]:
    """
    Perform forward checking after assigning value to var
    Returns dict of removed values or None if inconsistent
    """
    removed_values = {}
        
    for constraint in self.csp.constraints:
        if constraint.involves_variable(var):
            for other_var in constraint.variables:

                # Only trigger in assignment
                if other_var != var and other_var not in assignment:
                    to_remove = set()
                        
                    for other_value in other_var.domain:
                        test_assignment = assignment.copy()
                        test_assignment[var] = value
                        test_assignment[other_var] = other_value
                            
                        if not constraint.is_satisfied(test_assignment):
                            to_remove.add(other_value)
                        
                    if to_remove:
                        if other_var not in removed_values:
                            # Memorize what we will do to removed value 
                            removed_values[other_var] = set()
                        removed_values[other_var].update(to_remove)
                        other_var.domain -= to_remove
                            
                        # Check if domain becomes empty
                        if not other_var.domain:
                            return None
        
    # Return the record of removed value
    return removed_values

5. 弧一致性的维护

在搜索过程中动态维护弧一致性可以获得比单纯前向检查更强的过滤效果。

a.a. MAC算法

MAC算法是搜索算法中的一种,当给一个变量赋值时,它会:

  1. 先调用前项检查,检查变量邻近值的可行性。
  2. 然后调用弧一致性检查,使用ac3算法检查弧一致性。
class MaintainingArcConsistency(ConsistencyFilter):
    """MAC (Maintaining Arc Consistency) algorithm"""
    
    def __init__(self, csp: 'CSPWithFiltering'):
        super().__init__(csp)
        self.ac_filter = ArcConsistencyFilter(csp)
    
    def propagate_assignment(self, var: Variable, value: Any) -> bool:
        """
        Propagate assignment and maintain arc consistency
        Returns False if inconsistency detected
        """
        # Remove inconsistent values from assigned variable
        var.domain = {value}
        
        # Remove inconsistent values from neighbors
        for constraint in self.csp.constraints:
            if constraint.involves_variable(var):
                for other_var in constraint.variables:
                    if other_var != var:
                        to_remove = set()
                        for other_value in other_var.domain:
                            assignment = {var: value, other_var: other_value}
                            if not constraint.is_satisfied(assignment):
                                to_remove.add(other_value)
                        
                        other_var.domain -= to_remove
                        if not other_var.domain:
                            return False
        
        # Maintain arc consistency
        return self.ac_filter.ac3()

6. 更强的一致性

a.a. 路径一致性(Path Consistency)

路径一致性要求对于任意两个变量XiX_iXjX_j的值组合(a,b)(a,b),都存在中间变量XkX_k的值cc,使得约束(Xi=a,Xk=c)(X_i=a, X_k=c)(Xk=c,Xj=b)(X_k=c, X_j=b)都得到满足

路径一致性算法PC-2算法类似于AC-3,但处理的是三元组(Xi,Xj,Xk)(X_i, X_j, X_k)

def pc2(self) -> bool:
    """
    PC-2 algorithm implementation
    Returns False if inconsistency detected
    """
    queue = deque()
        
    # Initialize queue with all variable triples
    variables = self.csp.variables
    for i, xi in enumerate(variables):
        for j, xj in enumerate(variables):
            if i != j:
                for k, xk in enumerate(variables):
                    if k != i and k != j:
                        queue.append((xi, xj, xk))
        
    while queue:
        xi, xj, xk = queue.popleft()
            
        if self.revise_path_consistency(xi, xj, xk):
            if not self.has_consistent_pairs(xi, xj):
                return False
                
            # Add related triples back to queue
            self.add_related_triples(queue, xi, xj, xk)
        
    return True
    
def revise_path_consistency(self, xi: Variable, xj: Variable, xk: Variable) -> bool:
    """Revise path consistency for triple (xi, xj, xk)"""
    revised = False
    to_remove = []
        
    # Check all value pairs for xi and xj
    for x in xi.domain:
        for y in xj.domain:
            # Check if there exists a supporting value in xk
            has_support = False
            for z in xk.domain:
                assignment = {xi: x, xj: y, xk: z}
                if self.satisfies_path_constraints(xi, xj, xk, assignment):
                    has_support = True
                    break
                
            if not has_support:
                to_remove.append((x, y))
                revised = True
        
    # Remove unsupported pairs (simplified - actual implementation
    # would need to maintain explicit constraint relations)
    return revised

b.b. k-一致性

k-一致性是一致性概念的推广:如果任意k1k-1个变量的一致赋值都可以扩展为包含第k个变量的一致赋值,则CSP是k-一致的。

  • 1-一致性 = 节点一致性
  • 2-一致性 = 弧一致性
  • 3-一致性 = 路径一致性

7. 过滤与搜索的结合

a.a. 智能回溯

可以将过滤算法应用到回溯算法中,让回溯更加智能:

def intelligent_backtrack(self, assignment: Optional[Dict[Variable, Any]] = None) -> Optional[Dict[Variable, Any]]:
    """Intelligent backtracking with filtering"""
    if assignment is None:
        assignment = {}

    # Apply constraint propagation
    if not self.arc_filter.ac3():
        return None

    # Check if solved by propagation alone
    if all(len(var.domain) == 1 for var in self.variables):
        return {var: next(iter(var.domain)) for var in self.variables}

    if self.is_complete(assignment):
        return assignment

    # Select variable using heuristics
    var = self.select_variable(assignment)
    if var is None:
        return assignment

    # Try each value in domain
    for value in self.order_values(var, assignment):
        assignment[var] = value

        # Save state for backtracking
        saved_state = self.arc_filter.save_state()

        # Apply MAC
        if self.mac_filter.propagate_assignment(var, value):
            result = self.intelligent_backtrack(assignment)
            if result is not None:
                return result

        # Restore state and backtrack
        self.arc_filter.restore_state(saved_state)
        del assignment[var]

    return None