Ограниченное программирование - Constraint programming

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

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

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

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

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

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

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

Временное параллельное программирование с ограничениями (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 к в [1; п]}$ у нас есть ${ displaystyle x_ {k} in { mathcal {D}} _ {k}}$ ;
${ Displaystyle { mathcal {C}} = {C_ {1}, точки, C_ {m} }}$ это набор ограничений. Ограничение ${ Displaystyle C_ {я} = ({ mathcal {X}} _ {я}, { mathcal {R}} _ {я})}$ определяется набором ${ displaystyle { mathcal {X}} _ {i} = {x_ {i_ {1}}, dots, x_ {i_ {k}} }}$ переменных и отношения ${ displaystyle { mathcal {R}} _ {i} subset { mathcal {D}} _ {i_ {1}} times dots times { mathcal {D}} _ {i_ {k}} }$ который определяет набор значений, разрешенных одновременно для переменных ${ Displaystyle { mathcal {X}} _ {я}}$ :

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

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

Определение — Задание (или модель) ${ 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}}}} subset { 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}} }}$ - это набор значений, принимаемых присвоенными переменными.

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

Свойство — Данный ${ Displaystyle { mathcal {A}} = ({ mathcal {X _ { mathcal {A}}}}, { mathcal {V _ { mathcal {A}}}})}$ назначение (частичное или полное) CSP ${ Displaystyle P = ({ mathcal {X}}, { mathcal {D}}, { mathcal {C}})}$ , и ${ Displaystyle C_ {я} = ({ mathcal {X}} _ {я}, { mathcal {R}} _ {я})}$ ограничение ${ displaystyle P}$ такие как ${ Displaystyle { mathcal {X}} _ {я} subset { 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}} _ {я}}$ .

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

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

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

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

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

An Оптимальное решение к минимизации (максимизации) COP - это решение, которое минимизирует (максимизирует) значение целевая функция.

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

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

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

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

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

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

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

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

Домены

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

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

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

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

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

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

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

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

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

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

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

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

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

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

пример

Синтаксис для выражения ограничений для конечных доменов зависит от основного языка. Ниже приводится Пролог программа, которая решает классические алфавитный головоломка ОТПРАВИТЬ + БОЛЬШЕ = ДЕНЬГИ в программировании логики ограничений:

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

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

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

внешняя ссылка

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

[:0-1] а ^б Росси, Франческа; Бик, Питер ван; Уолш, Тоби (18 августа 2006 г.). Справочник по программированию в ограничениях. Эльзевир. ISBN 9780080463803.

[2] Джаффар, Джоксан и Дж.Л. Лассез. "Программирование логики ограничений. »Труды 14-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования. ACM, 1987.

[3] Мэйо, Брайан; Тюгу, Энн; Пенджам, Яан (1993). Программирование ограничений. Springer Science + Business Media. п. 76. ISBN 9783642859830.

[4] Лопес, Г., Фриман-Бенсон, Б., и Борнинг, А. (1994, январь). Калейдоскоп: язык императивного программирования с ограничениями. В Программирование ограничений (стр. 313-329). Springer Berlin Heidelberg.

[5] Бессьер, Кристиан (2006), «Ограниченное распространение», Справочник по программированию в ограничениях, Основы искусственного интеллекта, 2, Elsevier, стр. 29–83, Дои:10.1016 / с1574-6526 (06) 80007-6, ISBN 9780444527264

[1]

[2]

[3]

[4]

[5]

Типы языков программирования
Парадигма	Актерский Массив Аспектно-ориентированный На основе классов Конкатенативный Одновременный Поток данных Декларативная Зависит от домена Динамический Эзотерический Событийный Расширяемый Функциональный Императив Логика Макрос Метапрограммирование Объектно-ориентированный Объектно-ориентированный Трубопровод Процедурный На основе прототипа Светоотражающий Основанный на правилах Сценарии Ориентированный на стек Синхронный Тактильный Шаблон
Уровень	сборка Составлено Истолкованный Машина Низкий уровень Высокий уровень Очень высокий уровень
Поколение	Первый Второй В третьих Четвертый Пятый
Связанный	Не на английском языке Визуальный