Метод декомпозиции (удовлетворение ограничений)

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

Каждое структурное ограничение определяло меру сложности решения задачи после преобразования; эта мера называется шириной . Фиксация максимально допустимой ширины — это способ идентификации подкласса проблем удовлетворения ограничений. Решение задач этого класса является полиномиальным для большинства разложений; если это справедливо для декомпозиции, класс задач фиксированной ширины образует управляемый подкласс задач удовлетворения ограничений.

Обзор

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

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

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

Методы разложения

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

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

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

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

	Пример проблемы удовлетворения ограничений; эта задача является бинарной, а ограничения представлены ребрами этого графа.
	Дерево разложения; для каждого ребра исходного графа существует узел, содержащий обе его конечные точки; все узлы, содержащие переменную, связаны
	Решение подзадачи. В этом примере показано решение подзадачи, состоящей из всех ограничений на переменные первого набора. $\{x,y,z\}$ . Аналогичная процедура проделывается и для остальных наборов $\{u,x,z\}$ и $\{y,w\}$
	Каждый узел дерева делается переменной. Его областью определения является множество решений частичной задачи, представляющее собой набор кортежей. Ограничения новой задачи допускают только кортежи, содержащие равные значения исходных переменных. На рисунке равенство $y$ показано: соответствующему ограничению удовлетворяет только первый кортеж $(x,y,z)$ и первый кортеж $(y,w)$ , а вторым кортежем $(x,y,z)$ и второй кортеж $(y,w)$ . Более того, второй кортеж $(x,y,z)$ не может найти удовлетворенный кортеж в своем левом дочернем элементе ( $(u,x,z)$ ). Таким образом, второй кортеж $(u,x,z)$ следует удалить.

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

Методы декомпозиции бинарных задач

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

Двусвязные компоненты

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

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


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

Циклический разрез

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

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


Графическое представление проблемы удовлетворения ограничений	Циклическое сокращение графа (существуют и другие)	При удалении цикла цикла остается ациклический граф (в данном случае дерево, но в целом лес).

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

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

К сожалению, определение минимального набора для удаления — задача NP-Hard .

Разложение дерева

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

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

Исключение сегментов можно переформулировать как алгоритм, работающий над декомпозицией конкретного дерева. В частности, при упорядочивании переменных каждая переменная связана с сегментом, содержащим все ограничения, так что эта переменная является наибольшей в своей области действия. Исключение сегментов соответствует разложению дерева, в котором для каждого сегмента имеется узел. С этим узлом связаны все его ограничения и соответствует набору всех переменных этих ограничений. Родитель узла, связанного с сегментом $x_{i}$ — это узел, связанный с ведром $x_{j}$ , где $x_{j}$ это наибольший узел, который находится в ограничении с $x_{i}$ и предшествует $x_{i}$ в заказе.

Методы декомпозиции произвольных задач

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

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

Двусвязные компоненты

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

Разложение дерева

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

Циклический гиперкатсет

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

Шарнирное разложение

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

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

Шарниры определены для редуцированных гиперграфов, то есть гиперграфов, в которых ни одно гиперребро не содержится в другом. Набор как минимум из двух ребер $H$ является шарниром, если для каждой компоненты связности $F$ относительно $H$ , все узлы в $F$ которые также находятся в $H$ все содержатся в одном ребре $H$ .

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

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

Кластеризация деревьев

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

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

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

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

Конформность требует, чтобы максимальные клики простого графа точно попадали в область ограничений. Хотя областью действия каждого исходного ограничения является клика на исходном графе, эта клика не обязательно является максимальной. Более того, даже если изначально она была максимальной, соблюдение хордализации может привести к созданию более крупной клики. Конформность обеспечивается путем слияния ограничений. В частности, для каждой максимальной клики графа, возникающей в результате обеспечения хордльности, создается новое ограничение с кликой в качестве области действия. Удовлетворяющие значения этого нового ограничения — это значения, удовлетворяющие всем исходным ограничениям, область действия которых содержится в клике. Благодаря этому преобразованию каждое исходное ограничение «включается» как минимум в одно новое ограничение. Действительно, областью действия каждого исходного ограничения является клика основного графа. Эта клика остается кликой даже после обеспечения хордльности, поскольку этот процесс только вводит новые ребра. В результате эта клика либо максимальна, либо содержится в максимальной клике.


