Локальная согласованность

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

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

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

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

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

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

На рисунках, использованных в этой статье, отсутствие связей между двумя переменными указывает на то, что между этими двумя переменными либо нет ограничений, либо существует ограничение, удовлетворяемое всеми значениями. ^{[ нужны разъяснения ]}

Локальная согласованность

Все «стандартные» условия локальной согласованности требуют, чтобы все непротиворечивые частичные оценки могли быть расширены на другую переменную таким образом, чтобы результирующее присвоение было непротиворечивым. Частичная оценка является согласованной, если она удовлетворяет всем ограничениям, областью действия которых является подмножество назначенных переменных. ^{[ нужны разъяснения ]}

Согласованность узла

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

Например, если задана переменная $V$ с доменом $\left\{1,2,3,4\right\}$ и ограничение $V\leq 3$ , согласованность узлов ограничит домен до $\left\{1,2,3\right\}$ и тогда ограничение можно было бы отбросить. Этот этап предварительной обработки упрощает последующие этапы.

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

$x_{2}$ соответствует дуге $x_{3}$ но не с $x_{1}$ , как значение $x_{2}=1$ несовместим ни с одним значением для $x_{1}$ .

Переменная задачи удовлетворения ограничений является дугосогласованной с другой, если каждое из ее допустимых значений согласуется с некоторым допустимым значением второй переменной. Формально переменная $x_{i}$ согласуется ли дуга с другой переменной $x_{j}$ если для каждого значения $a$ в области $x_{i}$ существует ценность $b$ в области $x_{j}$ такой, что $(a,b)$ удовлетворяет бинарному ограничению между $x_{i}$ и $x_{j}$ . Проблема является дугосогласованной, если каждая переменная дугосогласована со всеми остальными.

Например, рассмотрим ограничение $x<y$ где переменные варьируются в диапазоне от 1 до 3. Поскольку $x$ никогда не может быть 3, нет дуги от 3 до значения в $y$ поэтому его можно безопасно удалить. Так же, $y$ никогда не может быть 1, поэтому дуги нет, поэтому ее можно удалить.

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

Согласованность дуги обеспечивается удалением 1 из значения x2. В результате x3 больше не соответствует дуге x2, поскольку x3=2 не соответствует значению x2.

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

Распространение ограничений может сделать всю проблему согласованной, если повторить это удаление для всех пар переменных. Возможно, этому процессу придется учитывать данную пару переменных более одного раза. Действительно, удаление значений из области определения переменной может привести к тому, что другие переменные перестанут с ней согласовываться. Например, если $x_{3}$ соответствует дуге $x_{2}$ но алгоритм уменьшает область определения $x_{2}$ , постоянство дуги $x_{3}$ с $x_{2}$ больше не действует и должен быть введен в действие снова.

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

Согласованность пути (k-согласованность)

x1 и x2 не согласованы по пути с x3. Их можно сделать согласованными по пути, удалив синие значения из R12.

Согласованность пути — это свойство, аналогичное согласованности дуги, но учитывает пары переменных, а не только одну. Пара переменных является согласованной по пути с третьей переменной, если каждая непротиворечивая оценка пары может быть расширена на другую переменную таким образом, что все бинарные ограничения будут удовлетворены. Формально, $x_{i}$ и $x_{j}$ соответствуют пути $x_{k}$ если для каждой пары значений $(a,b)$ который удовлетворяет бинарному ограничению между $x_{i}$ и $x_{j}$ , существует значение $c$ в области $x_{k}$ такой, что $(a,c)$ и $(b,c)$ удовлетворить ограничение между $x_{i}$ и $x_{k}$ и между $x_{j}$ и $x_{k}$ , соответственно.

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

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

Обеспечение согласованности пути x1 и x2 с помощью x3 удаляет край сверху. Значения x1 и x2 больше не являются свободными, а связаны новым фактическим ограничением.

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

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

Обобщения

Согласованность дуги и пути можно обобщить на небинарные ограничения, используя кортежи переменных вместо одной или пары. Кортеж из $i-1$ переменные $i$ -совместимо с другой переменной, если каждая непротиворечивая оценка $i-1$ переменные могут быть расширены значением другой переменной, сохраняя при этом согласованность. Это определение очевидным образом распространяется на целые проблемы. Сильный $i$ -согласованность $j$ -согласованность во всем $j\leq i$ .

Частный случай 2-согласованности совпадает с согласованностью дуг (в этой статье все проблемы предполагаются согласованными по узлам). С другой стороны, 3-согласованность совпадает с согласованностью пути, только если все ограничения являются двоичными, поскольку согласованность пути не включает троичные ограничения, в отличие от 3-согласованности.

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

