Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Парадигмы программирования
  • v
  • т
  • е

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

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

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

Программирование логики ограничений [ править ]

Основная статья: Программирование логики ограничений

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

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

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

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

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

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

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

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

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

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

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

Определение  -  Назначение (или модель) CSP определяется парой, где:

  • это подмножество переменных;
  • - это набор значений, принимаемых присвоенными переменными.

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

Свойство  -  Учитывая , в ассигнование (частичное или полный) от ПСА , и ограничение в таких , как , Ассигнационного удовлетворяет ограничение тогда и только тогда , когда все значения этих переменных ограничений принадлежат .

Определение  -  Раствор ПСУ является общей ассигнацией , которые удовлетворяют все ограничения задачи.

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

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

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

Основная статья: Оптимизация с ограничениями

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

Оптимальное решение для минимизации (максимизация) КС этого решения , которое сводит к минимуму (максимизирует) значение целевой функции .

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

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

Модели возмущения и уточнения [ править ]

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

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

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

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

Домены [ править ]

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

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

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

Распространение ограничений [ править ]

Основная статья: Распространение ограничений

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

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

Решение ограничений [ править ]

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

Поиск с возвратом [ править ]

Основная статья: Возврат

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

Локальный поиск [ править ]

Основная статья: Локальный поиск (удовлетворение ограничений)

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

Динамическое программирование [ править ]

Основная статья: Динамическое программирование

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

Пример [ править ]

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

% Этот код работает как в YAP, так и в SWI-Prolog с использованием поставляемой средой библиотеки решателя ограничений% CLPFD. Для работы в других средах Prolog или с использованием других средств решения ограничений могут потребоваться незначительные изменения . : -  use_module ( библиотека ( clpfd )). sendmore ( Digits )  : -  Digits  =  [ S , E , N , D , M , O , R , N , 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 ,  метка ( цифры ).  % Начать поиск

Интерпретатор создает переменную для каждой буквы в головоломке. Оператор 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. ^ Jaffar, Joxan и JL. Лассез. « Программирование с ограничениями логики ». Материалы 14-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования. ACM, 1987.
  3. ^ Мэйо, Брайан; Тюгу, Энн; Пенджам, Яан (1993). Ограниченное программирование . Springer Science + Business Media . п. 76. ISBN 9783642859830.
  4. ^ Лопес Г., Фримен-Бенсон Б., & Borning, А. (1994, январь). Калейдоскоп: язык императивного программирования с ограничениями. В программировании ограничений (стр. 313-329). Springer Berlin Heidelberg.
  5. ^ Bessiere, Кристиан (2006), "Ограничение распространения", Справочник по программированию Constraint , Основы искусственного интеллекта, 2 , Elsevier, стр 29-83,. DOI : 10.1016 / s1574-6526 (06) 80007-6 , ISBN 9780444527264

Внешние ссылки [ править ]

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