03-澳大利亚地图着色问题

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

3.2　澳大利亚地图着色问题

请想象有一张澳大利亚地图，希望按州/属地（统称为“地区”）进行着色。不允许两个相邻的地区共用一种颜色。请问你能只用3种不同的颜色为所有地区进行着色吗？

答案是肯定的。不妨自行尝试一下。最简单的做法是打印一张白色背景的澳大利亚地图。人们可以通过检查和少量的反复试错来快速求解。对之前的回溯式约束满足问题求解程序而言，这只是一个小问题，拿来初试牛刀太合适不过了。该地图着色问题如图3-2所示。

图3-2　在澳大利亚地图着色问题的解里，不允许有相邻地区同色

要将地图着色问题建模为CSP，需要定义变量、值域和约束。变量是澳大利亚的7个地区（至少这里仅限于这7个地区）：Western Australia、Northern Territory、South Australia、Queensland、New South Wales、Victoria和Tasmania。在此CSP中可以用字符串进行建模。每个变量的值域是可供赋值的3种颜色，这里将用到红色、绿色和蓝色。约束是比较棘手的部分。由于不允许对两个相邻地区用相同颜色进行着色，因此约束将取决于有哪些地区是彼此相邻的。这里可以采用二元约束（两个变量间的约束）。共用边界的两个地区也将共用一条二元约束，表示不能给它们赋予相同的颜色。

要在代码中实现这些二元约束，需要子类化 Constraint 类。 MapColoringConstraint 子类的构造函数需要给出两个变量，即共用边界的两个地区，其重写的 satisfied() 方法将首先检查两个地区是否赋有域值（颜色）。如果其中任何一个地区都没有域值，那么在获得域值之前，约束都能轻松得以满足，因为如果其中一个地区还没有颜色，就不可能发生冲突。然后该方法将检查两个地区是否被赋予了相同的颜色。显然，如果颜色相同就存在冲突，意味着不满足约束。

代码清单3-5将给出完整的 MapColoringConstraint 类，其本身在类型提示方面不是泛型化的，但它是泛型类 Constraint 的参数化版本的子类，标明了变量和值域都是 str 类型。

代码清单3-5　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: str = place1
       self.place2: str = 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]

提示　有时会用 super() 调用超类的方法，但也可以使用类本身的名称来调用，正如 Constraint.__init__([place1, place2]) 。在处理多重继承时，这种用法特别有用，因为这样对于要调用哪个超类的方法非常明了。

现在对于地区之间的约束有实现方案了，因而用 CSP 求解程序表现澳大利亚地图着色问题就简单了，只需填入值域和变量，再添加约束即可。具体代码如代码清单3-6所示。

代码清单3-6　map_coloring.py（续）

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"))

最后，调用 backtracking_search() 求出一个解。具体代码如代码清单3-7所示。

代码清单3-7　map_coloring.py（续）

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'}

Previous 上一篇本节目录 Next 下一篇

03-澳大利亚地图着色问题

3.2 澳大利亚地图着色问题

3.2　澳大利亚地图着色问题