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

Программирование логики ограничений - это форма программирования ограничений, в которой программирование логики расширен, чтобы рассмотреть концепцию из удовлетворение ограничений. Программа логики ограничений - это логическая программа, содержит ограничение в теле предложений. Пример предложения, включающего ограничение: A (X, Y): - X + Y>0, B (X), C (Y). В этом разделе X + Y>0- ограничение; A (X, Y), B (X)и C (Y)- это литералы, как в обычном логическом программировании. В этом разделе указано одно условие, при котором выполняется инструкция A (X, Y): X + Yбольше нуля, и оба B (X)и C (Y)верны.

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

• 1 Обзор
• 2 Семантика
• 3 Положения и условия
  • 3.1 Термины дерева
  • 3.2 Реалы
  • 3.3 Конечные домены
• 4 Хранилище ограничений
• 5 Маркировка
• 6 Переформулировки программы
• 7 Правила обработки ограничений
• 8 Оценка снизу вверх
• 9 Параллельное программирование логики ограничений
• 10 Приложения
• 11 История
• 12 См. Также
• 13 Ссылки
• 14 Ссылки

Формально программы с логикой ограничений похожи на обычные логические программы, но тело предложений может содержать ограничение в дополнение к обычным литералам логического программирования. Например, X>0является ограничением и включен в последний пункт следующей логической программы ограничения.

B (X, 1): - X <0. B(X,Y):- X=1, Y>0. A (X, Y): - X>0, B (X, Y).

Как и в обычном логическом программировании, оценка такой цели, как A (X, 1), требует оценки тела последнего предложения с Y = 1. Как и в обычном логическом программировании, это, в свою очередь, требует доказательства цели B (X, 1). В отличие от обычного логического программирования, это также требует ограничения: X>0, ограничение в теле последнего предложения (в обычном логическом программировании X>0 не может быть доказано, если X не связан до полностью основного термина, и выполнение программы завершится ошибкой, если это не так).

При обнаружении ограничения не всегда можно определить, удовлетворяется ли ограничение. В этом случае, например, значение Xне означает при оценке последнего предложения. В результате ограничения X>0не удовлетворяется и не нарушается в этот момент. Вместо того, чтобы продолжить оценку B (X, 1)и затем проверить, является ли полученное значение Xположительным, интерпретатор сохранения сохранения X>0, а переходит к оценке B (X, 1); таким образом, интерпретатор может построить нарушение ограничения X>0во время оценки B (X, 1)и немедленно вернуться назад, если это так, а не ждать оценка B ( X, 1)для заключения.

В общем, оценка логической программы ограничений выполняется же, как и обычная логическая программа. Однако ограничения, устанавливаемые во время оценки, помещаются в набор, называемый хранилищем ограничений. В качестве примера оценки цели A (X, 1)продолжается путем оценки тела первого предложения с Y = 1; эта оценка cer X>0в хранилище ограничений и требует подтверждения цели B (X, 1). При попытке доказать эту цель пытается первое предложение, но его оценка X <0в хранилище ограничений. Это добавление хранилище ограничений неудовлетворительным. Затем интерпретатор возвращается назад, удаляя последнее добавление из хранилища ограничений. Оценка второго предложения к хранилищу ограничений X = 1и Y>0. Для доказательства интерпретатора останавливается на решении X = 1, Y = 1.

Семантика программ логики ограничения может быть определена в терминах виртуального интерпретатора. Поддерживает пару $⟨G,\; S⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; G,\; S\; \backslash \; rangle\}$во время выполнения. Первый элемент этой пары называется текущей; второй элемент называется хранилищем ограничений. Текущие предложения содержат литералы, которые пытается доказать, а также может содержать некоторые ограничения, которые помогают ему помочь; хранилище ограничений содержит все ограничения, которые интерпретатор считал выполнимыми до сих пор.

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

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

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

