【人工智能】CSP问题全解全练

港控/mmm° 2022-09-14 02:01 188阅读 0赞

### 【人工智能】CSP问题全解全练 ###

*  例题
 *   *  构建 CSP 框架
     *  地图上色问题
     *  国际象棋的八王后问题
     *  上课问题
 *  参考文献

![在这里插入图片描述][7deb974002d54c3d8d47488482c31202.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5ouzTWFyeA_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5ouzTWFyeA_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5ouzTWFyeA_size_20_color_FFFFFF_t_70_g_se_x_16 2]

# 例题 #

由计算工具解决的很大一部分问题都可以归类为约束满足问题（CSPs, constraint-satisfaction problems）。CSP 一般包含三个基本概念：变量（variables）、域（domains）和约束条件（constraints）。比如需要在星期五为 Joe、Mary、Sue 三个人安排一场会议，要求 Sue 必须和另外的至少一个人同时在场。针对此问题：  
Joe、Mary、Sue 三个人即为变量（variables）  
每个人（变量）各自空闲的时间点即为对应的域（domains）。比如变量 Mary 在下午 2 点和 3 点的时候有空，这两个时间点即为变量 Mary 对应的域  
约束条件（constraints）有两点：Sue 必须在场；除 Sue 以外至少还需要另一人到场  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5ouzTWFyeA_size_20_color_FFFFFF_t_70_g_se_x_16 3]

## 构建 CSP 框架 ##

约束条件通过 Constraint 类实现。该类中包含被约束的变量以及测试其是否满足约束的 satisfied() 方法。确定是否满足约束条件是针对某个特定的 CSP 的核心逻辑，该 satisfied() 方法必须为抽象方法，由子类覆盖后发挥实际作用，以满足不同问题的不同约束条件。

# 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
    
    class Constraint(Generic[V, D], ABC):
        def __init__(self, variables: List[V]) -> None:
            self.variables = variables
    
        @abstractmethod
        def satisfied(self, assignment: Dict[V, D]) -> bool:
            pass

约束满足框架的核心部分代码是 CSP 类，该类集中处理变量、域和约束条件。CSP 的类型使用 Generic，目的是使其足够灵活，能够处理各种类型的 variables 和 domains。其中 variables 是 list 类型，domains 是由 variable 和对应的 list （所有可能的值）关联成的 dict 类型，constraints 则是由 variable 和对应的 list（约束条件列表）关联成的 dict 类型。

