5 Удовл ограничений

1. Задачи удовлетворения ограничений (Constraint Satisfaction Problems)

Лекция №5
1

2. Constraint satisfaction problems (CSPs)

Стандартные задачи поиска:
Состояние является «черным ящиком» – каждая
структура данных должна быть обеспечена функцией
определения приемника, эвристической функцией и
способностью определения целевого состояния
CSP:
Состояние определятся переменными Xi с значениями
из области определения Di
Целевое состояние - это состояние, при котором всем
переменным присвоены значения, удовлетворяющие
ограничениями.
2

3. Пример: раскраска карты

Переменные WA, NT, Q, NSW, V, SA, T
Область значений Di = {red,green,blue}
Ограничения: соседние регионы должны быть разных цветов
e.g., WA ≠ NT, or (WA,NT) in {(red,green),(red,blue),(green,red),
(green,blue),(blue,red),(blue,green)}
3

4. Пример: раскраска карты

Решение, например, WA = red, NT = green,Q =
red,NSW = green,V = red,SA = blue,T = green
4

5. Граф ограничений

Граф ограничений: узлы – переменные, дуги –
ограничения.
5

6. Виды переменных в CSP

Дискретные переменные
Конечная область определения:
Бесконечная область определения:
▪ целые числа, строки и т.д.
▪ календарное планирование
▪ необходимы доп. ограничения, StartJob1 + 5 ≤ StartJob3
Непрерывные переменные
большинство задач реального мира
задачи линейного программирования
6

7. Виды ограничений

Унарные ограничивают значение одной
переменной, например, SA ≠ green
Бинарные ограничения связывают две
переменных, например, SA ≠ WA
Ограничения высокого порядка связывают более
двух переменных, например,
криптоарифметические головоломки
7

8. Стандартная формулировка

Начальное состояние: пустое присваивание { }
Функция определения приемника: значение может быть
присвоено любой переменной с неприсвоенным значением,
при условии, что переменная не будет конфликтовать с
другими переменными
Проверка цели: полное присваивание удовл. всех
ограничениям
Для всех задач CSP характерно:
Любое решение имеет глубину n, если имеется n
переменных. В связи с этим наиболее оптимально применять
алгоритмы поиска в глубину
Путь, по которому достигается решение, не имеет значения
Коммутативность (применения любого конкретного
множества действий в процессе ее решения не влияет на
результат)
8

9. Поиск с возвратами

9

10. Пример поиска

10

11. Пример поиска

11

12. Пример поиска

12

13. Пример поиска

13

14. Повышение эффект. поиска

Повысить эффект. поиска можно, ответив на
следующие вопросы:
Какой переменной должно быть присвоено значение в
следующую очередь и в каком порядке необходимо
пытаться присваивать эти значения?
Как влияют текущие присваивания значений
переменным на другие переменные с
неприсвоенными значениями?
Если какой-то путь оказался неудачным (т.е.
достигнуто состояние, в котором ни одна переменная
не имеет допустимых значений), позволяет ли поиск
избежать повторения этой неудачи при прохождении
последующих путей?
14

15. Minimum Remaining Values

Для повышения эффективности поиска
при выборе следующей для присвоения
переменной нужно выбирать ту, которая
имеет минимальное количество
оставшихся значений
Такой подход называется эвристикой с
минимальным количеством оставшихся
значений (Minimum Remaining Values —
MRV)
15

16. Степенная эвристика

В этой эвристике предпринимается
попытка уменьшить коэффициент
ветвления в будущих вариантах за счет
выбора переменной, которая участвует в
наибольшем количестве ограничений на
другие переменные с неприсвоенными
значениями.
16

17. Выбор наиболее ограничительного значения

После выбора одной из переменных в этом
алгоритме необходимо принять решение о
том, в каком порядке должны проверяться ее
значения. Для этого в некоторых случаях
может оказаться эффективной эвристика с
наименее ограничительным значением. В ней
предпочитается значение, в котором из
рассмотрения исключается наименьшее
количество вариантов выбора значений для
соседних переменных в графе ограничений.
17

18. Предварительная проверка

При каждом присваивании значения
переменной Х в процессе
предварительной проверки
просматривается каждая переменная Y c
неприсвоенным значением, которая
соединена с X с помощью некоторого
ограничения, и из области определения
переменной Y удаляется любое значение,
которое является несовместимым со
значением, выбранным для X.
18

19. Сравнение различных модификаций

19