Программирование ограничений

Парадигма программирования, в которой отношения между переменными выражаются в форме ограничений.

Программирование с ограничениями (CP) ^[1] — это парадигма решения комбинаторных задач, основанная на широком спектре методов искусственного интеллекта , информатики и исследования операций . При программировании в ограничениях пользователи декларативно устанавливают ограничения на возможные решения для набора переменных решения. Ограничения отличаются от общих примитивов императивных языков программирования тем, что они не определяют шаг или последовательность шагов для выполнения, а скорее свойства искомого решения. Помимо ограничений, пользователям также необходимо указать метод решения этих ограничений. Обычно это основано на стандартных методах, таких как хронологический возврат и распространение ограничений , но может использоваться специальный код, такой как эвристика ветвления для конкретной проблемы .

Программирование с ограничениями берет свое начало и может быть выражено в форме программирования логики с ограничениями , которое встраивает ограничения в логическую программу . Этот вариант логического программирования принадлежит Джаффару и Лассе ^[2] , которые в 1987 году расширили особый класс ограничений, которые были введены в Прологе II . Первыми реализациями программирования логики с ограничениями были Prolog III, CLP(R) и CHIP .

Вместо логического программирования ограничения можно смешивать с функциональным программированием , переписыванием терминов и императивными языками . К языкам программирования со встроенной поддержкой ограничений относятся Oz (функциональное программирование) и Калейдоскоп (императивное программирование). В основном ограничения реализуются в императивных языках с помощью наборов инструментов для решения ограничений , которые представляют собой отдельные библиотеки для существующего императивного языка.

Программирование логики ограничений

Программирование с ограничениями — это встраивание ограничений в основной язык. Первыми используемыми основными языками были языки логического программирования , поэтому эта область первоначально называлась логическим программированием с ограничениями . Эти две парадигмы имеют много общих черт, таких как логические переменные и возврат . Сегодня большинство реализаций Пролога включают одну или несколько библиотек для программирования логики ограничений.

Разница между ними во многом заключается в их стилях и подходах к моделированию мира. Некоторые задачи более естественно (и, следовательно, проще) писать в виде логических программ, тогда как некоторые более естественно писать в виде программ с ограничениями.

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

Программирование с временными параллельными ограничениями (TCC) и недетерминированное программирование с параллельными временными ограничениями (MJV) — это варианты программирования с ограничениями, которые могут работать со временем.

Проблема удовлетворения ограничений

Ограничение — это связь между несколькими переменными, которая ограничивает значения, которые эти переменные могут принимать одновременно.

