Введение

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

Программирование с ограничениями (CP) – это парадигма для решения комбинаторных задач, использующая широкий спектр методов из искусственного интеллекта, информатики и исследования операций. В программировании с ограничениями пользователи декларативно задают ограничения на допустимые решения для набора переменных принятия решений. Ограничения отличаются от стандартных примитивов императивных языков программирования тем, что они не указывают шаг или последовательность шагов для выполнения, а описывают свойства искомого решения. Помимо ограничений, пользователям необходимо указать метод их решения. Обычно это стандартные методы, такие как хронологический возврат и распространение ограничений, но также может использоваться специализированный код, например, эвристика ветвления, специфичная для задачи. Программирование с ограничениями берет начало в логическом программировании с ограничениями, которое встраивает ограничения в логическую программу. Этот вариант логического программирования разработан Джаффаром и Лассесом, которые в 1987 году расширили конкретный класс ограничений, впервые представленный в Prolog II. Первыми реализациями логического программирования с ограничениями были Prolog III, CLP(R) и CHIP. Вместо логического программирования ограничения могут комбинироваться с функциональным программированием, преобразованием термов и императивными языками. Языки программирования со встроенной поддержкой ограничений включают Oz (функциональное программирование) и Kaleidoscope (императивное программирование). Чаще всего ограничения реализуются в императивных языках с помощью инструментариев для решения ограничений – отдельных библиотек для существующих императивных языков.

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

Ограничивающее программирование — это встраивание ограничений в язык-хост. Первыми языками-хостами, которые использовались, были языки логического программирования, поэтому эта область первоначально называлась логическим программированием с ограничениями. Обе парадигмы имеют много общих важных особенностей, таких как логические переменные и возврат (backtracking). Сегодня большинство реализаций Prolog включают одну или несколько библиотек для логического программирования с ограничениями. Разница между ними заключается главным образом в стилях и подходах к моделированию мира. Некоторые задачи более естественно (и, следовательно, проще) представлять в виде логических программ, а другие — в виде программ с ограничениями. Подход ограничивающего программирования заключается в поиске состояния мира, в котором одновременно выполняется большое количество ограничений. Задача обычно формулируется как состояние мира, содержащее ряд неизвестных переменных. Программа с ограничениями ищет значения для всех переменных. Временное конкурентное программирование с ограничениями (TCC) и недетерминированное временное конкурентное программирование с ограничениями (MJV) — это варианты ограничивающего программирования, способные работать со временем.

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

Условия локальной согласованности — это свойства задач, связанных с удовлетворением ограничений, которые относятся к согласованности подмножеств переменных или ограничений. Они могут использоваться для уменьшения пространства поиска и упрощения решения задачи. Применяются различные виды условий локальной согласованности, включая согласованность узлов, дуг и путей. Каждое условие локальной согласованности может быть обеспечено преобразованием, которое изменяет задачу, не меняя при этом её решений. Такое преобразование называется распространением ограничений. Распространение ограничений работает путем сужения областей значений переменных, усиления ограничений или добавления новых. Это приводит к уменьшению пространства поиска, что упрощает решение задачи некоторыми алгоритмами. Распространение ограничений также может использоваться как средство проверки выполнимости, которое в общем случае является неполным, но в некоторых конкретных случаях — полным.

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

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

Поиск с обратным отслеживанием

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

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

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

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

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