Интерпретатор доказал цель, когда текущая цель пуста и хранилище ограничений не обнаружено как неудовлетворительное. Результат выполнения - текущий набор (упрощенных) ограничений. Этот набор может пропускать в себя такие ограничения, как $X\; =\; 2\; \{\backslash \; displaystyle\; X\; =\; 2\}$, которые заставляют переменные к определенному значению, но также могут пропускать такие как $X>2\; \{\backslash \; displaystyle\; X>2\}$, которые только связывают переменные, не присваивая им конкретные значения.

Формально семантика программирования ограничений определяется в терминах производных. Переход - это пара пар цель / хранилище, таким $⟨G,\; S⟩\; \to \; ⟨G\; \text{'},\; S\text{'}⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; G,\; S\; \backslash \; rangle\; \backslash \; rightarrow\; \backslash \; langle\; G\text{'},\; S\; \text{'}\backslash \; rangle\}$. Такая пара утверждает возможность выхода из состояния $⟨\; G,\; S⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; G,\; S\; \backslash \; rangle\}$для состояний $⟨G\; \prime ,\; S\; \prime ⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; G\; \text{'},\; S\text{'}\; \backslash \; rangle\}$. Такой переход возможен в трех преступников:

• G являе тся ограничением C, $G\; \prime \; =\; G\; \setminus \; \{C\}\; \{\backslash \; displaystyle\; G\; \text{'}=\; G\; \backslash \; backslash\; \backslash \; \{C\; \backslash \}\}$и $S\; \prime \; =\; S\; \cup \; \{C\}\; \{\backslash \; displaystyle\; S\; \text{'}=\; S\; \backslash \; чашка\; \backslash \; \{C\; \backslash \}\}$; другими словами, ограничение можно переместить из цели в хранилище ограничений.
• элемент G является литералом $L\; (t\; 1,\dots ,\; tn)\; \{\backslash \; displaystyle\; L\; (t\_\; \{1\},\; \backslash \; ldots,\; t\_\; \{n\})\}$, существует предложение, которое, переписанное с использованием новых чисел, имеет вид $L\; (t\; 1\; \prime ,\dots ,\; tn\; \prime ):\; -\; B\; \{\backslash \; displaystyle\; L\; (t\_\; \{1\}\; \text{'},\; \backslash \; ldots,\; t\_\; \{n\}\text{'}):\; -\; B\}$, $G\; \prime \; \{\backslash \; displaystyle\; G\; \text{'}\}$- это G с $L\; (t\; 1,\dots ,\; tn)\; \{\backslash \; displaystyle\; L\; (t\_\; \{1\},\; \backslash \; ldots,\; t\_\; \{\; n\})\}$заменено на $t\; 1\; =\; t\; 1\; \prime ,\dots ,\; tn\; =\; tn\; \prime ,\; B\; \{\backslash \; displaystyle\; t\_\; \{1\}\; =\; t\_\; \{1\}\; \text{'},\; \backslash \; ldots,\; t\_\; \{n\; \}\; =\; t\_\; \{n\}\; \text{'},\; B\}$и $S\text{'}\; =\; S\; \{\backslash \; displaystyle\; S\; \text{'}=\; S\}$; Словами, литерал может быть заменен телом нового варианта предложения с тем же предикатом в заголовке, добавлен новый вариант и состав выше терминов к цели
• S и $S\; \text{'}\{\backslash \; displaystyle\; S\text{'}\}$эквивалентны в соответствии с определенной семантикой переходной ограниченностью

Последовательность является производной. Цель G может быть доказана, если существует производное от $⟨G,\; \varnothing ⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; G,\; \backslash \; emptyset\; \backslash \; rangle\}$к $⟨\varnothing ,\; S⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; \backslash \; emptyset,\; S\; \backslash \; rangle\}$для некоторого выполненного хранилища ограничений S. Эта семантика формализует возможные варианты развития интерпретатора, который произвольно выбирает литерал цели для обработки и предложение для замены литералов. Другими словами, цель доказывается в этой семантике, если существует последовательность вариантов выбора литералов и предложений, среди возможных многих, которые приводят к пустым целям и выполнимому хранилищу.

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

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

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

