Jump to content

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

(Перенаправлено из Решателя ограничений )

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

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

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

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

[ редактировать ]

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

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

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

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

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

[ редактировать ]

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

Определение . Проблема удовлетворения ограничений на конечных областях (или CSP) определяется тройкой где:

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

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

  • экстенсиональные ограничения: ограничения определяются путем перечисления набора значений, которые им удовлетворяют;
  • арифметические ограничения: ограничения определяются арифметическим выражением, т. е. с использованием ;
  • логические ограничения: ограничения определяются с явной семантикой, т. е. AllDifferent , AtMost , ...

Определение . Задание (или модель). CSP определяется парой где:

  • является подмножеством переменной;
  • — это кортеж значений, принимаемых назначенными переменными.

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

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

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

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

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

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

[ редактировать ]

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

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

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

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

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

[ редактировать ]

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

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

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

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

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

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

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

[ редактировать ]

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

Каждое условие локальной согласованности может быть реализовано с помощью преобразования, которое меняет проблему, не меняя ее решения. Такое преобразование называется распространением ограничения . [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 из области определения всех остальных переменных. Распространение ограничений может решить проблему, сводя все домены к одному значению; оно может доказать, что проблема не имеет решения, сводя домен к пустому множеству, но также может завершиться без доказательства выполнимости или невыполнимости. Литералы меток используются для фактического поиска решения.

См. также

[ редактировать ]
  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
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: ab35c904b124eb50a921dae1a78ebe0d__1721779620
URL1:https://arc.ask3.ru/arc/aa/ab/0d/ab35c904b124eb50a921dae1a78ebe0d.html
Заголовок, (Title) документа по адресу, URL1:
Constraint programming - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)