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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обобщения

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

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

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

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

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

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

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

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

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

1. обеспечение согласованности дуг устанавливает выполнимость задач, составленных из бинарных ограничений без циклов ( дерево бинарных ограничений);
2. обеспечение согласованности путей устанавливает выполнимость бинарных ограничений (возможно, с циклами) с бинарными доменами;
3. Обеспечение строгой согласованности устанавливает выполнимость задач, содержащих переменные. ${\displaystyle n}$ ${\displaystyle n}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Направленная i-консистенция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Распространение единиц
• Программирование ограничений
• Программирование логики ограничений
• Взгляд вперед (возврат)

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

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

Ссылки

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

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