Попарное равенство двух литералов часто компактно обозначается как $L\; (t\; 1,\dots ,\; tn)\; =\; L\; (t\; 1\; \prime ,\dots ,\; tn\; \prime )\; \{\backslash \; displaystyle\; L\; (t\_\; \{1\},\; \backslash \; ldots,\; t\_\; \{n\})\; =\; L\; (t\_\; \{1\}\; \text{'},\; \backslash \; ldots,\; t\_\; \{n\}\text{'})\}$: это сокращение для ограничений $t\; 1\; =\; t\; 1\; \prime ,\dots ,\; tn\; знак\; равно\; tn\; \prime \; \{\backslash \; displaystyle\; t\_\; \{1\}\; =\; t\_\; \{1\}\; \text{'},\; \backslash \; ldots,\; t\_\; \{n\}\; =\; t\_\; \{n\}\text{'}\}$. Общий вариант семантики для программирования логики огранич $L\; (t\; 1,\dots ,\; tn)\; =\; L\; (t\; 1\; \prime ,\dots ,\; tn\; \prime )\; \{\backslash \; displaystyle\; L\; (t\_\; \{1\},\; \backslash \; ldots,\; t\_\; \{n\})\; =\; L\; (t\_\; \{1\}\; \text{'},\; \backslash \; ldots,\; t\_\; \{n\}\text{'})\}$непосредственно в хранилище ограничений, а не в цель.

Используются разные определения терминов, порождающие различные виды программирования логики ограничения: над деревьями, вещественными числами или конечными областями. Своеобразным ограничением, которое всегда присутствует, является равенством условий. Такие ограничения необходимы, потому что интерпретатор репер t1 = t2к цели всякий раз, когда литерал P (... t1...)заменяется теломего варианта предложения, чей head is P (... t2...).

Термины дерева

Программирование логики ограничений с терминами деревьев имитирует программирование обычной логики, сохраняя подстановки как ограничения в хранилище ограничений. Термины - это переменные, константы и функциональные символы, применяемые к другим терминам. Единственные рассматриваемые ограничения - это равенство и неравенство между терминами. Равенство особенно важно, поскольку такие ограничения, как t1 = t2, часто генерируются интерпретатором. Ограничения равенства для членов могут быть упрощены, есть решены с помощью унификации :

Ограничение t1 = t2может быть упрощено, если оба члена являются функциональными символами, применяемыми к другим терминам. Если два одинаковых совпадения и количество подтермов также одинаково, это ограничение можно заменить попарным равенством подтермов. Если члены состоят из разных функциональных символов или одного и того же функтора, но на разном количестве, ограничение является невыполнимым.

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

В этой форме требований ограничений значения числа являются терминами.

Реальные числа

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

Если быть точным, термины - это выражения над переменными и действительными станстантами. Равенство между терминами - это своего установления между ограничением, присутствует всегда, поскольку интерпретатор генерирует равенство терминов во время выполнения. Например, если первая литерал текущей цели - A (X + 1), а интерпретатор выбрал предложение, которое является A (Y-1): - Y = 1после перезаписи текущей текущей цели добавляются следующие ограничения: X + 1 = Y-1и $Y\; =\; 1\; \{\backslash \; displaystyle\; Y\; =\; 1\}$. Не используются, что правила упрощения, очевидно для функциональных символов, не используются: X + 1 = Y-1не является неприемлемым, потому что первое выражение построено с использованием +, а второе - с использованием -.

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

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

Конечные области

Третий класс ограничений, используемый в программировании логики ограничений, - это конечные области. Значения в этом случае берутся из конечной области, часто из целых чисел. Для каждой переменной может быть указан другой домен: X :: [1..5], например, означает, что значение Xнаходится между 1и 5. Диапазон также может быть задана путем перечисления всех значений, которые могут принимать переменная; Следовательно, в указанном выше объявлении домена также может быть записано X :: [1,2,3,4,5]. Этот второй способ указания домена позволяет использовать домены, которые не состоят из целых чисел, например X :: [george, mary, john]. Если параметр не указан, указан, что это набор целых чисел, представимых на языке. Группе можно задать один и тот же домен, используя объявление типа [X, Y, Z] :: [1..5].

