СТАТЬЯ
Проблемы ограничения-удовлетворения в Python
Из Классические проблемы информатики в Python Дэвида Копека
___________________________________________________________________
Получите скидку 42% на Классические задачи информатики на Python. Просто введите fcckopec2 при оформлении заказа на manning.com.
___________________________________________________________________
Большое количество проблем, которые решают вычислительные инструменты, можно в широком смысле отнести к категории задач удовлетворения ограничений (CSP). CSP состоят из переменных с возможными значениями, которые попадают в диапазоны, известные как домены. Ограничения между переменными должны быть соблюдены, чтобы проблемы удовлетворения ограничений были решены. Эти три основные концепции - переменные, области и ограничения - просты для понимания, и их общность лежит в основе широкой применимости решения проблем удовлетворения ограничений.
Рассмотрим пример. Предположим, вы пытаетесь назначить встречу для Джо, Мэри и Сью на пятницу. Сью должна присутствовать на встрече хотя бы с одним человеком. В этой задаче планирования три человека - Джо, Мэри и Сью - являются переменными. Доменом для каждой переменной могут быть соответствующие часы доступности. Например, переменная Mary имеет домен 14:00, 15:00 и 16:00. Эта проблема также имеет два ограничения. Одним из ограничений является то, что Сью должна быть на встрече. Во-вторых, на собрании должны присутствовать как минимум два человека. Средство решения проблемы удовлетворения ограничений предоставляется с тремя переменными, тремя областями и двумя ограничениями, и оно решает проблему, не требуя от пользователя объяснения как. Рисунок 1 иллюстрирует этот пример.
В языках программирования, таких как Prolog и Picat, есть встроенные средства для решения проблем удовлетворения ограничений. Обычный метод на других языках - создание инфраструктуры, которая включает поиск с возвратом и несколько эвристик для повышения производительности этого поиска. В этой статье мы сначала создадим структуру для CSP, которая решит их, используя простой рекурсивный поиск с возвратом. Затем мы воспользуемся фреймворком для решения нескольких различных примеров задач.
Построение структуры проблемы удовлетворения ограничений
Ограничения определяются с помощью класса Constraint. Каждый Constraint состоит из variables, которое он ограничивает, и метода, который проверяет, соответствует ли он satisfied(). Определение того, удовлетворяется ли ограничение, является основной логикой, которая входит в определение конкретной проблемы удовлетворения ограничений. Реализация по умолчанию должна быть переопределена, потому что мы определяем наш Constraint класс как абстрактный базовый класс. Абстрактные базовые классы не предназначены для создания экземпляров; используются только подклассы, которые переопределяют и реализуют свои @abstractmethod.
ПРИМЕЧАНИЕ
Код в этой статье широко использует подсказки типов, существующие в Python 3.7. Если вы не видели подсказок по типу до ознакомления с официальной документацией Python по адресу https://docs.python.org/3/library/typing.html. Кроме того, в приложении C Классические задачи информатики в Python есть подсказки по типу. Наконец, вы можете найти весь исходный код из этой статьи в Интернете по адресу https://github.com/davecom/ClassicComputerScienceProblemsInPython/tree/master/Chapter3
Листинг 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 реализованы через абстрактные базовые классы. Общий совет - не использовать их в собственном коде, если вы не уверены, что строите каркас, на котором будут строить другие, а не только иерархию классов внутреннего использования. Для получения дополнительной информации см. Главу 11 книги Fluent Python Лучано Рамальо.
Центральным элементом нашей структуры удовлетворения ограничений является класс CSP. CSP - это точка сбора переменных, областей и ограничений. Что касается подсказок типа, он использует универсальные шаблоны, чтобы сделать себя достаточно гибким для работы с любыми типами переменных и значений домена (V ключей и D значений домена). В CSP определения коллекций variables, domains и constraints относятся к ожидаемым вами типам. Коллекция variables - это list переменных, domains - это dict сопоставление переменных со списками возможных значений (домены этих переменных), а constraints - это dict, который сопоставляет каждую переменную с list ограничениями, наложенными на нее.
Листинг 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__() создает constraints dict. Метод add_constraint() просматривает все переменные, затронутые данным ограничением, и добавляет себя к сопоставлению constraints для каждой из них. Оба метода имеют базовую проверку ошибок и вызывают исключение, когда variable отсутствует домен или constraint находится в несуществующей переменной.
Как мы узнаем, удовлетворяет ли данная конфигурация переменных и выбранные значения домена ограничениям? Мы будем называть такую конфигурацию «заданием». Нам нужна функция, которая проверяет каждое ограничение для данной переменной на соответствие назначению, чтобы увидеть, работает ли значение переменной в назначении для ограничений. Здесь мы реализуем функцию consistent() как метод на CSP.
Листинг 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.
Эта структура удовлетворения ограничений использует простой поиск с возвратом для поиска решений проблем. Возврат - это идея, что, наткнувшись на стену в поиске, вы возвращаетесь к последней известной точке, где вы приняли решение до стены, и выбираете другой путь. Поиск с возвратом, реализованный в следующей backtracking_search() функции, является разновидностью рекурсивного поиска в глубину. Эта функция добавлена как метод к классу CSP.
Листинг 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
Давайте пройдемся по backtrackingSearch() строка за строкой.
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]
Чтобы выбрать новую переменную, предметную область которой мы можем исследовать, мы просматриваем все переменные и находим первую, не имеющую назначения. Чтобы сделать это, мы создаем 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 # no solution
Наконец, если мы просмотрели все возможные значения домена для конкретной переменной и не нашли решения, использующего существующий набор назначений, мы возвращаем None, что означает отсутствие решения. Это приводит к обратному отслеживанию цепочки рекурсии до точки, где могло быть выполнено другое предыдущее присвоение.
Проблема раскраски карты Австралии
Представьте, что у вас есть карта Австралии, которую вы хотите раскрасить по штатам / территориям (которые мы все вместе называем «регионами»). Никакие два соседних региона не должны иметь одинаковый цвет. Можно ли раскрасить регионы всего тремя разными цветами?
Ответ положительный. Попробуйте сами (проще всего распечатать карту Австралии с белым фоном). Как люди, мы можем быстро найти решение путем проверки и небольшого количества проб и ошибок. Это тривиальная проблема и отличная первая проблема для нашего средства решения проблем удовлетворения ограничений с возвратом. Проблема проиллюстрирована на рисунке 2.
Чтобы смоделировать проблему как CSP, нам нужно определить переменные, области и ограничения. Переменные - это семь регионов Австралии (по крайней мере, семь, которыми мы ограничимся): Западная Австралия; Северная территория; Южная Австралия; Квинсленд; Новый Южный Уэльс; Виктория; и Тасмания. В нашем CSP их можно смоделировать с помощью строк. Область каждой переменной - это три разных цвета, которые могут быть назначены (мы будем использовать красный, зеленый и синий). Ограничения - это сложная часть. Никакие две соседние области не могут быть окрашены в один цвет, и наши ограничения зависят от того, какие области граничат друг с другом. Мы можем использовать бинарные ограничения (ограничения между двумя переменными). Каждые два региона, у которых есть общая граница, также имеют двоичное ограничение, указывающее, что им нельзя присвоить один и тот же цвет.
Чтобы реализовать эти двоичные ограничения в коде, нам нужно создать подкласс класса Constraint. Подкласс MapColoringConstraint принимает две переменные в своем конструкторе (следовательно, является двоичным ограничением): две области, которые имеют общую границу. Его переопределенный satisfied() метод проверяет, имеют ли обе области значение домена (цвет), назначенное им - если какой-либо из них нет, ограничение тривиально удовлетворяется до тех пор, пока они не сделают это (не может быть конфликта, если у кого-то еще нет цвет). Затем он проверяет, назначен ли двум областям один и тот же цвет (очевидно, существует конфликт, то есть ограничение не выполняется, когда они одинаковы).
Класс представлен здесь полностью. MapColoringConstraint не является универсальным с точки зрения подсказки типов, но он является подклассом параметризованной версии универсального класса Constraint, который указывает, что и переменные, и домены относятся к типу str.
Листинг 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 заключается в заполнении областей и переменных, а затем добавлении ограничений.
Листинг 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() вызывается, чтобы найти решение.
Листинг 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'}
Проблема восьми ферзей
Шахматная доска представляет собой сетку квадратов восемь на восемь. Ферзь - это шахматная фигура, которая может перемещаться по шахматной доске на любое количество квадратов по любой строке, столбцу или диагонали. Ферзь атакует другую фигуру, если за один ход он может переместиться на поле, на котором находится фигура, не перепрыгивая через любую другую фигуру. Если другая фигура находится в поле зрения ферзя, то она атакует ее). Задача восьми ферзей ставит вопрос о том, как восемь ферзей могут быть размещены на шахматной доске, чтобы ни один ферзь не атаковал другого ферзя. Проблема проиллюстрирована на рисунке 3.
Чтобы представить квадраты на шахматной доске, мы назначим каждому целочисленную строку и целочисленный столбец. Мы можем гарантировать, что каждая из восьми ферзей не находится в одном столбце, последовательно назначив им столбцы с 1 по 8. Переменными в нашей задаче удовлетворения ограничений является столбец рассматриваемой ферзя. Домены могут быть возможными строками (снова с 1 по 8). В следующем листинге кода мы переходим к концу нашего файла, где определяем эти переменные и домены.
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)
Чтобы решить эту проблему, нам нужно ограничение, которое проверяет, находятся ли какие-либо две ферзя в одной строке или на одной диагонали (для начала всем им были назначены разные последовательные столбцы). Проверка одной и той же строки тривиальна, но проверка той же диагонали требует немного математики. Если любые две ферзя находятся на одной диагонали, разница между их рядами такая же, как и между их столбцами. Вы видите, где эти проверки проходят в QueensConstraint? Обратите внимание, что теперь мы возвращаемся к началу исходного файла и вводим следующий код.
Продолжение листинга 9 queens.py
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: List[int] = columns
def satisfied(self, assignment: Dict[int, int]) -> bool:
for q1c, q1r in assignment.items(): # q1c = queen 1 column, q1r = queen 1 row
for q2c in range(q1c + 1, len(self.columns) + 1): # q2c = queen 2 column
if q2c in assignment:
q2r: int = assignment[q2c] # q2r = queen 2 row
if q1r == q2r: # same row?
return False
if abs(q1r - q2r) == abs(q1c - q2c): # same diagonal?
return False
return True # no conflict
Добавьте ограничение и запустите поиск, и мы вернемся в конец файла.
Продолжение листинга 10 queens.py
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}
ОТПРАВИТЬ + БОЛЬШЕ = ДЕНЬГИ
ОТПРАВИТЬ + БОЛЬШЕ = ДЕНЬГИ - это криптарифметическая головоломка, то есть поиск цифр, которые заменяют буквы, чтобы математическое утверждение было верным. Каждая буква в задаче представляет собой одну цифру (0–9). Две буквы не могут представлять одну и ту же цифру. Если буква повторяется, это означает, что в решении повторяется цифра.
Чтобы решить эту головоломку вручную, нужно выстроить слова в ряд.
SEND +MORE =MONEY
Ее можно решить вручную, с помощью некоторой алгебры и интуиции, но простая компьютерная программа может решить ее быстрее путем перебора множества возможных решений. Представим ОТПРАВИТЬ + БОЛЬШЕ = ДЕНЬГИ как проблему удовлетворения ограничений.
Листинг 11 send_more_money.py
from csp import Constraint, CSP
from typing import Dict, List, Optional
class SendMoreMoneyConstraint(Constraint[str, int]):
def __init__(self, letters: List[str]) -> None:
super().__init__(letters)
self.letters: List[str] = letters
def satisfied(self, assignment: Dict[str, int]) -> bool:
# if there are duplicate values then it's not a solution
if len(set(assignment.values())) < len(assignment):
return False
# if all variables have been assigned, check if it adds correctly
if len(assignment) == len(self.letters):
s: int = assignment["S"]
e: int = assignment["E"]
n: int = assignment["N"]
d: int = assignment["D"]
m: int = assignment["M"]
o: int = assignment["O"]
r: int = assignment["R"]
y: int = assignment["Y"]
send: int = s * 1000 + e * 100 + n * 10 + d
more: int = m * 1000 + o * 100 + r * 10 + e
money: int = m * 10000 + o * 1000 + n * 100 + e * 10 + y
return send + more == money
return True # no conflict
satisfied() метод SendMoreMoneyConstraint делает несколько вещей. Во-первых, он проверяет, есть ли какие-либо буквы, представляющие одни и те же цифры. Если да, то это недопустимое решение и возвращает False. Затем он проверяет, все ли буквы присвоены. Если да, он проверяет, правильна ли формула (ОТПРАВИТЬ + БОЛЬШЕ = ДЕНЬГИ) с заданным назначением. Если это так, решение было найдено, и оно возвращает True. В противном случае возвращается False. Наконец, если все буквы еще не назначены, возвращается True. Это необходимо для того, чтобы работа над частичным решением продолжалась.
Давай попробуем запустить его:
Листинг 12 send_more_money.py (продолжение)
if __name__ == "__main__":
letters: List[str] = ["S", "E", "N", "D", "M", "O", "R", "Y"]
possible_digits: Dict[str, List[int]] = {}
for letter in letters:
possible_digits[letter] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
possible_digits["M"] = [1] # so we don't get answers starting with a 0
csp: CSP[str, int] = CSP(letters, possible_digits)
csp.add_constraint(SendMoreMoneyConstraint(letters))
solution: Optional[Dict[str, int]] = csp.backtracking_search()
if solution is None:
print("No solution found!")
else:
print(solution)
Обратите внимание, что мы заранее присвоили ответ букве M. Это было сделано для того, чтобы ответ не содержал нуля для M, потому что в нашем ограничении нет понятия о том, что число не может начинаться с нуля. Не стесняйтесь попробовать это без заранее заданного ответа.
Решение должно выглядеть примерно так:
{'S': 9, 'E': 5, 'N': 6, 'D': 7, 'M': 1, 'O': 0, 'R': 8, 'Y': 2}
Внешний вид печатной платы
Производителю необходимо установить определенные прямоугольные микросхемы на прямоугольную печатную плату. Задача заключается в следующем: «Как несколько прямоугольников разного размера могут плотно уместиться внутри другого прямоугольника?» Решатель проблем с удовлетворением ограничений может найти решение. Проблема проиллюстрирована на рисунке 4.
Реальные приложения
Как упоминалось во введении к этой статье, при составлении расписания обычно используются средства решения проблем удовлетворения ограничений. На встрече должны присутствовать несколько человек, и они переменные. Домены состоят из времени работы в их календарях. Ограничения могут включать в себя то, какие комбинации людей требуются на собрании.
При планировании движения также используются средства решения проблем удовлетворения ограничений. Представьте себе манипулятор, который должен поместиться внутри трубы. Он имеет ограничения (стенки трубы), переменные (суставы) и области (возможные движения суставов).
Приложения в вычислительной биологии многочисленны. Вы можете представить себе ограничения между молекулами, необходимые для химической реакции. И, как это часто бывает с ИИ, в играх есть приложения. Написание решателя судоку - одно из следующих упражнений, но многие логические головоломки можно решить, используя решение задач удовлетворения ограничений.
Упражнения
- Создайте средство решения проблем с компоновкой печатной платы, как описано в статье, если вы еще этого не сделали.
- Создайте программу, которая может решать задачи судоку, используя структуру задачи удовлетворения ограничений, описанную в этой статье.
Это все для этой статьи. Если вы хотите узнать больше о книге, посмотрите ее в liveBook здесь и посмотрите эту колоду слайдов.
Об авторе:
Дэвид Копек, доцент кафедры компьютерных наук и инноваций в Champlain College, автор книги Dart for Absolute Beginners и Классические задачи информатики в Swift. Дэвид - опытный разработчик программного обеспечения и активный участник открытого исходного кода.
Первоначально опубликовано на freecontent.manning.com.