Последовательность и выполнимость

Этот экземпляр является дугосогласованным и не содержит пустых доменов, но не имеет решения. Синие линии обозначают назначения, вызванные выбором x1=1.

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

Действительно, локальная согласованность зависит только от согласованности групп переменных. Например, согласованность дуг гарантирует, что каждое непротиворечивое вычисление переменной может быть последовательно распространено на другую переменную. Однако когда одно значение переменной распространяется на две другие переменные, нет никакой гарантии, что эти два значения согласуются друг с другом. Например, $x_{1}=1$ может соответствовать $x_{2}=1$ и с $x_{3}=1$ , но эти две оценки могут не согласовываться друг с другом.

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

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

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

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

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

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

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

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

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

Ограничение, заставляющее несколько переменных быть разными, обычно записывается $\mathop {\rm {alldifferent}} (x_{1},\ldots ,x_{n})$ или alldifferent([X1,...,Xn]). Это ограничение эквивалентно неравенству всех пар разных переменных, т.е. $x_{i}\not =x_{j}$ для каждого $i\not =j$ . Когда домен переменной уменьшается до одного значения, это значение можно удалить из всех других доменов путем распространения ограничений при обеспечении согласованности дуги. Использование специализированного ограничения позволяет использовать свойства, которые не справедливы для отдельных бинарных неравенств .

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

Другой тип ограничения, который обычно используется, — это cumulative один. Он был введен для решения проблем планирования и размещения. В качестве примера: cumulative([S1,...,Sm], [D1,...,Dm], [R1,...,Rm], L) можно использовать для формализации состояния, в котором существуют m мероприятия, каждое из которых имеет время начала si, продолжительность di и используя сумму ri ресурса. Ограничение гласит, что общий доступный объем ресурсов равен L. Существуют специализированные методы распространения ограничений для кумулятивных ограничений; используются разные методики в зависимости от того, какие переменные домены уже сведены к единому значению.

Третье специализированное ограничение, которое используется в программировании логики ограничений, — это element один. В программировании логики ограничений списки допускаются в качестве значений переменных. Ограничение element(I, L, X) удовлетворен, если L это список и X это I-й элемент этого списка. Для этих ограничений существуют специальные правила распространения ограничений. Например, если L и I сводятся к домену с одним значением, уникальному значению для X можно определить. В более общем смысле, невозможные значения X можно вывести из области $I$ и наоборот.

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

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

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

Экземпляр, который является согласованным по направлению дуги в соответствии с порядком x1 x2 x3, но не согласован по дуге (между x1 и x3 нет ограничений; соответствующие ребра опущены). Каждое значение переменной с более низким индексом соответствует значениям переменных с более высоким индексом. Знаки вопроса указывают на точки, где обратное неверно.

Если алгоритм оценивает переменные в порядке $x_{1},\ldots ,x_{n}$ , согласованность полезна только тогда, когда она гарантирует, что все значения переменных с более низким индексом соответствуют значениям переменных с более высоким индексом.

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

Предполагая, что порядок оценки переменных $x_{1},\ldots ,x_{n}$ , проблема удовлетворения ограничений является направленно согласованной, если каждая переменная $x_{i}$ согласуется ли дуга с любой другой переменной $x_{j}$ такой, что $i<j$ . Согласованность направленного пути аналогична, но есть две переменные. $x_{i},x_{j}$ путь должен соответствовать $x_{z}$ только если $i,j<z$ . Строгая согласованность направленного пути означает согласованность как направленного пути, так и согласованность направленной дуги. Аналогичные определения можно дать и для других форм непротиворечивости.

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

Распространение ограничений, обеспечивающее согласованность направленной дуги, перебирает переменные от последней до первой, обеспечивая на каждом этапе согласованность дуги каждой переменной с меньшим индексом. Если порядок переменных $x_{1},\ldots ,x_{n}$ , этот алгоритм перебирает переменные из $x_{n}$ к $x_{1}$ ; для переменной $x_{j}$ , он обеспечивает согласованность дуг для каждой переменной с индексом ниже, чем $j$ с $x_{j}$ .


Экземпляр, который не соответствует направленной дуге: $x_{1}=2$ не соответствует никакому значению $x_{2}$ и $x_{2}=3$ не соответствует никакому значению $x_{3}$ . Никакого ограничения между $x_{1}$ и $x_{3}$ (соответствующие ребра опущены).	Обеспечение согласованности направленности дуги начинается с $x_{3}$ и делает $x_{2}$ дуга согласуется с ним, удалив значение $x_{2}=3$ .	Обеспечение согласованности направленности дуги осуществляется с помощью $x_{2}$ . С $x_{2}=3$ оба уже удалены $x_{1}=2$ и $x_{1}=3$ удаляются.

