Введение

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

Предположения

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

Местная согласованность

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

Соответствие узлов

Согласованность узлов требует, чтобы каждое унарное ограничение на переменную удовлетворялось всеми значениями в области значений этой переменной, и наоборот. Это условие можно тривиально обеспечить, сократив область значений каждой переменной до значений, удовлетворяющих всем унарным ограничениям для этой переменной. В результате унарные ограничения можно игнорировать, предполагая, что они уже учтены в областях значений. Например, для переменной с областью значений {1, 2, 3, 4, 5} и ограничения x > 2, согласованность узлов ограничит область значений до {3, 4, 5}, и это ограничение можно будет отбросить. Этот этап предварительной обработки упрощает последующие стадии.

Консистенция дуги

Переменная задачи удовлетворения ограничений является дугово согласованной с другой, если каждое из её допустимых значений согласовано с некоторым допустимым значением второй переменной. Формально, переменная дугово согласована с другой переменной , если для каждого значения в области существует значение в области такое, что удовлетворяет бинарному ограничению между и . Задача является дугово согласованной, если каждая переменная дугово согласована с каждой другой. Например, рассмотрим ограничение , где переменные принимают значения из области от 1 до 3. Поскольку никогда не может быть 3, дуги от 3 к значению в не существует, поэтому его можно безопасно удалить. Аналогично, никогда не может быть 1, поэтому дуги нет, и его также можно удалить. Дуговая согласованность также может быть определена относительно конкретного бинарного ограничения: бинарное ограничение является дугово согласованным, если для каждого значения одной переменной существует значение второй переменной, удовлетворяющее этому ограничению. Это определение дуговой согласованности аналогично вышеприведенному, но дано для конкретного ограничения. Это различие особенно важно для ненормализованных задач, где вышеуказанное определение учитывает все ограничения между двумя переменными, а это – только конкретное. Если переменная не дугово согласована с другой, её можно сделать таковой, удалив некоторые значения из её области. Это форма распространения ограничений, обеспечивающая дуговую согласованность: она удаляет из области переменной каждое значение, которое не соответствует значению другой переменной. Это преобразование сохраняет решения задачи, поскольку удаленные значения в любом случае не входят ни в одно решение. Распространение ограничений может сделать всю задачу дугово согласованной, повторяя это удаление для всех пар переменных. В этом процессе может потребоваться рассмотреть данную пару переменных более одного раза. Действительно, удаление значений из области переменной может привести к тому, что другие переменные перестанут быть с ней дугово согласованными. Например, если дугово согласована с , но алгоритм уменьшает область , дуговая согласованность с больше не выполняется и должна быть восстановлена. Простой алгоритм циклически перебирает пары переменных, обеспечивая дуговую согласованность, повторяя цикл до тех пор, пока ни одна область не изменится за полный цикл. Алгоритм AC-3 улучшает этот алгоритм, игнорируя ограничения, которые не были изменены с момента последнего анализа. В частности, он работает с набором ограничений, который изначально содержит все ограничения; на каждом шаге он берет ограничение и обеспечивает дуговую согласованность; если эта операция могла привести к нарушению дуговой согласованности для другого ограничения, он помещает это ограничение обратно в набор для анализа. Таким образом, как только дуговая согласованность наложена на ограничение, оно больше не рассматривается, если домен одной из его переменных не был изменен.

Консистенция пути (консистенция k)

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

Обобщения

Арковая и последовательность по путям могут быть обобщены на небинарные ограничения, используя кортежи переменных вместо одной или пары. Кортеж переменных считается согласованным с другой переменной, если любая согласованная оценка переменных может быть расширена значением этой другой переменной с сохранением согласованности. Это определение распространяется на всю задачу очевидным образом. Сильная согласованность – это согласованность для всех. Частный случай согласованности 2 совпадает с арковой согласованностью (в данной статье предполагается, что все задачи узлово согласованны). С другой стороны, согласованность 3 совпадает с последовательностью по путям только в том случае, если все ограничения бинарны, поскольку последовательность по путям не включает троичные ограничения, а согласованность 3 – включает. Другой способ обобщения арковой согласованности – гипер-арковая или обобщенная арковая согласованность, которая требует возможности расширения одной переменной для удовлетворения ограничения. А именно, переменная гипер-арково согласована с ограничением, если каждое значение этой переменной может быть расширено до других переменных ограничения таким образом, чтобы ограничение было выполнено.