Домен может быть уменьшен во выполнении. Действительно, когда интерпретатор выполняет функцию ограничения в хранилище ограничений, он распространение ограничения, чтобы обеспечить соответствие ограничения, и эти операции могут выполнять ограничения в области ограничения. Если домен переменной становится пустым, хранилище ограничений несовместимо, и алгоритм выполняет возврат. Если домен переменной становится одноэлементным, переменной может быть присвоено уникальное значение в ее домене. Обычно применяются следующие формы согласованности: согласованность дуги, согласованность гипер-дуги и согласованность границ. Текущий домен переменной можно проверить с помощью определенных литералов; например, dom (X, D)определяет текущий домен Dпеременной X.

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

Хранилище ограничений содержит ограничения, которые в настоящее время считаются выполнимыми. Можно рассмотреть, что в настоящее время заменяет обычное логическое программирование. Когда разрешены только термины дерева, хранилище ограничений содержит ограничения в форме t1 = t2; эти ограничения упрощаются за счет объединения, в результате чего возникают ограничения в виде переменная = термин; такие ограничения эквивалентны замене.

Однако хранилище ограничений может также содержать ограничения в форме t1! = T2, если разница ! =между терминами разрешена. Когда разрешены ограничения по реальным или конечным доменам, хранилище ограничений может также содержать ограничения, зависящие от домена, такие как X + 2 = Y / 2и т. Д.

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

Доменные ограничения могут поступать в хранилище ограничений как из тела предложения, так и из приравнивания литерала к заголовку предложения: например, если интерпретатор перезаписывает литерал A (X +2)с предложением, заголовок нового варианта которого равен A (Y / 2), ограничение X + 2 = Y / 2добавляется в хранилище ограничений. Если переменная появляется в реальной области, она может принимать значение в действующей или конечной области. Такая переменная не может принимать в качестве значения созданный из функтора, примененного к другим терминам. Хранилище ограничений неудовлетворительно, если переменная обязана принимать как значение конкретной области, так и функционтор, применяемый к терминам.

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

В результате этих операций добавление новых ограничений может изменить старые. Очень важно, чтобы интерпретатор мог отменить эти изменения при возврате. В простейшем случае интерпретатор сохраняет полное состояние хранилища каждый раз, когда он делает выбор (он выбирает предложение, чтобы переписать цель). Существуют более эффективные методы, позволяющие хранилищу ограничения вернуться в предыдущее состояние. В частности, можно просто сохранить изменения в хранилище выбора, сделанные между двумя точками, включая изменения, внесенные в старые ограничения. Это можно сделать, просто сохранив старое значение измененных ограничений; этот метод называется трейлингом. Более продвинутый метод - внесенные в измененные ограничения сохранить изменения. Например, линейное ограничение путем изменения его коэффициента: сохранение разницы между старым и новым коэффициентом позволяет отменить изменение. Этот второй метод называется семантическим отслеживанием с возвратом, поскольку сохраняется семантика изменения, а не только старая версия ограничений.

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

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

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

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

решение (X): - ограничения (X), маркировка (X), ограничения (X): - (все ограничения CSP)

Когда интерпретатор оценивает цель решить (аргументы), он помещает тело нового первого варианта предложения в текущую цель. Ограничения первая цель - ограничения (X '), оценивается второе предложение, и эта операция перемещает все ограничения в текущей цели, в конечном итоге, в хранилище ограничений. Затем оценивается литерал labeling (X '), вызывая поиск решения хранилища ограничений. Хранилище ограничений содержит в точности ограничения исходной задачи ограничения, эта операция ищет решение исходной задачи.

