CSP排序

• 11 min read • 2101 words
Tags: CSP
Categories: Introduction to Artificial Intelligence

CSP排序

1. 排序启发式概念

在约束满足问题的回溯搜索中,排序启发式(Ordering Heuristics)决定了搜索过程中变量选择和值选择的顺序。好的排序策略可以显著减少搜索空间的探索,将指数级的搜索问题转化为多项式时间可解的问题。

排序启发式的核心思想是通过智能的选择顺序来尽早发现冲突或找到解,避免在搜索树的错误分支上浪费大量计算资源。这种启发式方法体现了"失败优先"和"成功优先"的不同哲学。

2. 变量排序启发式

变量排序决定了在回溯搜索中下一个要赋值的变量,不同的选择策略会导致截然不同的搜索效率。

a.a. 最少剩余值(MRV)

最少剩余值(Most Constrained Variable, MRV)启发式选择域中合法值数量最少的变量进行赋值。

def select_mrv_variable(csp, assignment):
    """Select the unassigned variable with the smallest domain"""
    unassigned = [var for var in csp.variables if var not in assignment]
        
    if not unassigned:
        return None
        
    return min(unassigned, key=lambda var: len(csp.current_domain(var)))

MRV的策略原则如下:

  • 失败优先原则:最受约束的变量最可能导致失败,尽早检查可以及时剪枝
  • 减少分支因子:选择域小的变量减少了搜索树的分支
  • 约束传播效果:对受约束变量的赋值会引发更多的约束传播

b.b. 度启发式(Degree Heuristic)

度启发式选择与最多未赋值变量相连的变量,用于打破MRV的平局。

def degree_heuristic(csp, assignment):
    """Compute the number of constraints a variable has with unassigned variables"""
    unassigned = set(var for var in csp.variables if var not in assignment)
    
    def degree(var):
        count = 0
        for constraint in csp.constraints:
            if var in constraint.variables:
                # Count the number of unassigned variables in the constraint
                unassigned_in_constraint = sum(1 for v in constraint.variables if v in unassigned and v != var)
                if unassigned_in_constraint > 0:
                    count += 1
        return count
    
    return degree

MRV和度启发式可以组合使用:

def select_variable_combined(csp, assignment):
    """Select variable using combined MRV and Degree heuristics"""
    unassigned = [var for var in csp.variables 
                  if var not in assignment]
    
    if not unassigned:
        return None
    
    # First, sort by MRV
    min_remaining_values = min(len(csp.current_domain(var)) for var in unassigned)
    
    mrv_vars = [var for var in unassigned if len(csp.current_domain(var)) == min_remaining_values]
    
    # If only one MRV variable, return it
    if len(mrv_vars) == 1:
        return mrv_vars[0]
    
    # Use Degree heuristic to break ties
    degree_func = degree_heuristic(csp, assignment)
    return max(mrv_vars, key=degree_func)

3. 值排序启发式

值排序决定了对选定变量尝试赋值的顺序,好的值排序可以更快找到解或更早发现冲突。

a.a. 最小约束值(LCV)

最小约束值(Least Constraining Value, LCV)启发式选择对其他变量约束最少的值,即保留其他变量最多选择的值。

def order_lcv_values(var, csp, assignment):
    """Sort the domain values of a variable by LCV order"""
    def constraining_count(value):
        """Count how many values for other variables would be eliminated by choosing this value"""
        count = 0
        test_assignment = assignment.copy()
        test_assignment[var] = value

        # Check all related variables
        for constraint in csp.get_constraints_involving(var):
            for other_var in constraint.variables:
                if (other_var != var and 
                    other_var not in assignment):
                    # Count the number of values that would be eliminated
                    for other_value in csp.current_domain(other_var):
                        test_assignment[other_var] = other_value
                        if not constraint.is_satisfied(test_assignment):
                            count += 1
                        del test_assignment[other_var]

        del test_assignment[var]
        return count

    values = list(csp.current_domain(var))
    return sorted(values, key=constraining_count)

LCV的策略原则如下:

  • 成功优先原则:选择约束最少的值增加找到解的可能性
  • 保持灵活性:为其他变量保留更多选择空间
  • 延迟冲突:将困难的决策推迟到后面处理