Особые случаи

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

Специализированные ограничения

Обычно используются некоторые виды ограничений. Например, часто используется ограничение, что некоторые переменные все различны. Существуют эффективные специализированные алгоритмы для обеспечения согласованности дуг для таких ограничений. Ограничение, требующее, чтобы несколько переменных были различными, обычно записывается как `alldifferent([X1, ..., Xn])`. Это ограничение эквивалентно неравенству всех пар различных переменных, то есть для каждой пары. Когда область переменной сокращается до единственного значения, это значение можно исключить из всех остальных областей посредством распространения ограничений при обеспечении согласованности дуг. Использование специализированного ограничения позволяет использовать свойства, которые не применимы к отдельным бинарным неравенствам. Первое свойство заключается в том, что общее количество элементов в областях всех переменных должно быть не меньше числа переменных. Более точно, после обеспечения согласованности дуг, число необработанных переменных не должно превышать число значений в объединении их областей. В противном случае ограничение не может быть удовлетворено. Это условие легко проверить для ограничения в форме `alldifferent`, но оно не соответствует согласованности дуг сети неравенств. Второе свойство единственного ограничения `alldifferent` заключается в том, что гиперсогласованность дуг может быть эффективно проверена с использованием алгоритма поиска максимального двудольного соответствия. В частности, строится граф, в котором переменные и значения являются двумя множествами узлов, и на нем запускается специализированный алгоритм поиска двудольного соответствия для проверки существования такого соответствия. Другой вид ограничения, который часто используется, – кумулятивное. Оно было введено для задач планирования и размещения. Например, `cumulative([S1, ..., Sm], [D1, ..., Dm], [R1, ..., Rm], L)` можно использовать для формализации условия, при котором существует m видов деятельности, каждая из которых имеет время начала si, длительность di и потребляет количество ресурса ri. Ограничение указывает, что общее количество доступных ресурсов равно L. Существуют специализированные методы распространения ограничений для кумулятивных ограничений; различные методы используются в зависимости от того, области каких переменных уже сведены к единственному значению. Третье специализированное ограничение, используемое в логическом программировании с ограничениями, – это ограничение `element`. В логическом программировании со списками списки допускаются в качестве значений переменных. Ограничение `element(I, L, X)` выполняется, если L – это список, а X – это I-й элемент этого списка. Существуют специализированные правила распространения ограничений для этих ограничений. Например, если L и I сведены к единственной области значений, можно определить единственное значение для X. В более общем случае, из области L и I можно вывести невозможные значения X, и наоборот.

Направленная последовательность

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

Консистенция направленной дуги и траектории

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

Распространение ограничений для согласованности дуги и траектории

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

Направленная согласованность и удовлетворительность

Направленная согласованность гарантирует, что частичные решения, удовлетворяющие ограничению, могут быть последовательно расширены до другой переменной с более высоким индексом. Однако это не гарантирует, что расширения для разных переменных согласованы друг с другом. Например, частичное решение может быть последовательно расширено до переменной или до переменной , но при этом эти два расширения могут быть не согласованы. Существует два случая, когда этого не происходит, и направленная согласованность гарантирует выполнимость, если ни одна область не пуста и ни одно ограничение не является невыполнимым. Первый случай – это задача с бинарными ограничениями, имеющая упорядочение переменных, которое делает упорядоченный граф ограничений шириной 1. Такое упорядочение существует тогда и только тогда, когда граф ограничений является деревом. Если это так, то ширина графа ограничивает максимальное количество нижних (в соответствии с упорядочением) узлов, к которым соединен узел. Направленная дуговая согласованность гарантирует, что любое согласованное присваивание переменной может быть расширено до более высоких узлов, а ширина 1 гарантирует, что узел соединен не более чем с одним нижним узлом. В результате, как только нижняя переменная присвоена, ее значение может быть последовательно расширено на каждую более высокую переменную, с которой она соединена. Это расширение впоследствии не может привести к противоречию. Действительно, ни одна другая нижняя переменная не соединена с этой высшей переменной, поскольку ширина графа равна 1. Следовательно, если задача с ограничениями имеет ширину 1 относительно упорядочения ее переменных (что подразумевает, что соответствующий граф является деревом), и задача направленно дуговая согласованность относительно того же упорядочения, решение (если оно существует) может быть найдено путем итеративного присваивания переменных в соответствии с упорядочением. Второй случай, в котором направленная согласованность гарантирует выполнимость, если ни одна область не пуста и ни одно ограничение не является невыполнимым, – это задачи с бинарными ограничениями, граф которых имеет индуцированную ширину 2, с использованием сильной направленной согласованности по путям. Действительно, эта форма согласованности гарантирует, что любое присваивание переменной или паре переменных может быть расширено до более высокой переменной, а ширина 2 гарантирует, что эта переменная не соединена с другой парой нижних переменных. Причина, по которой рассматривается индуцированная ширина вместо ширины, заключается в том, что обеспечение направленной согласованности по путям может добавить ограничения. Действительно, если две переменные не находятся в одном и том же ограничении, но находятся в ограничении с более высокой переменной, некоторые пары их значений могут нарушать согласованность по путям. Удаление таких пар создает новое ограничение. В результате распространение ограничений может привести к задаче, граф которой имеет больше ребер, чем исходный. Однако все эти ребра обязательно находятся в индуцированном графе, поскольку они все соединяют двух родителей одного узла. Ширина 2 гарантирует, что любая согласованная частичная оценка может быть расширена до решения, но эта ширина относится к сгенерированному графу. Следовательно, для сильной направленной согласованности по путям требуется индуцированная ширина 2, чтобы гарантировать существование решений.