Данная логическая программа ограничений может быть переформулирована для повышения ее эффективности. Первое правило заключается в том, что маркировочные литералы следует размещать после того, как в хранилище ограничений будет накоплено количество ограничений на помеченные литералы. Теоретически A (X): - маркировка (X), X>0эквивалентна A (X): - X>0, маркировка (X), поиск, который выполняется, когда интерпретатор обнаруживает, что литерал маркировки находится в хранилище ограничений, которое не содержит ограничения X>0. В результате он может генерировать решения, такие как X = -1, которые, как позже выясняется, не удовлетворяют этому ограничению. С другой стороны, во второй формулировке поиск выполняется только тогда, когда ограничение уже находится в хранилище ограничений. В результате можно найти только согласованные с ним решения, используя тот факт, что дополнительные ограничения сокращают пространство поиска.

Вторая переформулировка, которая может повысить эффективность, - это использовать ограничения перед литералами в теле предложений. Опять же, A (X): - B (X), X>0и A (X): - X>0, B (X)в принципе эквивалентны. Однако для первого может потребоваться больше вычислений. Например, хранилище ограничений содержит ограничение X <-2, интерпретатор рекурсивно вычисляет B (X)в первом случае; в случае успеха он обнаруживает несогласованность хранилища ограничений при добавлении X>0. Во втором случае при оценке этого предложения интерпретатор сначала X>0в хранилище, а затем, возможно ограничения, оценивает B (X). Хранилище ограничений после добавления X>0оказывается несовместимым, рекурсивное вычисление B (X)не выполняется вообще.

Третья переформулировка, которая может повысить эффективность, - это добавление избыточных ограничений. Если программист знает (любыми) способами, он может включить это ограничение, чтобы как можно скорее вызвать несогласованность хранилища ограничений. Например, заранее известно, что оценка B (X)приведет к положительному значению для X, программист может добавить X>0перед любым появлением B (Х). Например, A (X, Y): - B (X), C (X)не удастся выполнить цель A (-2, Z), но это только выясняется при оценке подцели В (Х). С другой стороны, если указанное выше предложение заменяется на A (X, Y): - X>0, A (X), B (X), интерпретатор выполняет возврат, как только ограничение X>0добавлено хранилище ограничений, что происходит еще до того, как начнется оценка B (X).

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

A (X) <=>B (X) | C (X) A (X) ==>B (X) | C (X)

Первое правило гласит, что если B (X)влечет за собой хранилище, ограничение A (X)может быть переписано как С (Х). Например, N * X>0можно переписать как X>0, если хранилище подразумевает, что N>0. Символ <=>в логике напоминает эквивалентность и указывает, что первое ограничение эквивалентно второму. На практике это означает, что первое ограничение можно заменить вторым.

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

Эквивалентность позволяет упростить хранилище ограничений, заменив некоторые ограничения более простыми; в частности, если третье ограничение в правиле эквивалентно равно истина, второе ограничение влечет за собой, первое ограничение удаляется из хранилища ограничений. Установление позволяет новые ограничения, что может привести к доказательству несогласованности ограничения и, как правило, может сократить объем поиска, требования для его выполнимости.

Пункты логического программирования в режиме установления ограничений. Различные предложения используются для реализации вариантов выбора метода; правила обработки ограничений используются для перезаписи хранилища ограничений во время выполнения. Например, таким образом можно реализовать отслеживание с возвратом с модулем распространения. Пусть держит (L)представляет пропозициональное предложение, в литералах которого в списке Lнаходятся в том же порядке, в котором они оцениваются. Алгоритм может быть реализован с использованием предложений для выбора присвоения литералу значения true или false и правил обработки ограничений для распространения распространения. Эти правила определяют, что держит ([l | L])может быть удалено, если l = trueследует из хранилища, и его можно переписать как hold (L)если l = false, тоследует из магазина. Аналогично, держит ([l])можно заменить на l = true. В этом примере выбора предложений логического программирования; однако его можно закодировать в правилах обработки ограничений с использованием расширения, называемого правила обработки дизъюнктивных ограничений или CHR.

Стандартная стратегия оценки логических программ: сверху вниз и в глубину : от цели количество предложений определяется как возможное для доказательства цели и выполняется рекурсия по литералам их тел. Альтернативная стратегия - начать с фактов и использовать предложения для получения новых фактов; эта стратегия называется снизу вверх. Он считается лучшим, чем метод «сверху вниз», когда цель состоит в том, чтобы произвести все последствия данной программы, а не доказывать единственную цель. В частности, поиск всех последствий программы стандартным способом сверху вниз и в глубину может не завершиться, пока не завершится стратегия оценки снизу вверх .

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

