1 Интеллектуальные системы Лекция 3. Задачи удовлетворения ограничений. Поиск в условиях противодействия Вахтин А. А.

2 Задача удовлетворения ограничений Дано: {X 1 D 1, X 2 D 2,..., X n D n } – множество переменных {C 1 (X 1, X 2,… X n ), C 2 (X 1, X 2,… X n ),..., C m (X 1, X 2,… X n )} – множество ограничений F(X 1, X 2,… X n ) max – целевая функция

3 Задача удовлетворения ограничений Начальное состояние. Пустое присваивание {}, в котором ни одной переменной не присвоено значение. Функция определения преемника. Значение может быть присвоено любой переменной с неприсвоенным значением, при условии, что переменная не будет конфликтовать с другими переменными, значения которым были присвоены ранее. Проверка цели. Текущее присваивание является полным. Стоимость пути. Постоянная стоимость для каждого этапа.

4

5

6 Улучшение алгоритма поиска с возвратом для задач удовлетворения ограничений 1. Упорядочивание переменных и значений эвристика с минимальным количеством оставшихся значений степенная эвристика эвристика с наименее ограничительным значением 2. Распространение информации с помощью ограничений предварительная проверка

7

8 Улучшение алгоритма поиска с возвратом для задач удовлетворения ограничений 3. Распространение ограничения проверка совместимости дуг 4. Обработка специальных ограничений ресурсное ограничение распространение пределов

9 Улучшение алгоритма поиска с возвратом для задач удовлетворения ограничений 5. Интеллектуальный поиск с возвратами: поиск в обратном направлении Метод обратного перехода, управляемого конфликтами Метод определения ограничений с помощью обучения

10

11

12 Игра с двумя игроками Min и Max Начальное состояние, которое включает позицию на доске и определяет игрока, который должен ходить. Функция определения преемника, возвращающая список пар (move, state), каждая из которых указывает допустимый ход и результирующее состояние. Проверка терминального состояния, которое определяет, что игра закончена. Состояния, в которых игра закончена, называются терминальными состояниями. Функция полезности (называемая также целевой функцией, или функцией вознаграждения), которая сообщает числовое значение терминальных состояний.

13

14

15

16 Поиск - -отсечением

17 Взвешенная линейная функция оценки состояний:

18

19

20

21

22

23