На этом шаге мы рассмотрим построение такой структуры.
Определим ограничения посредством класса Constraint. Каждое ограничение Constraint состоит из переменных variables, которые оно ограничивает, и метода satisfied(), который проверяет, выполняется ли оно. Определение того, выполняется ли ограничение, является основной логикой, входящей в определение конкретной задачи с ограничениями. Реализацию по умолчанию нужно переопределить. Именно так и должно быть, потому что мы определяем Constraint как абстрактный базовый класс. Абстрактные базовые классы не предназначены для реализации. Только их подклассы, которые переопределяют и реализуют свои абстрактные методы @abstractmethod, предназначены для действительного использования (файл csp.py).
from typing import Generic, TypeVar, Dict, List, Optional from abc import ABC, abstractmethod V = TypeVar('V') # Тип variable для переменной D = TypeVar('D') # тип dоmain для области определения # Базовый класс для всех ограничений 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: ...
Абстрактные базовые классы играют роль шаблонов в иерархии классов.
В других языках, таких как C++, они получили более широкое распространение, чем в Python, как свойство, ориентированное на пользователя.
В сущности, они появились в Python примерно на середине жизненного пути языка. При этом многие классы коллекций из стандартной библиотеки
Python реализованы с помощью абстрактных базовых классов. Общий совет: не используйте их в своем коде, если не уверены, что строите структуру,
на основе которой будут создаваться другие классы, а не просто иерархию классов для внутреннего применения.
Центральным элементом нашей структуры соответствия ограничениям будет класс с названием CSP (файл csp.py). CSP - это место, где собраны все переменные, области определения и ограничения. С точки зрения подсказок типов класс CSP использует универсальные средства, чтобы быть достаточно гибким, работать с любыми значениями переменных и областей определения (где V - это значения переменных, a D - областей определения). В CSP коллекции variables, domains и constraints имеют ожидаемые типы. Коллекция variables - это list для переменных, domains - dict с соответствием переменных спискам возможных значений (областям определения этих переменных), a constraints - dict, где каждой переменной соответствует list наложенных на нее ограничений.
# Задача с ограничениями состоит из переменных типа V, # которые имеют диапазоны значений, известные как области определения, # типа D и ограничений, которые определяют, является ли допустимым # выбор данной области определения для данной переменной class CSP(Generic[V, D]): def __init__(self, variables: List[V], domains: Dict[V, List[D]]) -> None: self.variables: List[V] = variables # переменные, которые будут ограничены self.domains: Dict[V, List[D]] = 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("Каждой переменной должен быть назначен домен.") def add_constraint(self, constraint: Constraint[V, D]) -> None: for variable in constraint.variables: if variable not in self.variables: raise LookupError("Переменная в ограничении, а не в CSP") else: self.constraints[variable].append(constraint)
Инициализатор __init__() создает constraints dict. Метод add_constraint() просматривает все переменные, к которым относится данное ограничение, и добавляет себя в соответствие constraints для каждой такой переменной. Оба метода имеют простейшую проверку ошибок и вызывают исключение, если variable отсутствует в области определения или существует constraint для несуществующей переменной.
Как узнать, соответствует ли данная конфигурация переменных и выбранных значений области определения заданным ограничениям? Мы будем называть такую заданную конфигурацию присваиванием. Нам нужна функция, которая проверяла бы каждое ограничение для заданной переменной по отношению к присваиванию, чтобы увидеть, удовлетворяет ли значение переменной в присваивании этим ограничениям. В тексте ниже (файл csp.py) реализована функция constant() как метод класса CSP.
# Проверяем, соответствует ли присваивание значения, проверяя все ограничения
# для данной переменной
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
Метод constant() перебирает все ограничения для данной переменной (это всегда будет переменная, только что добавленная в присваивание) и проверяет, выполняется ли ограничение, учитывая новое присваивание. Если присваивание удовлетворяет всем ограничениям, возвращается True. Если какое-либо ограничение, наложенное на переменную, не выполняется, возвращается значение False.
Для поиска решения задачи в такой структуре выполнения ограничений будет использоваться простой поиск с возвратами. Возвраты - это подход, при котором, если поиск зашел в тупик, мы возвращаемся к последней известной точке, где было принято решение, перед тем как зайти в тупик, и выбираем другой путь. Если вам кажется, что это похоже на поиск в глубину из 24 шага, то вы правы. Поиск с возвратом, реализованный в следующей функции backtracking_search(), является своего рода рекурсивным поиском в глубину, в котором объединены ранее изложенные идеи. Эта функция добавляется в качестве метода в класс CSP (файл csp.py).
def backtracking_search(self, assignment: Dict[V, D] = {}) -> Optional[Dict[V, D]]:
# присваивание завершено, если существует присваивание
# для каждой переменной (базовый случай)
if len(assignment) == len(self.variables):
return assignment
# получить все переменные из CSP, но не из присваивания
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 # нет решения
Исследуем backtracking_search() построчно.
if len(assignment) == len(self.variables):
return assignment
Базовый случай для рекурсивного поиска означает, что нужно найти правильное присваивание для каждой переменной. Сделав это, мы возвращаем первый валидный экземпляр решения (и не продолжаем поиск).
unassigned: List[V] = [v for v in self.variables if v not in assignment]
Чтобы выбрать новую переменную, область определения которой будем исследовать, мы просто просматриваем все переменные и находим первую, которая не имеет присваивания. Для этого создаем список list переменных в self.variables, но не в assignment через генератор списков и называем его 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 # нет решения
Наконец, если мы рассмотрели все возможные значения области определения для конкретной переменной и не обнаружили решения, в котором использовался бы существующий набор назначений, то возвращаем None, что указывает на отсутствие решения. В результате по цепочке рекурсии будет выполнен возврат к точке, в которой могло быть принято другое предварительное присваивание.
На следующем шаге мы рассмотрим задачу раскраски карты Австралии.