Определение  .  Проблема удовлетворения ограничений на конечных областях (или CSP) определяется тройкой, где: ${\displaystyle ({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$

• ${\displaystyle {\mathcal {X}}=\{x_{1},\dots ,x_{n}\}}$– множество переменных задачи;
• ${\displaystyle {\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}}$— множество областей определения переменных, т. е. для всех, что у нас есть ; ${\displaystyle k\in [1;n]}$ ${\displaystyle x_{k}\in {\mathcal {D}}_{k}}$
• ${\displaystyle {\mathcal {C}}=\{C_{1},\dots ,C_{m}\}}$представляет собой набор ограничений. Ограничение определяется набором переменных и отношением , которое определяет набор значений, разрешенных одновременно для переменных . ${\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}$ ${\displaystyle {\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}}$ ${\displaystyle {\mathcal {R}}_{i}\subseteq {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}}$ ${\displaystyle {\mathcal {X}}_{i}}$

Существуют три категории ограничений:

• экстенсиональные ограничения: ограничения определяются путем перечисления набора значений, которые им удовлетворяют;
• арифметические ограничения: ограничения определяются арифметическим выражением, т.е. с использованием ; ${\displaystyle <,>,\leq ,\geq ,=,\neq ,...}$
• логические ограничения: ограничения определяются с явной семантикой, т. е. AllDifferent , AtMost , ...

Определение  .  Назначение (или модель) CSP определяется парой, где: ${\displaystyle {\mathcal {A}}}$ ${\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$ ${\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}$

• ${\displaystyle {\mathcal {X_{\mathcal {A}}}}\subseteq {\mathcal {X}}}$является подмножеством переменной;
• ${\displaystyle {\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}}$представляет собой кортеж значений, принимаемых назначенными переменными.

Присваивание — это связывание переменной со значением из ее области определения. Частичное присвоение — это когда присвоено подмножество переменных задачи. Полное присвоение — это когда всем переменным задачи присвоены значения.

Свойство  —  Учитывая назначение (частичное или полное) CSP и ограничение , такое как , назначение удовлетворяет ограничению тогда и только тогда, когда все значения переменных ограничения принадлежат . ${\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}$ ${\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$ ${\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}$ ${\displaystyle P}$ ${\displaystyle {\mathcal {X}}_{i}\subseteq {\mathcal {X_{\mathcal {A}}}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle C_{i}}$ ${\displaystyle {\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}}$ ${\displaystyle C_{i}}$ ${\displaystyle {\mathcal {R}}_{i}}$

Определение  .  Решение CSP — это полное задание, которое удовлетворяет всем ограничениям проблемы.

В ходе поиска решений CSP пользователь может пожелать:

• поиск решения (удовлетворяющего всем ограничениям);
• нахождение всех решений проблемы;
• доказательство неразрешимости задачи.

Проблема оптимизации ограничений

Задача оптимизации ограничений (COP) — это проблема удовлетворения ограничений, связанная с целевой функцией.

Оптимальным решением минимизации (максимизации) КПД является решение, минимизирующее (максимизирующее) значение целевой функции .

В процессе поиска решения КС пользователь может пожелать:

• поиск решения (удовлетворяющего всем ограничениям);

• поиск наилучшего решения относительно поставленной цели;
• доказательство оптимальности найденного наилучшего решения;
• доказательство неразрешимости задачи.

Модели возмущения и уточнения

Языки программирования на основе ограничений следуют одному из двух подходов: ^[3]

• Уточняющая модель: переменные в задаче изначально не назначены, и предполагается, что каждая переменная может содержать любое значение, входящее в ее диапазон или домен. По мере выполнения вычислений значения в области определения переменной сокращаются, если оказывается, что они несовместимы с возможными значениями других переменных, пока для каждой переменной не будет найдено единственное значение.
• Модель возмущения: переменным в задаче присваивается одно начальное значение. В разное время одна или несколько переменных получают возмущения (изменения их старого значения), и система распространяет это изменение, пытаясь присвоить новые значения другим переменным, которые соответствуют возмущению.

Распространение ограничений в задачах удовлетворения ограничений является типичным примером уточняющей модели, а электронные таблицы — типичным примером модели возмущений.

Модель уточнения является более общей, поскольку она не ограничивает переменные одним значением и может привести к нескольким решениям одной и той же проблемы. Однако модель возмущений более интуитивно понятна для программистов, использующих объектно-ориентированные языки со смешанными императивными ограничениями. ^[4]

Домены

Ограничения, используемые в программировании с ограничениями, обычно относятся к некоторым конкретным областям. Некоторые популярные области программирования в ограничениях:

• логические домены, где применяются только ограничения true/false ( проблема SAT )
• целочисленные области, рациональные области
• интервальные области, в частности для задач планирования ^[5]
• линейные области, где описываются и анализируются только линейные функции (хотя подходы к нелинейным проблемам существуют)
• конечные области, где ограничения определены над конечными множествами
• смешанные домены, включающие два или более из вышеперечисленных

Конечные области — одна из наиболее успешных областей программирования в ограничениях. В некоторых областях (например, в исследовании операций ) программирование в ограничениях часто отождествляется с программированием в ограничениях для конечных областей.

Распространение ограничений

Условия локальной согласованности — это свойства задач удовлетворения ограничений , связанные с согласованностью подмножеств переменных или ограничений. Их можно использовать для уменьшения пространства поиска и облегчения решения проблемы. Используются различные виды условий локальной согласованности, включая согласованность узла , согласованность дуги и согласованность пути .

Каждое условие локальной согласованности может быть реализовано с помощью преобразования, которое меняет проблему, не меняя ее решения. Такое преобразование называется распространением ограничения . ^[6] Распространение ограничений работает за счет сокращения областей переменных, усиления ограничений или создания новых. Это приводит к сокращению пространства поиска, что упрощает решение проблемы некоторыми алгоритмами. Распространение ограничений также можно использовать в качестве средства проверки невыполнимости, неполного в целом, но полного в некоторых частных случаях.

Решение ограничений

Существует три основных алгоритмических метода решения задач удовлетворения ограничений: поиск с возвратом, локальный поиск и динамическое программирование. ^[1]

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

Поиск с возвратом — это общий алгоритм поиска всех (или некоторых) решений некоторых вычислительных задач , в частности проблем удовлетворения ограничений , который постепенно создает кандидатов для решения и отбрасывает кандидата («возврат»), как только он определяет, что кандидат не может возможно, будет завершено до действительного решения.

Локальный поиск

Локальный поиск – неполный метод поиска решения проблемы . Он основан на итеративном улучшении назначения переменных до тех пор, пока не будут удовлетворены все ограничения. В частности, алгоритмы локального поиска обычно изменяют значение переменной в задании на каждом этапе. Новое присвоение близко к предыдущему в пространстве присвоения, отсюда и название локальный поиск .

Динамическое программирование

Динамическое программирование — это одновременно метод математической оптимизации и метод компьютерного программирования. Это относится к упрощению сложной проблемы путем рекурсивного разбиения ее на более простые подзадачи . Хотя некоторые проблемы принятия решений невозможно разобрать таким образом, решения, охватывающие несколько моментов времени, часто распадаются рекурсивно. Аналогично, в информатике, если проблему можно решить оптимально, разбив ее на подзадачи и затем рекурсивно найдя оптимальные решения подзадач, то говорят, что она имеет оптимальную подструктуру .

Пример

Синтаксис выражения ограничений для конечных областей зависит от основного языка. Ниже представлена ​​программа на Прологе , которая решает классическую алфавитную головоломку SEND+MORE=MONEY в логическом программировании с ограничениями:

% Этот код работает как в YAP, так и в SWI-Prolog, используя поставляемую со средой библиотеку решателя ограничений % CLPFD. Для работы % в других средах Пролога или при использовании других решателей ограничений могут потребоваться незначительные изменения . :-  use_module ( библиотека ( clpfd )). sendmore ( Digits )  :-  Digits  =  [ S , E , N , D , M , O , R , Y ] , % Создать переменные Цифры ins 0..9 , % Связать домены с переменными S #\= 0 , % Ограничение: S должно отличаться от 0 M #\= 0 , all_dependent ( Digits ), % все элементы должны принимать разные значения 1000 * S + 100 * E + 10 * N + D % Другие ограничения + 1000 * M + 100 * O + 10 * R + E #= 10000 * M + 1000 * O + 100 * N + 10 * E + Y , метка ( цифры ). % Начать поиск                                          

Интерпретатор создает переменную для каждой буквы головоломки. Оператор insиспользуется для указания доменов этих переменных, чтобы они находились в диапазоне значений {0,1,2,3,...,9}. Ограничения S#\=0и M#\=0означают, что эти две переменные не могут принимать нулевое значение. Когда интерпретатор оценивает эти ограничения, он уменьшает области определения этих двух переменных, удаляя из них значение 0. Затем all_different(Digits)рассматривается ограничение ; он не уменьшает какой-либо домен, поэтому он просто сохраняется. Последнее ограничение указывает, что цифры, назначенные буквам, должны быть такими, чтобы «SEND+MORE=MONEY» сохранялось, когда каждая буква заменяется соответствующей цифрой. Из этого ограничения решатель делает вывод, что M=1. Все сохраненные ограничения, включающие переменную M, пробуждаются: в этом случае распространение ограничения на all_differentограничение удаляет значение 1 из области определения всех остальных переменных. Распространение ограничений может решить проблему, сводя все домены к одному значению; оно может доказать, что проблема не имеет решения, сводя домен к пустому множеству, но также может завершиться без доказательства выполнимости или невыполнимости. Литералы меток используются для фактического поиска решения.

Смотрите также

• Комбинаторная оптимизация
• Программирование логики ограничений
• Параллельное программирование логики ограничений
• Математическая оптимизация
• Эвристические алгоритмы
• Проблема с расписанием работы медсестры
• Регулярное ограничение
• Проблема с передвижным турниром

Рекомендации

1. Росси, Франческа ; Бик, Питер ван; Уолш, Тоби (18 августа 2006 г.). Справочник по программированию с ограничениями. Эльзевир. ISBN 9780080463803.
2. Джаффар, Джоксан и Дж.Л. Лассез. «Программирование логики ограничений». Материалы 14-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . АКМ, 1987.
3. Мэйо, Брайан; Тьюгу, Энн; Пенджам, Яан (1993). Программирование ограничений. Springer Science+Business Media . п. 76. ИСБН 9783642859830.
4. Лопес Г., Фриман-Бенсон Б. и Борнинг А. (1994, январь). Калейдоскоп: язык программирования с императивным ограничением. В программировании с ограничениями (стр. 313–329). Шпрингер Берлин Гейдельберг.
5. Батист, Филипп; Папе, Клод Ле; Нуйтен, Вим (6 декабря 2012 г.). Планирование на основе ограничений: применение программирования с ограничениями к задачам планирования. Springer Science & Business Media. ISBN 978-1-4615-1479-4.
6. Бессьер, Кристиан (2006), «Распространение ограничений», Справочник по программированию с ограничениями , Основы искусственного интеллекта, том. 2, Elsevier, стр. 29–83, CiteSeerX 10.1.1.398.4070 , doi : 10.1016/s1574-6526(06)80007-6, ISBN  9780444527264

Внешние ссылки

• Ассоциация программирования с ограничениями
• Серия конференций CP
• Руководство по программированию ограничений
• Система программирования Моцарта на archive.today (архивировано 5 декабря 2012 г.), бесплатное программное обеспечение на базе Oz ( стиль X11 ).
• Вычислительный центр ограничений Корка на archive.today (архивировано 7 января 2013 г.)