Задача удовлетворения ограничений — Искусственный интеллект — Раздел I: Решение задач

РАЗДЕЛ I - РЕШЕНИЕ ЗАДАЧ Задача удовлетворения ограничений - ЗА Задачи удовлетворения ограничений (ЗУО) — это математические вопросы, определяемые как набор объектов, состояние которых должно удовлетворять ряду ограничений или лимитов. ЗУО представляют объекты задачи в виде набора конечных ограничений на переменные, которая решается методами удовлетворения ограничений. Присвоение и решение ЗАУО Присвоение считается завершенным, когда каждой переменной присваивается значение. Решение ЗАУО — это полное присвоение, удовлетворяющее всем ограничениям. Приложения: Раскраска карт Интерпретация линейных чертежей Задачи планирования Планирование размещения оборудования в СБИС Формальное определение задачи планирования размещения оборудования (CSP) Задача CSP состоит из: Конечного множества переменных X1, X2, …, Xn Непустой области возможных значений для каждой переменной D1, D2, … Dn, где Di = {v1, …, vk} Конечного множества ограничений C1, C2, …, Cm — Каждое ограничение Ci ограничивает значения, которые могут принимать переменные, например, X1 ≠ X2 Состояние определяется как присвоение значений некоторым или всем переменным. Согласованное присвоение, не нарушающее ограничения, называется согласованным или допустимым присвоением. Полное присвоение — это такое присвоение, при котором сохраняется каждая переменная, и оно является решением задачи CSP, т.е. полным присвоением, удовлетворяющим всем ограничениям. Некоторые задачи CSP также требуют решения, максимизирующего целевую функцию. Задача состоит в том, чтобы раскрасить области на заданной карте таким образом, чтобы никакие две смежные области не имели одинаковых цветов. Области на карте — это переменные, а множество возможных цветов для каждой области — это область определения. Представление задачи Переменные: Vi = {WA, NT, Q, NSW, V, SA, T} Области определения: Di = {красный, зеленый, синий} Ограничения: смежные области должны иметь разные цвета например, WA ≠ NT —Таким образом, (WA,NT) должны принадлежать {(красный, зеленый), (красный, синий), (зеленый, красный), …} Начальное состояние: Пустое присваивание {}, в котором все переменные не имеют присвоенных значений Функции-преемники Значение может быть присвоено любой не присвоенной переменной при условии, что оно не конфликтует с ранее присвоенным значением Проверка цели Текущее присваивание завершено, и проверяется, достигнута ли цель Стоимость пути Вычисляется стоимость для каждого шага Решения представляют собой полные и согласованные присваивания, например, WA = красный, NT = зеленый, Q = красный, NSW = зеленый, V = красный, SA = синий, T = зеленый CSP – Раскраска карты против Раскраска графа В большинстве случаев эти задачи имеют множество решений. Топология графа ограничений может быть использована для легкой идентификации решений. Раскраска карты иногда может быть представлена ​​как задача раскраски графа. Поиск целевого состояния в CSP Каждое решение должно быть полным присваиванием и, следовательно, появляется на глубине «n», если существует «n» переменных. Дерево поиска простирается только до глубины «n». Алгоритмы поиска в глубину популярны для CSP. Путь, по которому должно быть достигнуто решение, не имеет значения. Для этой формулировки хорошо работают методы локального поиска. Типы ограничений в CSP: Унарное ограничение (связанное с одной переменной в задаче) Бинарное ограничение (связанное с двумя переменными — раскраска графа) Ограничение высшего порядка (связанное со многими переменными — криптотическая головоломка)