Согласованность направленного пути и строгая согласованность направленного пути могут обеспечиваться с помощью алгоритмов, аналогичных алгоритмам согласованности дуги. Они обрабатывают переменные из $x_{n}$ к $x_{1}$ ; для каждой переменной $x_{z}$ две переменные $x_{i},x_{j}$ с $i,j<z$ учитываются, и их согласованность путей с $x_{z}$ соблюдается. Никакой операции не требуется, если задача не содержит ограничений на $x_{i}$ и $x_{z}$ или нет ограничений между $x_{j}$ и $x_{z}$ . Однако даже если между $x_{i}$ и $x_{j}$ , предполагается тривиальный. Если распространение ограничения уменьшает набор удовлетворяющих присваиваний, оно фактически создает новое нетривиальное ограничение. Распространение ограничений, обеспечивающее строгую согласованность направленного пути, аналогично, но также обеспечивает согласованность дуги.

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

Согласованность по направлениям гарантирует, что частичные решения, удовлетворяющие ограничению, могут быть последовательно распространены на другую переменную с более высоким индексом. Однако это не гарантирует, что расширения различных переменных согласуются друг с другом. Например, частичное решение может быть последовательно расширено до переменной $x_{i}$ или в переменную $x_{j}$ , но, тем не менее, эти два расширения несовместимы друг с другом.

Есть два случая, когда этого не происходит, и согласованность по направлениям гарантирует выполнимость, если ни один домен не является пустым и ни одно ограничение не является невыполнимым.

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

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

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

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

Направленная i-согласованность

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

Направленный $i$ -согласованность – это гарантия того, что каждое последовательное присвоение $i-1$ переменные могут быть последовательно расширены до другой переменной, которая находится выше по порядку. Сильная направленность $i$ -согласованность определяется аналогично, но все группы не более $i-1$ учитываются переменные. Если проблема строго направлена $i$ - однородный и имеет ширину менее $i$ и не имеет пустой области или невыполнимых ограничений, у него есть решения.

Любую задачу можно решить строго направленно. $i$ -согласованно, но эта операция может увеличить ширину соответствующих графиков. Процедура распространения ограничений, обеспечивающая согласованность направлений, аналогична процедуре, используемой для согласованности направленной дуги и согласованности пути. Переменные рассматриваются поочередно, от последней к первой по порядку. Для переменной $x_{k}$ , алгоритм рассматривает каждую группу $i-1$ переменные, имеющие индекс ниже, чем $k$ и находятся в ограничении с $x_{k}$ . Согласованность этих переменных с $x_{k}$ проверяется и, возможно, применяется путем удаления удовлетворяющих назначений из ограничения среди всех этих $i$ переменные (если они есть, или создание новых в противном случае).

Обеспечение согласованности для x5 удаляет красную линию, создавая тем самым новое нетривиальное ограничение между x3 и x4. В результате у x4 есть новый родительский элемент x3, помимо x1 и x2. Это изменение увеличивает ширину до 3.

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

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

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

Устранение ведра

Исключение сегментов — это алгоритм выполнимости. Его можно определить как переформулировку адаптивной последовательности. В его определениях используются сегменты, которые являются контейнерами для ограничений, причем каждая переменная имеет связанный сегмент. Ограничение всегда принадлежит сегменту его самой высокой переменной.

Алгоритм исключения корзин поочередно действует от самой высокой к самой низкой переменной. На каждом шаге ограничения в сегментах этой переменной $x_{i}$ считаются. По определению, эти ограничения включают только переменные, которые ниже, чем $x_{i}$ . Алгоритм изменяет ограничение между этими младшими переменными (если оно есть, в противном случае он создает новое). В частности, он обеспечивает возможность распространения их значений на $x_{i}$ в соответствии с ограничениями в сегменте $x_{i}$ . Это новое ограничение, если таковое имеется, затем помещается в соответствующий сегмент. Поскольку это ограничение включает только переменные, которые меньше, чем $x_{i}$ , он добавляется в корзину переменной, которая меньше, чем $x_{i}$ .

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

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

Реляционная согласованность