Показатель направленности i-согласованности

Направленная согласованность – это гарантия того, что любое последовательное назначение переменным может быть последовательно расширено на другую переменную, имеющую более высокий порядок. Сильная направленная согласованность определяется аналогичным образом, но рассматриваются все группы переменных, состоящие максимум из заданного числа переменных. Если задача сильно направленно согласована, имеет ширину меньше *k* и не содержит пустых областей или неудовлетворимых ограничений, то она имеет решение. Любую задачу можно сделать сильно направленно согласованной, но эта операция может увеличить ширину соответствующих графов. Процедура распространения ограничений, обеспечивающая направленную согласованность, аналогична процедуре, используемой для направленной согласованности дуг и согласованности путей. Переменные рассматриваются последовательно, от последней до первой в соответствии с заданным порядком. Для переменной *i* алгоритм рассматривает каждую группу из *m* переменных, имеющих индекс меньше *i* и находящихся в ограничении с переменной *i*. Проверяется и, возможно, обеспечивается согласованность этих переменных с переменной *i* путем удаления допустимых назначений из ограничения среди всех этих *m* переменных (если таковые имеются) или добавления нового ограничения. Эта процедура генерирует сильно направленно согласованный экземпляр. Однако она также может добавить новые ограничения к экземпляру. В результате, даже если ширина исходной задачи равна *k*, ширина полученного экземпляра может быть больше. Если это так, то сильная направленная согласованность не гарантирует выполнимость, даже если ни одна область не пуста и ни одно ограничение не является неудовлетворимым. Однако распространение ограничений добавляет ограничения только к переменным, имеющим индекс меньше, чем у текущей переменной. Следовательно, никакое ограничение, связанное с переменной, не изменяется и не добавляется после того, как алгоритм обработал эту переменную. Вместо рассмотрения фиксированного *m*, его можно изменить на количество родителей каждой рассматриваемой переменной (родителями переменной являются переменные с меньшим индексом, чем у данной переменной, и находящиеся в ограничении с ней). Это соответствует рассмотрению всех родителей данной переменной на каждом шаге. Иными словами, для каждой переменной *i* от последней до первой все ее родители включаются в новое ограничение, которое ограничивает их значения теми, которые согласованы с переменной *i*. Поскольку этот алгоритм можно рассматривать как модификацию предыдущего, в котором значение *m* изменяется на количество родителей каждого узла, он называется адаптивной согласованностью. Этот алгоритм обеспечивает сильную направленную согласованность, где *m* равно индуцированной ширине задачи. Полученный экземпляр выполним тогда и только тогда, когда ни одна область или ограничение не становятся пустыми. Если это так, решение можно легко найти, итеративно устанавливая неназначенной переменной произвольное значение и распространяя эту частичную оценку на другие переменные. Этот алгоритм не всегда выполняется за полиномиальное время, поскольку количество ограничений, введенных при обеспечении сильной направленной согласованности, может привести к экспоненциальному увеличению размера. Однако задача может быть решена за полиномиальное время, если обеспечение сильной направленной согласованности не увеличивает размер экземпляра сверхполиномиально. Следовательно, если экземпляр имеет индуцированную ширину, ограниченную константой, его можно решить за полиномиальное время.

