В удовлетворении ограничений , местные непротиворечивости условие является свойство задач удовлетворения ограничений , связанных с последовательностью подмножеств переменных или ограничений. Их можно использовать для уменьшения пространства поиска и облегчения решения проблемы. Различные виды местных условий согласования заемных средств, в том числе последовательности узлов , консистенции дуги и консистенции пути .
Каждое условие локальной согласованности может быть усилено преобразованием, которое изменяет проблему без изменения ее решений. Такое преобразование называется распространением ограничений . Распространение ограничений работает за счет сокращения областей переменных, усиления ограничений или создания новых. Это приводит к сокращению пространства поиска, что упрощает решение проблемы с помощью некоторых алгоритмов. Распространение ограничений также может использоваться как средство проверки на неудовлетворенность, неполное в целом, но полное в некоторых частных случаях.
Условия локальной согласованности можно сгруппировать по различным классам. Исходные условия локальной согласованности требуют, чтобы каждое согласованное присвоение можно было последовательно расширить до другой переменной. Направленная согласованность требует, чтобы это условие выполнялось только тогда, когда другая переменная выше, чем переменная в присвоении, в соответствии с заданным порядком. Реляционная согласованность включает расширения для нескольких переменных, но это расширение требуется только для удовлетворения заданного ограничения или набора ограничений.
Предположения
В этой статье проблема удовлетворения ограничений определяется как набор переменных, набор областей и набор ограничений. Переменные и домены связаны: домен переменной содержит все значения, которые может принимать переменная. Ограничение состоит из последовательности переменных, называемых его областью действия, и набора их оценок, которые являются оценками, удовлетворяющими ограничению.
Предполагается, что проблемы удовлетворения ограничений, упомянутые в этой статье, имеют особую форму. Проблема находится в нормализованной форме , соответственно в регулярной форме , если каждая последовательность переменных является областью действия не более одного ограничения или ровно одного ограничения. Предположение о регулярности, сделанное только для двоичных ограничений, приводит к стандартизированной форме . Эти условия всегда можно обеспечить, объединив все ограничения последовательности переменных в одну и / или добавив ограничение, которому удовлетворяют все значения последовательности переменных.
На рисунках, использованных в этой статье, отсутствие связей между двумя переменными указывает на то, что между этими двумя переменными не существует ограничений или ограничений, удовлетворяющих всем значениям. [ требуется разъяснение ]
Локальная согласованность
Все «стандартные» условия локальной согласованности требуют, чтобы все согласованные частичные оценки могли быть расширены до другой переменной таким образом, чтобы результирующее присвоение было согласованным. Частичная оценка является непротиворечивой, если она удовлетворяет всем ограничениям, объем которых является подмножеством присвоенных переменных. [ требуется разъяснение ]
Согласованность узлов
Согласованность узлов требует, чтобы каждое унарное ограничение на переменную удовлетворялось всеми значениями в области определения переменной, и наоборот. Это условие можно тривиально выполнить, уменьшив область определения каждой переменной до значений, которые удовлетворяют всем унарным ограничениям на эту переменную. В результате унарными ограничениями можно пренебречь и считать, что они включены в домены.
Например, учитывая переменную с доменом и ограничение , согласованность узлов ограничит домен и тогда ограничение можно было бы отбросить. Этот этап предварительной обработки упрощает последующие этапы.
Стабильность дуги
Переменная в задаче удовлетворения ограничений является дуговой согласованной с другой, если каждое из ее допустимых значений согласовано с некоторым допустимым значением второй переменной. Формально переменная согласовано с другой переменной если для каждого значения в области существует ценность в области такой, что удовлетворяет двоичному ограничению между а также . Проблема является дуговой согласованной, если каждая переменная согласована по дуге со всеми остальными.
Например, рассмотрим ограничение где переменные находятся в диапазоне от 1 до 3. Поскольку никогда не может быть 3, нет дуги от 3 до значения в так что безопасно удалить. Так же, никогда не может быть 1, поэтому дуги нет, поэтому ее можно удалить.
Согласованность по дуге также может быть определена относительно конкретного двоичного ограничения: двоичное ограничение согласовано с дугой, если каждое значение одной переменной имеет значение второй переменной, так что они удовлетворяют ограничению. Это определение согласованности дуги аналогично приведенному выше, но дается для конкретного ограничения. Это различие особенно актуально для ненормализованных задач, где в приведенном выше определении учитываются все ограничения между двумя переменными, а в этом - только конкретная.
Если переменная не согласуется с другой, это можно сделать так, удалив некоторые значения из ее домена. Это форма распространения ограничений, которая обеспечивает согласованность дуги: она удаляет из области определения переменной каждое значение, которое не соответствует значению другой переменной. Это преобразование поддерживает решения проблемы, поскольку удаленные значения в любом случае не являются решением.
Распространение ограничений может сделать всю дугу задачи согласованной, повторив это удаление для всех пар переменных. В этом процессе может потребоваться рассмотреть данную пару переменных более одного раза. В самом деле, удаление значений из области определения переменной может привести к тому, что другие переменные больше не будут согласованы с ней. Например, если соответствует ли дуга но алгоритм уменьшает область , дуговая консистенция с участием больше не действует и требует повторного выполнения.
Упрощенный алгоритм будет перебирать пары переменных, обеспечивая согласованность по дуге, повторяя цикл до тех пор, пока в течение всего цикла не изменится ни одна область. Алгоритм AC-3 улучшает по этому алгоритму, игнорируя ограничения, которые не были изменены , так как они в последний раз были проанализированы. В частности, он работает с набором ограничений, который изначально содержит их все; на каждом шаге он устанавливает ограничение и обеспечивает согласованность по дуге; если эта операция могла привести к нарушению согласованности дуги по другому ограничению, она помещает его обратно в набор ограничений для анализа. Таким образом, после того, как для ограничения применяется согласованность по дуге, это ограничение не рассматривается снова, если не изменен домен одной из его переменных.
Согласованность пути
Согласованность путей - это свойство, аналогичное согласованности дуг, но учитывает пары переменных, а не только одну. Пара переменных согласована по пути с третьей переменной, если каждую согласованную оценку пары можно распространить на другую переменную таким образом, чтобы выполнялись все двоичные ограничения. Формально, а также путь согласуется с если для каждой пары значений который удовлетворяет двоичному ограничению между а также , существует значение в области такой, что а также удовлетворить ограничение между а также и между а также , соответственно.
Форма распространения ограничения, обеспечивающая согласованность пути, работает путем удаления некоторого удовлетворительного назначения из ограничения. Действительно, согласованность пути может быть обеспечена путем удаления из двоичного ограничения всех оценок, которые не могут быть распространены на другую переменную. Что касается согласованности дуги, при этом удалении, возможно, придется учитывать двоичное ограничение более одного раза. Что касается согласованности дуги, результирующая проблема имеет те же решения, что и исходная, поскольку удаленные значения не являются решением.
Форма распространения ограничений, обеспечивающая согласованность пути, может вводить новые ограничения. Когда две переменные не связаны двоичным ограничением, они фактически связаны ограничением, допускающим любую пару значений. Однако некоторая пара значений может быть удалена путем распространения ограничения. Результирующее ограничение больше не удовлетворяется всеми парами значений. Следовательно, это больше не виртуальное, тривиальное ограничение.
Название «согласованность путей» происходит от исходного определения, которое включало пару переменных и путь между ними, а не пару и одну переменную. Хотя эти два определения различны для одной пары переменных, они эквивалентны, когда относятся ко всей проблеме.
Обобщения
Согласованность дуги и пути можно обобщить на небинарные ограничения, используя кортежи переменных вместо одной или пары. Кортеж переменные -соответствует другой переменной, если каждая последовательная оценка переменные могут быть расширены значением другой переменной при сохранении согласованности. Это определение очевидным образом распространяется на все проблемы. Сильный-согласованность -согласованность для всех .
Частный случай 2-непротиворечивости совпадает с дуговой непротиворечивостью (в этой статье все задачи считаются узловыми). С другой стороны, 3-согласованность совпадает с согласованностью пути только в том случае, если все ограничения являются двоичными, потому что согласованность пути не включает тройных ограничений, в то время как 3-согласованность делает.
Другой способ обобщения согласованности дуги - это согласованность по гипер-дуге или обобщенная согласованность по дуге , которая требует расширяемости одной переменной для удовлетворения ограничению. А именно, переменная является гипер-дугой, согласованной с ограничением, если каждое значение переменной может быть расширено до других переменных ограничения таким образом, чтобы ограничение удовлетворялось.
Последовательность и выполнимость
Распространение ограничения (обеспечение некоторой формы локальной согласованности) может привести к пустому домену или невыполнимому ограничению. В этом случае у проблемы нет решения. Обратное неверно в целом: несогласованный экземпляр может быть согласованным по дуге или по пути, не имея при этом пустой области или невыполнимых ограничений.
В самом деле, локальная согласованность относится только к согласованности групп переменных. Например, согласованность дуги гарантирует, что каждое последовательное вычисление переменной может быть последовательно распространено на другую переменную. Однако, когда одно значение переменной расширяется до двух других переменных, нет гарантии, что эти два значения согласованы друг с другом. Например, может соответствовать и с , но эти две оценки могут не согласовываться друг с другом.
Однако в некоторых случаях для доказательства выполнимости можно использовать распространение ограничений. Набор двоичных ограничений, согласованный по дуге и не имеющий пустой области, может быть несовместимым, только если сеть ограничений содержит циклы. В самом деле, если ограничения являются двоичными и образуют ациклический граф, значения всегда можно распространить по ограничениям: для каждого значения переменной все переменные в ограничении с ним имеют значение, удовлетворяющее этому ограничению. В результате решение может быть найдено путем итеративного выбора неназначенной переменной и рекурсивного распространения по ограничениям. Этот алгоритм никогда не пытается присвоить значение уже назначенной переменной, поскольку это подразумевает наличие циклов в сети ограничений.
Аналогичное условие выполняется для согласованности путей. Ниже перечислены частные случаи, в которых выполнимость может быть установлена путем обеспечения согласованности дуги и согласованности путей.
- обеспечение согласованности дуги устанавливает выполнимость задач, состоящих из бинарных ограничений без циклов ( дерево бинарных ограничений);
- обеспечение согласованности путей устанавливает выполнимость бинарных ограничений (возможно, с циклами) с бинарными доменами;
- обеспечение сильного последовательность устанавливает выполнимость проблем, содержащих переменные.
Особые случаи
Некоторые определения или результаты об относительной непротиворечивости применимы только в особых случаях.
Когда домены состоят из целых чисел , может быть определена связанная согласованность. Эта форма согласованности основана на согласованности крайних значений доменов, то есть минимальных и максимальных значений, которые может принимать переменная.
Когда ограничения являются алгебраическими или булевыми , согласованность дуги эквивалентна добавлению нового ограничения или синтаксическому изменению старого, и это может быть сделано путем составления соответствующих ограничений.
Специализированные ограничения
Обычно используются некоторые виды ограничений. Например, часто используется ограничение, заключающееся в том, что некоторые переменные все разные. Существуют эффективные специализированные алгоритмы для обеспечения согласованности дуги при таких ограничениях.
Ограничение, заставляющее ряд переменных отличаться, обычно записывается или alldifferent([X1,...,Xn])
. Это ограничение эквивалентно неравенству всех пар разных переменных, то есть для каждого . Когда домен переменной сокращается до одного значения, это значение может быть удалено из всех других доменов путем распространения ограничений при обеспечении согласованности дуги. Использование специального ограничения позволяет использовать свойства, которые не выполняются для отдельных двоичных неравенств .
Первое свойство состоит в том, что общее количество элементов в доменах всех переменных должно быть не меньше количества переменных. Точнее, после обеспечения согласованности дуги количество неназначенных переменных не должно превышать количество значений в объединении их доменов. В противном случае ограничение не может быть выполнено. Это условие легко проверяется на ограничении в 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
могут быть выведены из области и наоборот.
Направленная согласованность
Направленная согласованность - это вариант дуги, пути и -согласованность, адаптированная для использования алгоритмом, который присваивает значения переменным в соответствии с заданным порядком переменных. Они аналогичны своим ненаправленным аналогам, но требуют только, чтобы согласованное присвоение некоторым переменным могло быть последовательно расширено на другую переменную, которая больше, чем они, в соответствии с порядком.
Направленная дуга и согласованность пути
Если алгоритм оценивает переменные в порядке , согласованность полезна только тогда, когда она гарантирует, что все значения переменных с более низким индексом согласуются со значениями переменных с более высоким индексом.
При выборе значения для переменной значениями, несовместимыми со всеми значениями неназначенной переменной, можно пренебречь. В самом деле, даже если все эти значения согласуются с текущей частичной оценкой, алгоритм позже не сможет найти согласованное значение для неназначенной переменной. С другой стороны, обеспечение согласованности с переменными, которые уже оцениваются, не обязательно: если алгоритм выбирает значение, несовместимое с текущей частичной оценкой, несогласованность обнаруживается в любом случае.
Предполагая, что порядок оценки переменных равен , проблема удовлетворения ограничений является направленно-дуговой согласованной, если каждая переменная согласуется ли дуга с любой другой переменной такой, что . Согласованность направленного пути аналогична, но две переменные должен соответствовать пути только если . Сильная согласованность направленного пути означает согласованность как направленного пути, так и согласованности направленной дуги. Аналогичные определения могут быть даны для других форм согласованности.
Распространение ограничений для согласованности дуги и пути
Распространение ограничения, обеспечивающее согласованность направленной дуги, выполняет итерацию по переменным от последней к первой, обеспечивая на каждом шаге согласованность дуги каждой переменной с более низким индексом. Если порядок переменных, этот алгоритм перебирает переменные из к ; для переменной, он обеспечивает согласованность по дуге каждой переменной с индексом ниже, чем с участием .
Экземпляр, который не соответствует направленной дуге: не соответствует никакому значению а также не соответствует никакому значению . Между а также (соответствующие ребра опускаются). | Обеспечение согласованности направленной дуги начинается с , и делает дуга согласуется с ним, удаляя значение . | Обеспечение согласованности направленной дуги выполняется с помощью . С уже удалено, оба а также удалены. |
Согласованность направленного пути и строгая согласованность направленного пути могут быть обеспечены с помощью алгоритмов, аналогичных алгоритму согласованности дуги. Они обрабатывают переменные из к ; для каждой переменной две переменные с участием учитываются, и согласованность пути их с принудительно. Никаких операций не требуется, если проблема не содержит ограничения на а также или нет ограничений между а также . Однако даже если между а также , предполагается тривиальный. Если распространение ограничения сокращает набор удовлетворяющих назначений, оно эффективно создает новое нетривиальное ограничение. Распространение ограничений, обеспечивающее строгую согласованность направленного пути, аналогично, но также обеспечивает согласованность дуги.
Направленная последовательность и выполнимость
Направленная согласованность гарантирует, что частичные решения, удовлетворяющие ограничению, могут быть последовательно расширены до другой переменной с более высоким индексом. Однако это не гарантирует, что расширения различных переменных совместимы друг с другом. Например, частичное решение может быть последовательно расширено до переменной или изменить , но все же эти два расширения не согласуются друг с другом.
Есть два случая, когда этого не происходит, и согласованность по направлениям гарантирует выполнимость, если ни один домен не является пустым и никакое ограничение не является невыполнимым.
Первый случай - это проблема бинарных ограничений с упорядочением переменных, которое делает упорядоченный граф ограничений шириной 1. Такой порядок существует тогда и только тогда, когда граф ограничений является деревом. В этом случае ширина графа ограничивает максимальное количество нижних (в соответствии с порядком) узлов, к которым присоединяется узел. Согласованность направленной дуги гарантирует, что каждое согласованное присвоение переменной может быть расширено на более высокие узлы, а ширина 1 гарантирует, что узел не присоединен более чем к одному нижнему узлу. В результате, как только нижняя переменная присвоена, ее значение может быть последовательно расширено на каждую более высокую переменную, с которой она связана. Это расширение не может впоследствии привести к несогласованности. Действительно, никакая другая более низкая переменная не присоединяется к этой более высокой переменной, поскольку ширина графика равна 1.
В результате, если проблема ограничения имеет ширину 1 относительно упорядочения ее переменных (что означает, что соответствующий ей граф является деревом) и проблема является направленно-дуговой согласованной относительно того же порядка, решение (если таковое имеется) можно найти путем итеративного присвоения переменных в соответствии с порядком.
Второй случай, в котором согласованность по направлениям гарантирует выполнимость, если ни одна область не пуста и ни одно ограничение не является невыполнимым, - это проблема двоичных задач с ограничениями, граф которых имеет индуцированную ширину 2, с использованием строгой согласованности по направлениям. Действительно, эта форма согласованности гарантирует, что каждое присвоение переменной или паре переменных может быть расширено до более высокой переменной, а ширина 2 гарантирует, что эта переменная не будет присоединена к другой паре более низких переменных.
Причина, по которой наведенная ширина рассматривается вместо ширины, заключается в том, что обеспечение согласованности направленного пути может добавить ограничения. В самом деле, если две переменные не находятся в одном ограничении, но находятся в ограничении с более высокой переменной, некоторые пары их значений могут нарушить согласованность пути. Удаление таких пар создает новое ограничение. В результате распространение ограничений может привести к проблеме, граф которой имеет больше ребер, чем исходный. Однако все эти ребра обязательно находятся в индуцированном графе, поскольку все они находятся между двумя родителями одного и того же узла. Ширина 2 гарантирует, что каждая непротиворечивая частичная оценка может быть расширена до решения, но эта ширина относится к сгенерированному графику. В результате, индуцированная ширина, равная 2, требуется для сильной согласованности направленности траектории, чтобы гарантировать существование решений.
Направленная i-согласованность
Направленный -согласованность - это гарантия того, что каждое последовательное присвоение переменные могут быть последовательно расширены до другой переменной, которая находится выше по порядку. Сильное направленное-согласованность определяется аналогично, но все группы не более рассматриваются переменные. Если проблема строго направлена-согласованный и имеет ширину меньше чем и не имеет пустой области или невыполнимых ограничений, у него есть решения.
Каждую проблему можно решить строго направленно -согласованны, но эта операция может увеличить ширину соответствующих ей графиков. Процедура распространения ограничений, обеспечивающая согласованность по направлениям, аналогична процедуре, используемой для согласованности по дуге и согласованности по траектории. Переменные рассматриваются по очереди, от последней к первой в соответствии с порядком. Для переменной, алгоритм рассматривает каждую группу переменные с индексом ниже, чем и находятся в затруднительном положении с . Согласованность этих переменных с проверяется и, возможно, выполняется путем удаления удовлетворяющих назначений из ограничения среди всех этих переменные (если есть, или создание новых в противном случае).
Эта процедура генерирует строго направленный -согласованный экземпляр. Однако он также может добавить к экземпляру новые ограничения. В результате, даже если ширина исходной задачи равна, ширина полученного экземпляра может быть больше. Если это так, направленная строгая согласованность не подразумевает выполнимости, даже если ни один домен не является пустым и никакое ограничение не является невыполнимым.
Однако распространение ограничений добавляет ограничения только к переменным, которые ниже, чем та, которую он в настоящее время рассматривает. В результате никакие ограничения на переменную не изменяются и не добавляются после того, как алгоритм обработал эту переменную. Вместо того, чтобы рассматривать фиксированный, можно изменить его на количество родителей каждой рассматриваемой переменной (родители переменной - это переменные с индексом ниже, чем переменная, и которые находятся в ограничении с переменной). Это соответствует рассмотрению всех родителей данной переменной на каждом этапе. Другими словами, для каждой переменной от последнего до первого, все его родители включены в новое ограничение, которое ограничивает их значения теми, которые согласуются с . Поскольку этот алгоритм можно рассматривать как модификацию предыдущего со значениемкоторый изменяется на количество родителей каждого узла, это называется адаптивной согласованностью .
Этот алгоритм применяет строго направленные -соответствие равной наведенной ширине задачи. Результирующий экземпляр является выполнимым тогда и только тогда, когда ни один домен или ограничение не становятся пустыми. В этом случае решение можно легко найти, итеративно устанавливая неназначенной переменной произвольное значение и распространяя эту частичную оценку на другие переменные. Этот алгоритм не всегда является полиномиальным, поскольку количество ограничений, вводимых путем обеспечения строгой согласованности по направлениям, может привести к экспоненциальному увеличению размера. Однако проблема разрешима за полиномиальное время, если принудительная строгая согласованность по направлениям не суперполиномиально увеличивает экземпляр. В результате, если у экземпляра индуцированная ширина ограничена константой, его можно решить за полиномиальное время.
Устранение ведра
Исключение ведра - это алгоритм выполнимости. Его можно определить как переформулировку адаптивной согласованности. В его определениях используются сегменты, которые являются контейнерами для ограничения, каждая переменная имеет связанный сегмент. Ограничение всегда принадлежит сегменту самой высокой переменной.
Алгоритм исключения ведра поочередно переходит от самой высокой переменной к самой низкой. На каждом шаге ограничения в сегментах этой переменнойсчитаются. По определению, эти ограничения включают только переменные ниже, чем. Алгоритм изменяет ограничение между этими более низкими переменными (если есть, в противном случае он создает новую). В частности, это требует, чтобы их значения могли быть расширены до в соответствии с ограничениями в ведре . Это новое ограничение, если оно есть, затем помещается в соответствующую корзину. Поскольку это ограничение включает только переменные ниже, чем, он добавляется в корзину переменной, которая ниже, чем .
Этот алгоритм эквивалентен обеспечению адаптивной согласованности. Поскольку оба они обеспечивают согласованность переменной со всеми ее родителями, и поскольку после рассмотрения переменной не добавляется новое ограничение, в результате получается экземпляр, который может быть решен без отслеживания с возвратом .
Поскольку граф создаваемого ими экземпляра является подграфом индуцированного графа, если индуцированная ширина ограничена константой, сгенерированный экземпляр имеет размер, полиномиальный по размеру исходного экземпляра. В результате, если индуцированная ширина экземпляра ограничена константой, решение может быть выполнено за полиномиальное время двумя алгоритмами.
Реляционная согласованность
В то время как предыдущие определения согласованности касаются согласованности присваиваний, реляционная согласованность включает только удовлетворение заданного ограничения или набора ограничений. Точнее, реляционная согласованность подразумевает, что каждое непротиворечивое частичное присваивание может быть расширено таким образом, чтобы удовлетворялось данное ограничение или набор ограничений. Формально ограничение по переменным реляционно-согласованно с одной из своих переменных если каждое последовательное задание может быть расширен до таким образом доволен. Разница между "обычным" Непротиворечивость и непротиворечивость реляционной дуги заключается в том, что последнее требует только расширенного присвоения для удовлетворения заданного ограничения, в то время как первое требует, чтобы оно удовлетворяло всем соответствующим ограничениям.
Это определение может быть расширено до более чем одного ограничения и более чем одной переменной. В частности, реляционная согласованность путей аналогична реляционной дуговой согласованности, но вместо одного используются два ограничения. Два ограничения являются реляционными путями, согласованными с переменной, если каждое согласованное присвоение всем их переменным, кроме рассматриваемого, может быть расширено таким образом, чтобы выполнялись два ограничения.
Для более чем двух ограничений реляционные -согласованность определена. Реляционный-согласованность предполагает набор ограничения и переменная, которая находится в области действия всех этих ограничений. В частности, эти ограничения реляционные -согласовано с переменной, если каждое согласованное присвоение всем другим переменным, находящимся в их области действия, может быть расширено до переменной таким образом, чтобы эти ограничения были удовлетворены. Проблема в том-относительно непротиворечивым, если каждый набор ограничения реляционные -соответствует каждой переменной, которая присутствует во всех областях. Сильные отношения согласованность определяется, как указано выше: это свойство быть реляционным -соответствует каждому .
Реляционная согласованность также может быть определена для большего количества переменных вместо одной. Набор из ограничения реляционные -согласованным, если каждое последовательное присвоение подмножеству их переменных можно расширить до оценки всех переменных, удовлетворяющих всем ограничениям. Это определение не является точным расширением вышеизложенного, поскольку переменные, на которые предполагается распространить оценки, не обязательно входят во все области задействованных ограничений.
Если задан порядок переменных, реляционная согласованность может быть ограничена случаями, когда переменные (ы) оценки должны быть расширяемыми, чтобы следовать за другими переменными в порядке. Это измененное условие называется направленной реляционной согласованностью.
Относительная согласованность и выполнимость
Проблема удовлетворения ограничений может быть реляционно непротиворечивой, не иметь пустой области или невыполнимых ограничений, но при этом быть неудовлетворительной. Однако в некоторых случаях это невозможно.
Первый случай - это сильно реляционный -согласованная проблема, когда домены содержат не более элементы. В этом случае последовательная оценкапеременные всегда могут быть расширены до одной другой переменной. Если такая оценка и это переменная, есть только возможные значения, которые может принимать переменная. Если все такие значения несовместимы с оценкой, есть(не обязательно уникальные) ограничения, которые нарушаются оценкой и одним из ее возможных значений. В результате оценка не может быть расширена для удовлетворения всех этих требований.-или менее ограничений, нарушающих условие сильной реляционной -последовательность.
Второй случай связан с мерой ограничений, а не с областями. Ограничение-tight, если каждое вычисление ко всем своим переменным, кроме одной, может быть расширено, чтобы удовлетворить ограничение, либо всеми возможными значениями другой переменной, либо не более чем его ценностей. Проблема с-жатые ограничения выполнимы тогда и только тогда, когда они строго реляционно -последовательный.
Третий случай - это бинарные ограничения, которые могут быть представлены выпуклыми по строкам матрицами. Бинарное ограничение может быть представлено двумерной матрицей, где равно 0 или 1 в зависимости от того, -ое значение домена и -ое значение домена удовлетворить ограничение. Строка этой матрицы является выпуклой, если содержащиеся в ней единицы являются последовательными (формально, если два элемента равны 1, все элементы между ними также равны 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