**init**() 初始化方法会创建 constraints 字典，将 variables 中的值作为键，每个键关联一个空列表。add\_constraint() 方法遍历 variables 中的值（同时也是 constraints 中的键），将对应的 constraint 添加到 constraints 字典的该 variable 键关联的列表中。  
从而完成对 variables、domains、constraints 三类数据的初始化。\`\`\`

# csp.py
    class CSP(Generic[V, D]):
        def __init__(self, variables: List[V], domains: Dict[V, List[D]]) -> None:
            self.variables = variables
            self.domains = domains
            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)

consistent() 方法用于检查给定的 variable 对应的每一个约束条件是否一一符合当前预设的方案。这个临时的方案用 assignment 表示。  
即先有某个 variable，然后为其选择对应的 domain 中的任意一个值作为临时的 assignment，再检查该 assignment 是否符合对应的 variable 关联的所有约束条件。

# csp.py
    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

约束满足框架还需要一个简单的 backtracking 搜索用于查找问题的解决方案。Backtracking 意味着一旦在搜索路径的某个节点上终止，则返回到上一个已知的搜索节点，选择另一条搜索路径。有点类似于深度优先搜索（DFS, depth-first search）。

def backtracking_search(self, assignment: Dict[V, D] = {}) -> Optional[Dict[V, D]]:
        # assignment is complete if every variable is assigned
        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]
        first: V = unassigned[0]
        for value in self.domains[first]:
            local_assignment = assignment.copy()
            local_assignment[first] = value
            if self.consistent(first, local_assignment):
                result: Optional[Dict[V, D]] = self.backtracking_search(local_assignment)
                if result is not None:
                    return result
        return None

逐条分析以上代码：

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

上面的 backtracking 搜索采用了递归的形式，此 if 语句则提供了一种递归的终止条件。即当所有 variable 都被赋予了合法的值时，意味着其中一种搭配方案已被找到，则停止进一步的搜索，返回该搭配方案。

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

取出 variables 中第一个还未被赋值（未做选择）的 variable，作为下一步中进行赋值（做决定）和约束条件测试的对象。

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

为前面未赋值的某个 variable “做决定”。将对应的 domain 中所有存在的值依次赋值给该 variable，形成一个新的方案（local\_assignment）。若该方案符合所有的约束条件（通过 consistent() 方法检测），则借助递归进行下一轮对另一个 variable 的赋值，直到触发终止条件（所有 variable 都被赋值）。

return None

若针对某个特定的 variable，已经检查完 domain 中包含的所有可能的值，仍没有找到符合要求的方案，则返回 None 表示没有解决。这会导致 backtracking 搜索结束本轮 for 循环，返回到递归的上一层中的 for 循环，尝试为上一步中已赋值的 variable 做出不同的决定，并继续递归（或回溯）下去。

## 地图上色问题 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5ouzTWFyeA_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
地图上色问题的一种解决方案  
借助前面构建的约束符合框架，实现代码如下：

# map_coloring.py
    from csp import Constraint, CSP
    from typing import Dict, List, Optional
    
    class MapColoringConstraint(Constraint[str, str]):
        def __init__(self, place1: str, place2: str) -> None:
            super().__init__([place1, place2])
            self.place1 = place1
            self.place2 = place2
    
        def satisfied(self, assignment: Dict[str, str]) -> bool:
            # if either place is not in the assignment, then it is not
            # yet possible for their colors to be conflicting
            if self.place1 not in assignment or self.place2 not in assignment:
                return True
            # check the color assigned to place1 is not the same as the
            # color assigned to place2
            return assignment[self.place1] != assignment[self.place2]
    
    
    if __name__ == "__main__":
        variables: List[str] = ["Western Australia", "Northern Territory", "South Australia",
                                "Queensland", "New South Wales", "Victoria", "Tasmania"]
        domains: Dict[str, List[str]] = {
        }
        for variable in variables:
            domains[variable] = ["red", "green", "blue"]
        csp: CSP[str, str] = CSP(variables, domains)
        csp.add_constraint(MapColoringConstraint("Western Australia", "Northern Territory"))
        csp.add_constraint(MapColoringConstraint("Western Australia", "South Australia"))
        csp.add_constraint(MapColoringConstraint("South Australia", "Northern Territory"))
        csp.add_constraint(MapColoringConstraint("Queensland", "Northern Territory"))
        csp.add_constraint(MapColoringConstraint("Queensland", "South Australia"))
        csp.add_constraint(MapColoringConstraint("Queensland", "New South Wales"))
        csp.add_constraint(MapColoringConstraint("New South Wales", "South Australia"))
        csp.add_constraint(MapColoringConstraint("Victoria", "South Australia"))
        csp.add_constraint(MapColoringConstraint("Victoria", "New South Wales"))
        csp.add_constraint(MapColoringConstraint("Victoria", "Tasmania"))
    
        solution: Optional[Dict[str, str]] = csp.backtracking_search()
        if solution is None:
            print("No solution found")
        else:
            print(solution)
    
    # => {'Western Australia': 'red', 'Northern Territory': 'green', 'South
    # Australia': 'blue', 'Queensland': 'red', 'New South Wales': 'green',
    # 'Victoria': 'red', 'Tasmania': 'green'}

简单梳理一下程序逻辑：

在上述 CSP 中，地图中的 7 个州即为 variables（为方便，以 a、b、c、d、e、f、g 代替）  
variables = \[‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’\]

每个州都可以涂成红绿蓝三种颜色（假设用 1、2、3 指代）中的任何一种，各 variable 对应的所有颜色即组成对应 variable 的 domain：  
domains = \{‘a’: \[1, 2, 3\], ‘b’: \[1, 2, 3\], ‘c’: \[1, 2, 3\], ‘d’: \[1, 2, 3\], ‘e’: \[1, 2, 3\], ‘f’: \[1, 2, 3\], ‘g’: \[1, 2, 3\]\}

constraints 的逻辑在 MapColoringConstraints 类中实现，即已经涂色的相邻的两个州色彩须不一致。比如 a 与 b 相邻，则该 constraint 的表示如下：  
MapColoringConstraint(‘a’, ‘b’)  
而所有的 constraints 都会关联到对应的以 variable 为键的字典中。即若 a 同时与 b 和 c 相邻，则变量 a 的 constraints 表示为：  
\{‘a’: \[MapColoringConstraint(‘a’, ‘b’), MapColoringConstraint(‘a’, ‘c’)\]\}

backtrack\_search() 方法的执行流程为：

在 variables 中取第一个未被赋值（涂色）的 variable，为其赋予对应 domain 中的某个数值作为临时方案  
用该 variable 对应的所有 constraints 测试上述临时方案的可行性。若符合要求，则借助递归开启下一轮循环，继续为另一个未被赋值（涂色）的 variable 赋值  
若不符合要求，则继续本轮循环，为本 variable 赋予 domain 中的另一个值  
若对应 domain 中的所有值赋予 variable 后都不能符合约束要求，则返回 None。本轮循环结束，回到递归的上一轮继续循环，为上一轮中已赋值的 variable 赋予不同的值，延续递归操作  
若所有 variable 都已被赋值，则返回 variable 及其对应的值作为最终的解决方案；若所有循环（递归/回溯）结束，返回结果最终为 None，则表示无法找到合理的解决方案

## 国际象棋的八王后问题 ##

国际象棋的棋盘由 8x8 的方格组成，棋子落于方格上。而棋子王后能够吃掉处于同一行、同一列、同一斜线上的任何一个敌方棋子。  
八王后问题是指需要将 8 个王后放置到国际象棋棋盘上且彼此之间不会产生冲突（即不会有任意两枚棋子位于同一行、同一列或者同一斜线上）。

其中一种可能的解决方案如下图：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5ouzTWFyeA_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
实现代码如下：

from csp import Constraint, CSP
    from typing import Dict, List, Optional
    
    class QueensConstraint(Constraint[int, int]):
        def __init__(self, columns: List[int]) -> None:
            super().__init__(columns)
            self.columns = columns
    
        def satisfied(self, assignment: Dict[int, int]) -> bool:
            # q1c = queen 1 column, q1r = queen 1 row
            for q1c, q1r in assignment.items():
                # q2c = queen 2 column
                for q2c in range(q1c + 1, len(self.columns) + 1):
                    if q2c in assignment:
                        q2r = assignment[q2c]
                        if q1r == q2r:  # same row?
                            return False
                        if abs(q1r - q2r) == abs(q1c - q2c):  # same diagonal?
                            return False
            return True
    
    
    if __name__ == "__main__":
        columns: List[int] = [1, 2, 3, 4, 5, 6, 7, 8]
        rows: Dict[int, List[int]] = {
        }
        for column in columns:
            rows[column] = [1, 2, 3, 4, 5, 6, 7, 8]
        csp: CSP[int, int] = CSP(columns, rows)
    
        csp.add_constraint(QueensConstraint(columns))
        solution: Optional[Dict[int, int]] = csp.backtracking_search()
        if solution is None:
            print("No solution found!")
        else:
            print(solution)
    
    # => {1: 1, 2: 5, 3: 8, 4: 6, 5: 3, 6: 7, 7: 2, 8: 4}

简单解释下 satisfied() 方法中的两个 for 循环。assignment 采用类似 \{1: 1, 2: 5, 3: 8, 4: 6, 5: 3, 6: 7, 7: 2, 8: 4\} 的字典类型（一开始会短一些），上述两个 for 循环的作用在于，先以棋盘上的第一列为标准，若第一列与剩余的几列不存在冲突，则去掉第一列，再比较第二列与剩余的几列是否存在冲突，以此类推。一旦出现任何冲突，则返回 False。

## 上课问题 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5ouzTWFyeA_size_20_color_FFFFFF_t_70_g_se_x_16 6]

# map_coloring.py
    from csp import Constraint, CSP
    from typing import Dict, List, Optional
    
    class MapColoringConstraint(Constraint[str, str]):
        def __init__(self, place1: str, place2: str) -> None:
            super().__init__([place1, place2])
            self.place1 = place1
            self.place2 = place2
    
        def satisfied(self, assignment: Dict[str, str]) -> bool:
            # if either place is not in the assignment, then it is not
            # yet possible for their colors to be conflicting
            if self.place1 not in assignment or self.place2 not in assignment:
                return True
            # check the color assigned to place1 is not the same as the
            # color assigned to place2
            return assignment[self.place1] != assignment[self.place2]
    
    
    if __name__ == "__main__":
        variables: List[str] = ["计算机编程简介", "人工智能导论", "软件工程",
                                "计算机视觉", "机器学习"]
    
        domains: Dict[str, List[str]] = {
        }
        for variable in variables:
            domains[variable] = ["A", "B", "C"]
    
        domains: Dict[str, List[str]] = {
        '计算机编程简介': ["A","C"], '人工智能导论': ["A"], '软件工程': ["B", "C"], '计算机视觉': ["B", "C"], '机器学习': ["A", "B"]}
        csp: CSP[str, str] = CSP(variables, domains)
        csp.add_constraint(MapColoringConstraint("计算机编程简介", "人工智能导论"))
        csp.add_constraint(MapColoringConstraint("人工智能导论", "软件工程"))
        csp.add_constraint(MapColoringConstraint("人工智能导论", "计算机视觉"))
        csp.add_constraint(MapColoringConstraint("软件工程", "计算机视觉"))
    
    
        solution: Optional[Dict[str, str]] = csp.backtracking_search()
        if solution is None:
            print("No solution found")
        else:
            print(solution)
    
    
    # 变量："计算机编程简介", "人工智能导论", "软件工程","计算机视觉", "机器学习"
    # 值域："A", "B", "C"
    # 约束：csp.add_constraint(MapColoringConstraint("计算机编程简介", "人工智能导论"))
    #      csp.add_constraint(MapColoringConstraint("人工智能导论", "软件工程"))
    #      csp.add_constraint(MapColoringConstraint("人工智能导论", "计算机视觉"))
    #      csp.add_constraint(MapColoringConstraint("软件工程", "计算机视觉"))

# 参考文献 #

[人工智能第六章——约束满足问题（CSP）][CSP]  
[2021人工智能-6-约束满足问题][2021_-6-]

[7deb974002d54c3d8d47488482c31202.png]: /images/20220828/92826f5d6b934277927dbb50fce7f4f6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5ouzTWFyeA_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/59dd90c9dbde4ea99c9b631de05e83cf.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5ouzTWFyeA_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/834b79b5161944c9aa609b1c9d410d8d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5ouzTWFyeA_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/b64dddcf82764b26a46835f24d14eeb5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5ouzTWFyeA_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/76326cc817eb4d2ab3d9232fe06cf4a1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5ouzTWFyeA_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/d9a3a1a197224238be74994278cd12cb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5ouzTWFyeA_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/ca480f658c704005bd9b9f2b92b0e971.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5ouzTWFyeA_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/374c4e018d85493b890b88bbc8ee71fe.png
[CSP]: https://blog.csdn.net/weixin_39278265/article/details/80932277
[2021_-6-]: https://www.bilibili.com/video/BV1sp4y1t78J?from=search&seid=9724075300094039838&spm_id_from=333.337.0.0