В то время как предыдущие определения согласованности касаются согласованности присваиваний, реляционная согласованность предполагает удовлетворение только данного ограничения или набора ограничений. Точнее, реляционная согласованность подразумевает, что каждое непротиворечивое частичное присвоение может быть расширено таким образом, чтобы удовлетворялось заданное ограничение или набор ограничений. Формально ограничение $C$ по переменным $X$ является реляционной дугой, согласованной с одной из ее переменных $x$ если каждое последовательное присвоение $X\backslash \{x\}$ может быть расширен до $x$ таким образом $C$ удовлетворен. Разница между «обычным» $i$ согласованность и согласованность реляционной дуги заключается в том, что последняя требует, чтобы расширенное присваивание удовлетворяло только заданному ограничению, тогда как первое требует, чтобы оно удовлетворяло всем соответствующим ограничениям.

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

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

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

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

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

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

Относительная согласованность и выполнимость

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

Первый случай – это сильно реляционный случай. $m$ -постоянная проблема, когда домены содержат не более $m$ элементы. В этом случае последовательная оценка $k$ переменные всегда могут быть расширены до одной другой переменной. Если $x_{1}=a_{1},\ldots ,x_{k}=a_{k}$ это такая оценка и $x_{k+1}$ это переменная, есть только $m$ возможные значения, которые может принимать переменная. Если все такие значения не соответствуют оценке, существуют $m$ (не обязательно уникальные) ограничения, которые нарушаются оценкой, и одно из ее возможных значений. В результате оценка не может быть расширена для удовлетворения всех этих требований. $m$ ограничения -или меньше, нарушающие условие сильных реляционных отношений. $m$ -последовательность.

Второй случай связан с мерой ограничений, а не с областями. Ограничение – это $m$ -плотно, если каждое вычисление касается всех своих переменных, но одна может быть расширена для удовлетворения ограничения либо всеми возможными значениями другой переменной, либо не более чем $m$ своих ценностей. Проблема с $m$ -жесткие ограничения выполнимы тогда и только тогда, когда они строго реляционны. $m+1$ -последовательный.

Выпуклая матрица строк: единицы в каждой строке смежны (между ними нет 0).

Третий случай — это бинарные ограничения, которые могут быть представлены выпуклыми матрицами. Бинарное ограничение может быть представлено двумерной матрицей. $M$ , где $M_{ij}$ равен 0 или 1 в зависимости от того, $i$ -е значение домена $x_{i}$ и $j$ -е значение домена $x_{j}$ удовлетворить ограничение. Строка этой матрицы является выпуклой, если содержащиеся в ней единицы являются последовательными (формально, если два элемента равны 1, все элементы между ними также равны 1). Матрица называется выпуклой по строкам, если все ее строки выпуклые.

Каждая матрица представляет ограничение между x _i и x _{k +1} . Если a ₁ ... a _k являются значениями для x ₁ ... x _k , строки a ₁ ... a _k в каждой матрице указывают допустимые значения для x _{k +1} . Выпуклость строк и сильная согласованность реляционных путей подразумевают существование непротиворечивого значения a _{k +1} для x _{k +1} .

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

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

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

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

Локальная согласованность доказывает выполнимость в некоторых ограниченных случаях (см. Сложность удовлетворения ограничений#Ограничения ). Это относится к некоторым особым видам задач и/или к некоторым видам локальной согласованности. Например, обеспечение согласованности дуг в бинарных ациклических задачах позволяет определить, выполнима ли проблема. Обеспечение строгого направления $i$ -согласованность позволяет определить выполнимость задач, которые вызвали ширину $i-1$ согласно тому же приказу. Адаптивная направленная согласованность позволяет определить выполнимость произвольной задачи.

См. также

Внешние ссылки

Распространение ограничений - диссертация Гвидо Така, дающая хороший обзор теории и проблем реализации.

Ссылки

^ Режен, Жан-Шарль (июль 1994 г.). «Алгоритм фильтрации ограничений различий в CSP» (PDF) . Материалы конференции AAAI . Проверено 16 декабря 2022 г.

Лекутр, Кристоф (2009). Сети ограничений: методы и алгоритмы . ИСТЭ/Уайли. ISBN 978-1-84821-106-3
Дектер, Рина (2003). Обработка ограничений . Морган Кауфманн. ISBN 1-55860-890-7
Апт, Кшиштоф (2003). Принципы программирования в ограничениях . Издательство Кембриджского университета. ISBN 0-521-82583-0
Марриотт, Ким; Питер Дж. Стаки (1998). Программирование с ограничениями: Введение . МТИ Пресс. ISBN 0-262-13341-5

[1] Режен, Жан-Шарль (июль 1994 г.). «Алгоритм фильтрации ограничений различий в CSP» (PDF) . Материалы конференции AAAI . Проверено 16 декабря 2022 г.

[1]