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

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

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

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

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

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

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

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

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

Временное параллельное программирование с ограничениями (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]

Домены

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

Ссылки

1. Росси, Франческа ; Бик, Питер ван; Уолш, Тоби (2006-08-18). Справочник по программированию в ограничениях. Elsevier. ISBN 9780080463803.
2. Джаффар, Джоксан и Дж. Л. Лассе. «Программирование логики ограничений». Труды 14-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . ACM, 1987.
3. Mayoh, Brian; Tyugu, Enn; Penjam, Jaan (1993). Constraint Programming. Springer Science+Business Media . стр. 76. ISBN 9783642859830.
4. Лопес, Г., Фримен-Бенсон, Б. и Борнинг, А. (1994, январь). Калейдоскоп: язык программирования с ограничениями. В разделе « Программирование с ограничениями» (стр. 313-329). Springer Berlin Heidelberg.
5. Батист, Филипп; Папе, Клод Ле; Нуйтен, Вим (2012-12-06). Планирование на основе ограничений: применение программирования ограничений к задачам планирования. 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
• Руководство по программированию ограничений
• Система программирования Mozart на archive.today (архив 5 декабря 2012 г.), свободное программное обеспечение на базе Oz ( стиль X11 )
• Cork Constraint Computation Centre в archive.today (архивировано 7 января 2013 г.)