Двойная проблема удовлетворения ограничений - Constraint satisfaction dual problem

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

Двойная проблема

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

Ограничения двойственной задачи запрещают двум двойственным переменным принимать значения, соответствующие двум несовместимым кортежам. Без этих ограничений одна двойственная переменная может принимать значение, соответствующее кортежу ${displaystyle x = 1, y = 2}$ в то время как другая двойная переменная принимает значение, соответствующее ${displaystyle y = 3, z = 1}$ , который присваивает другое значение ${displaystyle y}$ .

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

	Двойственные переменные являются ограничениями исходной задачи.
	Область определения каждой двойственной переменной - это набор кортежей соответствующего исходного ограничения.
	Двойные ограничения заставляют двойные переменные (исходные ограничения) иметь значения (исходные кортежи), которые содержат равные значения исходных переменных. В этом примере исходные ограничения ${displaystyle C_ {1}}$ и ${displaystyle C_ {2}}$ поделиться переменной ${displaystyle y}$ . В двойственной задаче переменные ${displaystyle C_ {1}}$ и ${displaystyle C_ {2}}$ могут иметь значения ${displaystyle (1,2)}$ и ${displaystyle (2,1)}$ потому что эти ценности согласуются ${displaystyle y = 2}$ .

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

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

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

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

{displaystyle x, y}

между

{displaystyle C_ {1}}

и

{displaystyle C_ {2}}

указывает на то, что двойная задача содержит ограничение между

{displaystyle C_ {1}}

и

{displaystyle C_ {2}}

, и это ограничение применяет значения (кортежи), которые соответствуют

{displaystyle x}

и

{displaystyle y}

.

Соединяйте графы и соединяйте деревья

В дуальном графе некоторые ограничения могут быть ненужными. В самом деле, двойные ограничения обеспечивают равенство исходных переменных, а некоторые ограничения могут быть избыточными из-за транзитивности равенства. Например, если ${displaystyle C_ {2}}$ и ${displaystyle C_ {1}}$ соединены ребром, метка которого содержит ${displaystyle y}$ , и так ${displaystyle C_ {1}}$ и ${displaystyle C_ {3}}$ , равенство ${displaystyle y}$ во всех трех двойственных переменных гарантируется. В результате двойное ограничение между ${displaystyle C_ {2}}$ и ${displaystyle C_ {3}}$ обеспечение равенства ${displaystyle y}$ не является обязательным и может быть удален при наличии.

Поскольку равенство

{displaystyle y}

навязывается другими двойными ограничениями, между

{displaystyle C_ {2}}

и

{displaystyle C_ {3}}

можно уронить.

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

Найти дерево соединений, если таковое имеется, можно, используя следующее свойство: если дуальный граф имеет дерево соединений, то максимальный вес остовные деревья графа являются деревьями соединений, если ребра взвешиваются по количеству переменных, которые соответствующие ограничения заставляют быть равными. Алгоритм поиска дерева соединений, если таковой имеется, действует следующим образом. На первом этапе ребрам присваиваются веса: если два узла представляют ограничения, ${displaystyle n}$ переменным, соединяющему их ребру присваивается вес ${displaystyle n}$ . На втором этапе ищется остовное дерево максимального веса. Как только один найден, проверяется, обеспечивает ли он требуемое равенство переменных. В этом случае это остовное дерево является деревом соединений.

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

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

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

Расширения

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

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

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

Скрытая трансформация

Двойная проблема удовлетворения ограничений - Constraint satisfaction dual problem

Содержание