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

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

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

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

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

Предположения [ править ]

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

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

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

Локальная согласованность [ править ]

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

Согласованность узлов [ править ]

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

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

Согласованность дуги [ править ]

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

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

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

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

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

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

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

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

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

Обычно используется другой тип ограничения 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}$

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

Если алгоритм оценивает переменные в порядке , согласованность полезна только тогда, когда она гарантирует, что все значения переменных с более низким индексом согласуются со значениями переменных с более высоким индексом. ${\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-согласованность [ править ]

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

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

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

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

Второй случай связан с мерой ограничений, а не с областями. Ограничение является жестким, если каждое вычисление для всех его переменных, кроме одной, может быть расширено для удовлетворения ограничения либо всеми возможными значениями другой переменной, либо не более чем ее значениями. Проблема с ограничениями -tight выполнима тогда и только тогда, когда они строго реляционно- согласованы.${\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}}$

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

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

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

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

Локальная согласованность доказывает выполнимость в некоторых ограниченных случаях (см. Сложность выполнения ограничений # Ограничения ). Это имеет место для каких-то особых проблем и / или некоторых видов локальной согласованности. Например, обеспечение согласованности дуги для двоичных ациклических задач позволяет определить, является ли проблема выполнимой. Обеспечение строгой согласованности по направлениям позволяет говорить о выполнимости задач, вызвавших ширину, в том же порядке. Адаптивная согласованность по направлениям позволяет определить выполнимость произвольной задачи.${\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