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

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

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

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

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

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

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

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

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

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

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

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

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

Стабильность дуги

x2 согласован с x3, но не с x1, поскольку значение x2 = 1 не соответствует никакому значению для x1.

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

Например, рассмотрим ограничение, в котором переменные находятся в диапазоне от 1 до 3. Поскольку не может быть 3, в нем нет дуги от 3 до значения, поэтому его можно безопасно удалить. Точно так же никогда не может быть 1, поэтому дуги нет, поэтому ее можно удалить. ${\ Displaystyle х <у}$${\ 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 улучшает по этому алгоритму, игнорируя ограничения, которые не были изменены , так как они в последний раз были проанализированы. В частности, он работает с набором ограничений, который изначально содержит их все; на каждом шаге он устанавливает ограничение и обеспечивает согласованность дуги; если эта операция могла привести к нарушению согласованности дуги по другому ограничению, она помещает его обратно в набор ограничений для анализа. Таким образом, после того, как для ограничения применяется согласованность по дуге, это ограничение не рассматривается снова, если не изменен домен одной из его переменных.

Согласованность пути

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

Согласованность путей - это свойство, подобное согласованности дуг, но учитывает пары переменных, а не только одну. Пара переменных согласована по пути с третьей переменной, если каждую согласованную оценку пары можно распространить на другую переменную таким образом, чтобы выполнялись все двоичные ограничения. Формально и являются путями, согласованными с if, для каждой пары значений, которая удовлетворяет двоичному ограничению между и , существует значение в домене, такое, что и удовлетворяет ограничению между и и между и , соответственно. ${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {k}}$${\ Displaystyle (а, б)}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle c}$${\ displaystyle x_ {k}}$${\ Displaystyle (а, с)}$${\ 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 я \ not = j}$

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

Обычно используется другой тип ограничения 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могут быть выведены из области и наоборот. ${\ 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_ {1} = 2}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {2} = 3}$${\ displaystyle x_ {3}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {3}}$	Обеспечение согласованности направленной дуги начинается с и делает дугу согласованной с ним, удаляя значение . ${\ displaystyle x_ {3}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {2} = 3}$	Обеспечение согласованности направленной дуги продолжается . Поскольку уже был удален, оба и удаляются. ${\ displaystyle x_ {2}}$${\ displaystyle x_ {2} = 3}$${\ displaystyle x_ {1} = 2}$${\ displaystyle x_ {1} = 3}$

Согласованность направленного пути и строгая согласованность направленного пути можно обеспечить с помощью алгоритмов, аналогичных алгоритму согласованности дуги. Они обрабатывают переменные от до ; для каждой переменной рассматриваются две переменные с , и обеспечивается согласованность их пути с . Никакие операции не требуются , если проблема не содержит никаких ограничений на и или нет ограничений между и . Однако, даже если между и нет ограничения , предполагается тривиальное ограничение . Если распространение ограничения сокращает свой набор удовлетворяющих назначений, оно эффективно создает новое нетривиальное ограничение. Ограничение распространения, обеспечивающее строгую согласованность направленного пути, аналогично, но также обеспечивает согласованность дуги. ${\ 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 Х \ обратная косая черта \ {х \}}$${\ 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 к <м}$

Реляционная согласованность также может быть определена для большего количества переменных вместо одной. Набор ограничений является реляционно- согласованным, если каждое согласованное присвоение подмножеству их переменных может быть расширено до оценки для всех переменных, удовлетворяющей всем ограничениям. Это определение не является точным расширением вышеизложенного, поскольку переменные, на которые предполагается распространить оценки, не обязательно входят во все области задействованных ограничений. ${\ displaystyle m}$${\ Displaystyle (я, м)}$${\ 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}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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