Удаление из ковша

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

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

Относительная последовательность

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

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

Относительная согласованность и удовлетворительность

Проблема удовлетворения ограничений может быть реляционно согласованной, не иметь пустых доменов или неудовлетворимых ограничений, и тем не менее быть неудовлетворимой. Однако существуют случаи, когда это невозможно. Первый случай – это сильно реляционно согласованная проблема, когда домены содержат не более элементов. В этом случае согласованная оценка переменных всегда может быть расширена до другой одной переменной. Если это такая оценка, а это переменная, то существует только возможных значений, которые может принимать переменная. Если все эти значения несовместимы с оценкой, то существует (не обязательно уникальных) ограничений, которые нарушаются оценкой и одним из ее возможных значений. В результате оценка не может быть расширена для удовлетворения всем этим или меньшему числу ограничений, что нарушает условие сильной реляционной согласованности. Второй случай связан с мерой ограничений, а не с доменами. Ограничение является жестким, если любая оценка всех его переменных, кроме одной, может быть расширена для удовлетворения ограничению либо всеми возможными значениями другой переменной, либо не более чем ее значениями. Проблемы с жесткими ограничениями разрешимы тогда и только тогда, когда они сильно реляционно согласованны. Третий случай – это бинарные ограничения, которые могут быть представлены рядово-выпуклыми матрицами. Бинарное ограничение может быть представлено двумерной матрицей , где 0 или 1 в зависимости от того, удовлетворяют ли ограничению -е значение домена и -е значение домена . Ряд этой матрицы является выпуклым, если содержащиеся в нем 1 последовательны (формально, если два элемента равны 1, то все элементы между ними также равны 1). Матрица является рядово-выпуклой, если все ее ряды выпуклые. Условие, при котором сильная реляционная согласованность по пути эквивалентна разрешимости, заключается в проблемах удовлетворения ограничений, для которых существует порядок переменных, при котором все ограничения могут быть представлены рядово-выпуклыми матрицами. Этот результат основан на том факте, что набор выпуклых рядов, имеющих общий элемент попарно, также имеет глобально общий элемент. Рассматривая оценку по переменным, допустимые значения для -й переменной определяются путем выбора некоторых рядов из некоторых ограничений. В частности, для каждой переменной из числа , ряд, соответствующий ее значению в матрице, представляющей ограничение, связывающее ее с -й переменной, представляет допустимые значения последней. Поскольку эти ряды выпуклые и имеют общий элемент попарно из-за согласованности по пути, они также имеют общий общий элемент, который представляет значение последней переменной, согласованное с остальными.

Использование локальной согласованности

Все формы локальной согласованности могут быть обеспечены распространением ограничений, которое может уменьшить области значений переменных и множества допустимых назначений, удовлетворяющих ограничению, а также ввести новые ограничения. Если распространение ограничений приводит к пустому домену или неудовлетворимому ограничению, исходная задача неудовлетворима. Следовательно, все формы локальной согласованности могут использоваться как приближения к проверяемости на выполнимость. Более точно, они могут использоваться как неполные алгоритмы доказательства неудовлетворимости, поскольку они могут доказать неудовлетворимость задачи, но, как правило, не могут доказать её выполнимость. Такие приближенные алгоритмы могут использоваться алгоритмами поиска (с возвратом, с возвратом и переходом, локальным поиском и т.д.) в качестве эвристик для определения возможности расширения частичного решения до полного, удовлетворяющего всем ограничениям, без дальнейшего анализа. Даже если распространение ограничений не приводит к пустому домену или неудовлетворимому ограничению, оно все же может уменьшить области значений или усилить ограничения. В этом случае пространство поиска задачи сокращается, что уменьшает объем поиска, необходимый для её решения. Локальная согласованность доказывает выполнимость в некоторых ограниченных случаях (см. Сложность задачи об удовлетворении ограничений#Ограничения). Это справедливо для некоторых специальных типов задач и/или некоторых видов локальной согласованности. Например, обеспечение согласованности по дугам для бинарных ациклических задач позволяет определить, выполнима ли задача. Обеспечение строгой направленной согласованности позволяет определить выполнимость задач, имеющих индуцированную ширину в соответствии с тем же порядком. Адаптивная направленная согласованность позволяет определить выполнимость произвольной задачи.