Пример: задача удовлетворения бинарных ограничений (кластеризация дерева соединений также может применяться к небинарным ограничениям.) Этот граф не является хордальным (x3x4x5x6 образует цикл из четырех узлов, не имеющих хорды).	Граф сделан хордальным. Алгоритм анализирует узлы от x6 до x1. Красное ребро — единственное добавленное ребро, поскольку x6 — единственный узел, имеющий двух несоединенных родительских узлов. Он представляет собой ограничение между x4 и x5, которому удовлетворяет каждая пара значений.	Идентифицируются максимальные клики полученного графа. Кластеризация дерева соединений заменяет ограничения на {x3, x4, x5, x6} двумя эквивалентными ограничениями: одно на {x3, x4, x5} и одно на {x4, x5, x6}.

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

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

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

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

Шарнирное/кластерное разложение

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

Декомпозиция запроса

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

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

Гиперграфическое представление задачи удовлетворения ограничений: ограничениям даны имена (P, Q, R, S, T) и показаны их области действия (P (a, b, c) означает, что ограничение P относится к переменным {a , б, в}

Декомпозиция задачи по запросу. Узлы могут содержать переменные, ограничения или и то, и другое. Хотя с самым правым узлом связано всего пять переменных (т.е. a,b,c,d,e среди двух ограничений), это разложение шириной 3, поскольку ни один узел не содержит более трех ограничений и изолированных переменных (существует другое разложение ширины 2 и можно показать, что это разложение ширины 2 является минимальной шириной этого гиперграфа).

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

Недостатком этого метода декомпозиции является то, что проверка того, имеет ли экземпляр фиксированную ширину, обычно является NP-полной ; было доказано, что это имеет место с шириной 4

Разложение гипердерева

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

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

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

Декомпозиция гипердерева той же проблемы, что и описанная выше декомпозиция запроса. R(b,d,e,-) означает, что последняя переменная R не является переменной, связанной с корнем. При группировке двух переменных в одном ограничении в корне ширина уменьшается с трёх до двух.

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

Возможность связать ограничение с узлом, в то время как некоторые из его переменных не связаны с узлом эффективно, может привести к тому, что ширина будет меньше ширины запроса. Например, если узел связан с $\{C(a,b),c,d,e\}$ в декомпозиции запроса и ограничение $D(c,d,e,f)$ существует, разложение гипердерева может связать один и тот же узел с ограничениями $\{C,D\}$ и переменные $\{a,b,c,d,e\}$ . Поскольку при проверке ширины вычисляются только ограничения, этот узел имеет ширину два. Тот же узел имеет ширину четыре при использовании декомпозиции запроса (одно ограничение и три переменные). Такое уменьшение ширины возможно, если две или более переменных можно заменить одним ограничением, даже если это ограничение содержит переменную, не связанную с узлом.

Обобщенное разложение гипердерева

Обобщенные декомпозиции гипердерева определяются как декомпозиции гипердерева, но последнее требование опущено; это условие «переменные ограничений узла, которые не являются переменными узла, не встречаются в поддереве с корнем в узле». Задача может быть явно решена за полиномиальное время, если задано ее разложение фиксированной ширины. Однако неизвестно, чтобы ограничение фиксированной ширины было осуществимым, поскольку по состоянию на 2001 год неизвестна сложность поиска разложения фиксированной ширины, даже если известно, что оно существует. ^[update].

Сравнение

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

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

Сравнение всех остальных методов декомпозиции основано на обобщении и избиении. Обобщение означает, что каждая проблема, имеющая ширину $n$ согласно методу имеет ширину, ограниченную $n+k$ за фиксированную $k$ . Биение означает, что существуют классы задач, которые имеют фиксированную ширину по одному методу декомпозиции, но не по другому. Ниже приведены результаты для произвольных задач, где декомпозиция запроса не рассматривается:

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

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

Решение из разложения

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

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

Ограничение, передаваемое от узла i к узлу j, суммирует эффекты узлов на «стороне» i на переменные j.

В дереве каждое ребро разбивает граф на две части. Ограничение, передаваемое вдоль ребра, сообщает, как часть исходного конца ребра влияет на переменные узла назначения. Другими словами, ограничение, переданное из узла $i$ узел $j$ рассказывает, как узлы «на стороне $i$ "ограничить переменные узла $j$ .

Если переменные этих двух узлов $X_{i}$ и $X_{j}$ , узлы на стороне $i$ не влияют на все переменные $X_{j}$ но только общие переменные $X_{i}\cap X_{j}$ . В результате влияние на $X_{j}$ узлов на стороне $i$ можно представить как ограничение на переменные $X_{i}\cap X_{j}$ . Такое ограничение можно рассматривать как «сводку» того, как набор узлов влияет на другой узел.

Алгоритм исходит из листьев дерева. В каждом узле собираются сводные данные о его дочерних узлах (если таковые имеются). Эти сводные данные и ограничения узла используются для создания сводных данных узла для его родителя. Когда достигается корень, процесс инвертируется: создается и отправляется сводка каждого узла для каждого дочернего узла. Когда все листья достигнуты, алгоритм останавливается.


Дерево декомпозиции со связанными ограничениями. В этом примере все переменные имеют домен {0,..,10}.	Самый левый узел содержит ограничение a<b и разделяет переменную b со своим родителем. Эти ограничения позволяют b принимать только значения, большие или равные 1. Это ограничение b>0 отправляется его родительскому элементу.	Левый дочерний элемент корня получает ограничение b>0 и объединяет его со своим ограничением b<c. Он разделяет c со своим родителем, и два ограничения обеспечивают соблюдение c>1. Это ограничение отправляется своему родителю.	Когда корень получил ограничения для всех своих дочерних элементов, он объединяет их и отправляет им ограничения обратно. Процесс заканчивается, когда достигнуты все листья. На этом этапе допустимые значения переменных являются явными.

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

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

Компромисс памяти/времени

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

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

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

Последнее является следствием ацикличности: два соединенных узла не могут быть присоединены к одному и тому же другому узлу. Если $n_{1}$ и $n_{2}$ два узла, которые необходимо объединить, и $N_{1}$ и $N_{2}$ являются наборами узлов, присоединенных к ним, то $N_{1}\cap N_{2}=\emptyset$ , так как в противном случае в дереве был бы цикл. В результате узел, полученный слиянием $n_{1}$ и $n_{2}$ будет присоединен к каждому из узлов $N_{1}\cup N_{2}$ . В результате разделители этого объединенного узла являются в точности разделителями двух исходных узлов.

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

Структурные ограничения

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

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

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

Раннее структурное ограничение (которое позже превратилось в ограничение, основанное на индуцированной ширине) основано на ширине основного графа задачи. Учитывая порядок узлов графа, ширина узла — это количество узлов, которые присоединяются к нему и предшествуют ему в порядке. Однако ограничение только ширины не приводит к допустимому ограничению: даже ограничивая эту ширину до 4, установление выполнимости остается NP-полным . Сговорчивость достигается путем ограничения отношений; в частности, если проблема имеет ширину $k$ и сильно $k$ -согласована, эффективно разрешима. Это ограничение не является ни структурным, ни реляционным, поскольку оно зависит как от областей действия, так и от отношений ограничений.

См. также

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

Интернет-ресурсы

Вот несколько ссылок на онлайн-ресурсы по разложению дерева/гипердерева в целом.

Treewidthlib : эталон алгоритмов для Treewidth и связанных с ним проблем с графами.
Реализация на C++, использованная в статье «Полный алгоритм в любое время для ширины дерева», Вибхав Гогейт и Рина Дектер, UAI 2004. Ссылка ведет на домашнюю страницу автора, где распространяются как исходный код LINUX, так и исполняемый файл Windows.
Реализация разложения гипердерева с использованием нескольких эвристик.
Инструмент панели инструментов имеет реализацию некоторых эвристик разложения дерева.
Библиотека TreeD: содержит исходный код некоторых методов декомпозиции.

Ссылки

Дектер, Рина (2003). Обработка ограничений . Морган Кауфманн. ISBN 1-55860-890-7
Дауни, Род ; Товарищи, Майкл (1997). Параметризованная сложность . Спрингер. ISBN 0-387-94883-X
Готтлоб, Георг ; Леоне, Никола ; Скарчелло, Франческо (2001). «Разложение гипердеревьев: обзор» . МФКС 2001 . стр. 37–57. ^{[ мертвая ссылка ]}
Готтлоб, Георг; Леоне, Никола; Скарчелло, Франческо (2000). «Сравнение методов структурной декомпозиции CSP» . Искусственный интеллект . 124 (2): 243–282. дои : 10.1016/S0004-3702(00)00078-3 .