A (q). В (Х): - А (Х).

Набор последствий изначально пуст. На первом этапе A (q)является единственным предложением, тело которого может быть доказано (поскольку оно пусто), и поэтому A (q)добавляется к текущему набору последствия. На втором этапе, поскольку A (q)доказано, можно использовать второе предложение, а B (q)добавляется к последствиям. Поскольку никакие другие последствия не могут быть доказаны из {A (q), B (q)}, выполнение прекращается.

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

A (q). В (Х): - А (Х). А (Х): - В (Х).

Например, при оценке всех ответов на цель A (X), стратегия сверху вниз приведет к следующим выводам:

A (q) A ( q): - B (q), B (q): - A (q), A (q) A (q): - B (q), B (q): - A (q), A (q) : -B (q), B (q): - A (q), A (q)

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

Стратегия «снизу вверх» не имеет такого же недостатка, поскольку уже полученные последствия не имеют никакого эффекта. В приведенной выше программе восходящая стратегия начинает добавлять A (q)к набору последствий; на втором этапе B (X): - A (X)используется для получения B (q); на третьем этапе единственными фактами, которые могут быть выведены из безуспешных последствий, это A (q)и B (q), которые, однако, уже входят в набор последствий. В результате останавливается.

В приведенном выше примере единственными используемыми фактами наземные литералы. В общем, каждое предложение, которое содержит только ограничение в теле, считается фактом. Например, предложение A (X): - X>0, X <10также считается фактом. Для этого расширенного определения фактов некоторые факты могут быть эквивалентными, но не синтаксически равными. Например, A (q)эквивалентно A (X): - X = q, и оба эквивалентны A (X): - X = Y, Y = q. Чтобы решить эту проблему, факты переводятся в нормальную форму, в которой заголовок содержит кортеж всех различных чисел; тогда два факта эквивалентны, если их тела эквивалентны по переменным головам, то есть их наборы решений одинаковы при ограничении этим переменными.

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

A (0). А (Х): - Х>0. А (Х): - Х = Y + 1, А (Y).

Восходящий алгоритм устанавливает, что A (X)истинно для X = 0и X>0. На втором этапе первый факт с третьим предложением позволяет получить A (1). На третьем этапе получается A (2)и т. Д. Однако этот факт уже связан с тем фактом, что A (X)истинно для любого неотрицательного X. Этот недостаток можно преодолеть, проверив наличие следствия фактов, которые должны быть добавлены к текущему набору последствий. Если новое последствие уже влечет за собой набор, он не добавляется к нему. Местные факты хранятся в виде предложений, возможно, с «локальными переменными», ограничен по переменным их заголовков.

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

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

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

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

• BProlog
• BNR Prolog (также известный как CLP (BNR))
• Ciao
• CLP (R)
• Распределенный Oz Mozart
• ECLiPSe
• GNU Prolog
• SWI-Prolog

• Dechter, Rina (2003). Обработка ограничений. Морган Кауфманн. ISBN 1-55860-890-7.ISBN 1-55860-890-7
• Апт, Кшиштоф (2003). Принципы программирования ограничений. Издательство Кембриджского университета. ISBN 0-521-82583-0.ISBN 0-521-82583-0
• Marriott, Kim; Питер Дж. Стаки (1998). Программирование с ограничениями: введение. MIT Press. ISBN 0-262-13341-5
• Фрювирт, Том; Слим Абденнадхер (2003). Основы программирования с ограничениями. Springer. ISBN 3-540-67623-6.ISBN 3-540-67623-6
• Джаффар, Джоксан; Майкл Дж. Махер (1994). «Программирование логических ограничений: обзор». Журнал логического программирования. 19/20: 503–581. doi : 10.1016 / 0743-1066 (94) 90033-7.
• Колмерауэр, Ален (1987). «Открытие вселенной Prolog III». Байт. Август.