02-构建约束满足问题的解决框架

3.1　构建约束满足问题的解决框架

约束将用 Constraint 类来定义。每个 Constraint 包括受其约束的变量 variables ，以及检查是否满足条件的 satisfied() 方法。确定是否满足约束是开始定义某个约束满足问题所需的主要逻辑。 satisfied() 的默认实现代码应该被重写（overridden），其实也必须如此，因为 Constraint 类将被定义为抽象基类。抽象基类本来就不是注定要被实例化的，只有重写并实现了 @abstractmethods 的抽象基类的子类才能用于实际应用。具体代码如代码清单3-1所示。

代码清单3-1　csp.py

from typing import Generic, TypeVar, Dict, List, Optional
from abc import ABC, abstractmethod
V = TypeVar('V') # variable type
D = TypeVar('D') # domain type
# Base class for all constraints
class Constraint(Generic[V, D], ABC):
    # The variables that the constraint is between
    def __init__(self, variables: List[V]) -> None:
        self.variables = variables
    # Must be overridden by subclasses
    @abstractmethod
    def satisfied(self, assignment: Dict[V, D]) -> bool:
        ...

提示 　 抽象基类在类的层次结构中充当着模板的作用。在其他语言（如C++）中，它们作为面向用户的特性，比在Python中应用更为普遍。实际上，抽象基类是在Python发展的中途才被引入Python的。话虽如此，Python标准库中的许多集合（collection）类都是通过抽象基类实现的。一般建议不要在自己的代码中使用抽象基类，除非确定要构建的框架不仅仅是供内部使用的类架构，而是要作为供其他人构建的基础。要获得更多信息，请参阅Luciano Ramalho的《流畅的Python》（Fluent Python）的第11章（O’Reilly，2015）。

该约束满足框架的核心将是一个名为 CSP 的类。 CSP 是变量、值域和约束的汇集点，其类型提示用到了泛型以使其保持足够的灵活性，从而能处理任意类型的变量和域值（键 V 和域值 D ）。在 CSP 中，集合 variables 、 domains 和 constraints 可以是你期望的任意类型。 variables 集合是变量的 list ， domains 是把变量映射为可取值的列表（这些变量的值域）的 dict 类型，而 constraints 则是把每个变量映射为其所受约束的 list 的 dict 类型。具体代码如代码清单3-2所示。

代码清单3-2　csp.py（续）

# A constraint satisfaction problem consists of variables of type V
# that have ranges of values known as domains of type D and constraints
# that determine whether a particular variable's domain selection is valid
class CSP(Generic[V, D]):
    def __init__(self, variables: List[V], domains: Dict[V, List[D]]) -> None:
        self.variables: List[V] = variables # variables to be constrained
        self.domains: Dict[V, List[D]] = domains # domain of each variable
        self.constraints: Dict[V, List[Constraint[V, D]]] = {}
        for variable in self.variables:
            self.constraints[variable] = []
            if variable not in self.domains:
                raise LookupError("Every variable should have a domain assigned to it.")
    def add_constraint(self, constraint: Constraint[V, D]) -> None:
        for variable in constraint.variables:
            if variable not in self.variables:
                 raise LookupError("Variable in constraint not in CSP")
            else:
                 self.constraints[variable].append(constraint)

__init__() 初始化方法中将会创建 dict 类型的 constraints 。 add_constraint() 方法会遍历给定约束涉及的所有变量，并将其这一约束添加到每个变量的 constraints 映射中去。这两个方法都带有一些基本的错误检查代码，如果 variables 缺少值域或者 constraints 用到了不存在的变量，都将会引发异常。

如何判断给定的变量配置和所选域值是否满足约束呢？这个给定的变量配置被称为“赋值”。我们需要一个函数能根据某种赋值检查给定变量的每个约束，以查看该赋值中的变量值是否满足约束。代码清单3-3中将实现 consistent() 函数，其为 CSP 的一个方法。

代码清单3-3　csp.py（续）

# Check if the value assignment is consistent by checking all constraints
# for the given variable against it
def consistent(self, variable: V, assignment: Dict[V, D]) -> bool:
    for constraint in self.constraints[variable]:
        if not constraint.satisfied(assignment):
            return False
    return True

consistent() 将遍历给定变量（一定是刚刚加入到赋值中的变量）的每个约束，并检查新的赋值是否满足约束。如果该赋值满足全部约束，则返回 True 。只要施加于变量的约束中有一条不满足，就返回 False 。

本约束满足框架将使用简单的回溯搜索来找到问题的解。回溯的思路如下：一旦在搜索中碰到障碍，就会回到碰到障碍之前最后一次做出判断的已知点，然后选择其他的一条路径。如果你觉得这看起来像是第 2 章中的深度优先搜索，那么你真是很敏锐。在代码清单 3-4 中， backtracking_search() 函数实现的回溯搜索正是一种递归式深度优先搜索，它结合了第1章和第2章中介绍的思路。该函数将作为方法加入 CSP 类。

代码清单3-4　csp.py（续）

def backtracking_search(self, assignment: Dict[V, D] = {}) -> Optional[Dict[V, D]]:
    # assignment is complete if every variable is assigned (our base case)
    if len(assignment) == len(self.variables):
        return assignment
    # get all variables in the CSP but not in the assignment
    unassigned: List[V] = [v for v in self.variables if v not in assignment]
    # get the every possible domain value of the first unassigned variable
    first: V = unassigned[0]
    for value in self.domains[first]:
        local_assignment = assignment.copy()
        local_assignment[first] = value
        # if we're still consistent, we recurse (continue)
        if self.consistent(first, local_assignment):
            result: Optional[Dict[V, D]] = self.backtracking_search(local_assignment)
            # if we didn't find the result, we will end up backtracking
            if result is not None:
                return result
    return None

下面来逐行过一遍 backtracking_search() 函数。

if len(assignment) == len(self.variables):
    return assignment

递归搜索的基线条件是为每个变量都找到满足条件的赋值，一旦找到就会返回满足条件的解的第一个实例，而不会继续搜索下去。

unassigned: List[V] = [v for v in self.variables if v not in assignment] first: V = unassigned[0]

为了选出一个新变量来探索其值域，只需遍历所有变量并找出第一个未赋值的变量。为此，我们用列表推导式为在 self.variables 中但不在 assignment 中的变量创建一个变量 list ，并将其命名为 unassigned ，然后取出 unassigned 中的第一个值。

for value in self.domains[first]:
    local_assignment = assignment.copy()
    local_assignment[first] = value 

我们尝试为该变量赋予所有可能的域值，每次只赋一个。新的赋值都存储在名为 local_assignment 的局部字典中。

if self.consistent(first, local_assignment):
    result: Optional[Dict[V, D]] = self.backtracking_search(local_assignment)
    if result is not None:
        return result

如果 local_assignment 中的新赋值满足所有约束（即 consistent() 检查的内容），我们就会用新赋值继续进行递归搜索。如果新赋值已涵盖了全体变量（基线条件），那么我们就会把新赋值返回到递归调用链中去。

    return None  # no solution

如果已经对某变量遍历了每一种可能的域值，并且用现有的一组赋值没有找到解，就返回 None ，表示该问题无解。这会导致递归调用链回溯到之前成功做出上一次赋值的位置。