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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\mathcal {X_{\mathcal {A}}}}\subseteq {\mathcal {X}}$ является подмножеством переменной;
${\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}}\}$ — это кортеж значений, принимаемых назначенными переменными.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Домены

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

% This code works in both YAP and SWI-Prolog using the environment-supplied
% CLPFD constraint solver library.  It may require minor modifications to work
% in other Prolog environments or using other constraint solvers.
:- use_module(library(clpfd)).
sendmore(Digits) :-
   Digits = [S,E,N,D,M,O,R,Y],   % Create variables
   Digits ins 0..9,                % Associate domains to variables
   S #\= 0,                        % Constraint: S must be different from 0
   M #\= 0,
   all_different(Digits),          % all the elements must take different values
                1000*S + 100*E + 10*N + D     % Other constraints
              + 1000*M + 100*O + 10*R + E
   #= 10000*M + 1000*O + 100*N + 10*E + Y,
   label(Digits).                  % Start the search

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

См. также

Ссылки

^ Jump up to: ^а ^б Росси, Франческа ; Бик, Питер ван; Уолш, Тоби (18 августа 2006 г.). Справочник по программированию с ограничениями . Эльзевир. ISBN 9780080463803 .
^ Джаффар, Джоксан и Дж.Л. Лассез. « Программирование логики ограничений ». Материалы 14-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . АКМ, 1987.
^ Мэйо, Брайан; Тьюгу, Энн; Пенджам, Яан (1993). Программирование ограничений . Springer Science+Business Media . п. 76. ИСБН 9783642859830 .
^ Лопес Г., Фриман-Бенсон Б. и Борнинг А. (1994, январь). Калейдоскоп: язык программирования с императивным ограничением. В программировании с ограничениями (стр. 313–329). Шпрингер Берлин Гейдельберг.
^ Батист, Филипп; Папе, Клод Ле; Нуйтен, Вим (6 декабря 2012 г.). Планирование на основе ограничений: применение программирования с ограничениями к задачам планирования . Springer Science & Business Media. ISBN 978-1-4615-1479-4 .
^ Бессьер, Кристиан (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 г.)

[:0-1] Jump up to: ^а ^б Росси, Франческа ; Бик, Питер ван; Уолш, Тоби (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

[1]

[2]

[3]

[4]

[5]

[6]

v т и Типы языков программирования
Level	Machine Assembly Compiled Interpreted Low-level High-level Very high-level Esoteric
Generation	First Second Third Fourth Fifth