Программирование логики ограничений - Constraint logic programming

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

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

Обзор

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

B(Икс,1):- Икс<0.B(Икс,Y):- Икс=1, Y>0.А(Икс,Y):- Икс>0, B(Икс,Y).

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

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

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

Семантика

Семантика программ логики ограничений может быть определена в терминах виртуального интерпретатора, который поддерживает пару ${displaystyle langle G, Sangle}$ во время исполнения. Первый элемент этой пары называется текущей целью; второй элемент называется хранилищем ограничений. В текущая цель содержит литералы, которые интерпретатор пытается доказать, а также может содержать некоторые ограничения, которые он пытается удовлетворить; то магазин ограничений содержит все ограничения, которые интерпретатор считал выполнимыми до сих пор.

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

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

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

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

Формально семантика программирования логики ограничений определяется в терминах производные. Переход - это пара пар цель / магазин, отмеченная ${displaystyle langle G, Sangle ightarrow langle G ', S'angle}$ . Такая пара заявляет о возможности выхода из состояния ${displaystyle langle G, Sangle}$ заявить ${displaystyle langle G ', S'angle}$ . Такой переход возможен в трех возможных случаях:

элемент $грамм$ это ограничение $C$ , ${displaystyle G '= G ackslash {C}}$ и ${displaystyle S '= Scup {C}}$ ; другими словами, ограничение можно переместить из цели в хранилище ограничений.
элемент $грамм$ это буквальный ${displaystyle L (t_ {1}, ldots, t_ {n})}$ , существует предложение, которое, переписанное с использованием новых переменных, ${displaystyle L (t_ {1} ', ldots, t_ {n}'): - B}$ , ${displaystyle G '}$ является $грамм$ с ${displaystyle L (t_ {1}, ldots, t_ {n})}$ заменен на ${displaystyle t_ {1} = t_ {1} ', ldots, t_ {n} = t_ {n}', B}$ , и ${displaystyle S '= S}$ ; другими словами, литерал может быть заменен телом нового варианта предложения с тем же предикатом в заголовке, добавив к цели тело нового варианта и указанные выше равенства терминов.
$S$ и ${displaystyle S '}$ эквивалентны в соответствии с конкретной семантикой ограничений

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

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

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

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

Попарное равенство членов двух литералов часто компактно обозначают через ${displaystyle L (t_ {1}, ldots, t_ {n}) = L (t_ {1} ', ldots, t_ {n}')}$ : это сокращение для ограничений ${displaystyle t_ {1} = t_ {1} ', ldots, t_ {n} = t_ {n}'}$ . Общий вариант семантики для программирования логики ограничений добавляет ${displaystyle L (t_ {1}, ldots, t_ {n}) = L (t_ {1} ', ldots, t_ {n}')}$ непосредственно в хранилище ограничений, а не в цель.

Условия и положения

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

Условия дерева

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

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

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

В этой форме удовлетворения ограничений значения переменных являются терминами.

Реалы

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

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

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

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

Конечные домены

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

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

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

Хранилище ограничений

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

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

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

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

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

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

Маркировка

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

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

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

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

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

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

Переформулировки программы

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

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

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

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

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

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

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

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

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

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

Оценка снизу вверх

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

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

A (q) .B (X): - A (X).

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

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

A (q) .B (X): - A (X) .A (X): - B (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)

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

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

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

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

А(0).А(Икс):-Икс>0.А(Икс):-Икс=Y+1, А(Y).

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

Программирование логики параллельных ограничений

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

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

Приложения

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

История

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

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

BProlog
BNR Prolog (также известный как CLP (BNR))
Чао
CLP (R)
Распространенный Оз Моцарт
Затмение
GNU Prolog
SWI-Prolog