b.b. 随机值排序

在某些情况下,随机选择可能比启发式方法更有效:

def order_random_values(var, csp, assignment):
    """Randomly order the domain values of a variable"""
    import random
    values = list(csp.current_domain(var))
    random.shuffle(values)
    return values

4. 动态变量排序

a.a. 动态MRV

在搜索过程中,变量的约束程度会发生变化,于是我们可以在每次赋值后就进行一次排序,也就是动态排序

def dynamic_mrv_search(csp):
    """Dynamic MRV search"""
    assignment = {}
    
    def backtrack():
        if len(assignment) == len(csp.variables):
            return assignment
        
        # Dynamically select the MRV variable
        var = select_mrv_variable(csp, assignment)
        
        for value in order_lcv_values(var, csp, assignment):
            if csp.is_consistent(var, value, assignment):
                assignment[var] = value
                
                # Update domains after constraint propagation
                inference = csp.forward_check(var, value, assignment)
                if inference is not None:
                    result = backtrack()
                    if result:
                        return result
                
                # Undo inference and assignment
                csp.restore_domains(inference)
                del assignment[var]
        
        return None
    
    return backtrack()

b.b. 自适应排序

自适应搜索策略(Adaptive Ordering)更进一步地引入了学习机制。其核心思想是:

在整个回溯搜索的过程中,持续记录和统计历史信息——哪些变量的选择频繁导致失败,哪些值的选择更容易通向成功。然后,利用这些宝贵的历史数据来动态地、更智能地指导未来的搜索方向。该排序的完整流程如下:

  1. 初始化:在搜索开始前,创建一个AdaptiveOrdering实例,其内部的失败和成功计数器均为空
  2. 进入递归搜索循环:
    1. 选择变量:根据MRV和历史失败次数,选出一个变量var
    2. 排序值:根据历史成功次数,对变量var的所有可用值进行排序。
    3. 尝试赋值:按排序后的顺序,逐一尝试变量var的值val
      1. 进行赋值var=val
      2. 执行推理(如前向检查或 MAC)。
      3. 递归调用,进入下一层搜索。
    4. 处理递归返回结果:
      • 如果递归成功 (找到解):
        • 这是一个宝贵的学习机会!遍历当前完整解中的每一个 (变量, 值) 对,记录这些方法并记录成功次数。
        • 然后将解层层返回。
      • 如果递归失败 (没找到解):
        • 撤销赋值和推理。
        • 继续尝试var的下一个值。
    5. 记录失败:
      • 如果变量var的所有值都尝试完毕,仍然没有找到解,这意味着变量var在当前搜索路径下是导致失败的“罪魁祸首”。
      • 记录这个错误方法并记录错误次数。
      • 然后执行回溯,返回到上一层。
    6. 循环与学习:整个搜索过程就在“决策 -> 尝试 -> 记录成败 -> 调整决策”的循环中不断进行,策略本身也随之智能调整。
class AdaptiveOrdering:
    def __init__(self):
        self.variable_failure_count = {}
        self.value_success_count = {}
    
    def select_variable(self, csp, assignment):
        """Select variable based on historical failure count"""
        unassigned = [var for var in csp.variables 
                      if var not in assignment]
        
        def score(var):
            domain_size = len(csp.current_domain(var))
            failure_weight = self.variable_failure_count.get(var, 0)
            return domain_size + 0.1 * failure_weight
        
        return min(unassigned, key=score)
    
    def order_values(self, var, csp, assignment):
        """Order values based on historical success rate"""
        values = list(csp.current_domain(var))
        
        def success_score(value):
            return self.value_success_count.get((var, value), 0)
        
        return sorted(values, key=success_score, reverse=True)
    
    def record_failure(self, var):
        """Record failure caused by variable"""
        self.variable_failure_count[var] = \
            self.variable_failure_count.get(var, 0) + 1
    
    def record_success(self, var, value):
        """Record successful variable-value pair"""
        self.value_success_count[(var, value)] = \
            self.value_success_count.get((var, value), 0) + 1