В удовлетворении ограничений метод декомпозиции переводит проблему удовлетворения ограничений в другую проблему удовлетворения ограничений, которая является бинарной и ациклической . Методы декомпозиции работают путем группировки переменных в наборы и решения подзадачи для каждого набора. Эти переводы выполняются, поскольку решение бинарных ациклических проблем является поддающейся решению проблемой .
Каждое структурное ограничение определяет меру сложности решения задачи после преобразования; эта мера называется шириной . Фиксация максимально допустимой ширины является способом определения подкласса задач удовлетворения ограничений. Решение задач в этом классе является полиномиальным для большинства разложений; если это справедливо для разложения, класс задач фиксированной ширины образует поддающийся обработке подкласс задач удовлетворения ограничений.
Методы декомпозиции переводят проблему в новую, которую легче решить. Новая проблема содержит только бинарные ограничения ; их области действия образуют направленный ациклический граф . Переменные новой проблемы представляют собой набор переменных исходной. Эти наборы не обязательно являются непересекающимися, но они покрывают набор исходных переменных. Трансляция находит все частичные решения относительно каждого набора переменных. Проблема, которая возникает в результате трансляции, представляет собой взаимодействия между этими локальными решениями.
По определению, метод разложения создает бинарную ациклическую задачу; такие задачи могут быть решены за время, полиномиальное по ее размеру. В результате исходная задача может быть решена путем ее первого перевода, а затем решения полученной задачи; однако этот алгоритм является полиномиальным только в том случае, если разложение не увеличивает размер сверхполиномиально. Ширина метода разложения является мерой размера проблемы, которую он создает. Первоначально ширина была определена как максимальная мощность наборов исходных переменных; один метод, разложение гипердерева, использует другую меру. В любом случае ширина разложения определяется так, что разложения размера, ограниченного константой, не создают чрезмерно больших задач. Экземпляры, имеющие разложение фиксированной ширины, могут быть переведены путем разложения в экземпляры размера, ограниченного полиномом по размеру исходного экземпляра.
Ширина задачи — это ширина ее разложения минимальной ширины. Хотя разложения фиксированной ширины могут использоваться для эффективного решения задачи, ограничение ширины экземпляров обязательно создает поддающееся обработке структурное ограничение. Действительно, задача фиксированной ширины имеет разложение фиксированной ширины, но его нахождение может не быть полиномиальным. Для того чтобы задача фиксированной ширины была эффективно решена путем разложения, необходимо эффективно найти одно из ее разложений малой ширины. По этой причине методы разложения и связанная с ними ширина определяются таким образом, что не только решение задачи, заданной ее разложением фиксированной ширины, является полиномиальным по времени, но и нахождение разложения фиксированной ширины для задачи фиксированной ширины является полиномиальным по времени.
Методы декомпозиции создают задачу, которую легко решить из произвольной. Каждая переменная этой новой задачи связана с набором исходных переменных; ее домен содержит кортежи значений для переменных в связанном наборе; в частности, это кортежи, которые удовлетворяют набору ограничений по этим переменным. Ограничения новой задачи ограничивают значения двух новых переменных, чтобы иметь в качестве значений два кортежа, которые согласуются с общими исходными переменными. Три дополнительных условия гарантируют, что новая задача эквивалентна старой и может быть решена эффективно.
Для того, чтобы новая проблема была разрешима эффективно, первичный граф новой проблемы должен быть ациклическим. Другими словами, рассматривая переменные как вершины, а (бинарные) ограничения как ребра, результирующий граф должен быть деревом или лесом .
Для того чтобы новая проблема была эквивалентна старой, каждое исходное ограничение применяется как часть определения области по крайней мере одной новой переменной. Это требует, чтобы для каждого ограничения старой проблемы существовала переменная новой проблемы, такая, что ее связанный набор исходных переменных включает область ограничения, и все кортежи в ее области удовлетворяют ограничению.
Еще одним условием, необходимым для обеспечения эквивалентности, является то, что бинарные ограничения достаточны для того, чтобы заставить все «копии» каждой исходной переменной принять одно и то же значение. Поскольку одна и та же исходная переменная может быть связана с несколькими новыми переменными, значения этих новых переменных должны согласовываться со значением старой переменной. Бинарные ограничения используются для обеспечения равенства старых переменных, общих для двух новых переменных. Две копии новой переменной принудительно равны, если существует путь бинарных ограничений между их новыми переменными, и все новые переменные в этом пути содержат старую переменную.
Метод декомпозиции обычно определяется путем предоставления дерева, узлы которого являются переменными новой задачи; для каждого узла также предоставляются связанный набор исходных переменных и, возможно, набор исходных ограничений, используемых для построения домена переменной в новой задаче. Из трех приведенных выше условий (структура дерева, обеспечение ограничений и эквивалентность копий исходных переменных) первое автоматически обеспечивается этим определением. Условие обеспечения ограничений в основном формулируется как: область действия каждого ограничения является подмножеством переменных некоторого узла; однако, может использоваться другое условие, когда узлы также связаны с наборами ограничений. Эквивалентность всех копий исходных переменных обычно формулируется как: подграф, индуцированный узлами, связанными с исходной переменной, связан.
Существует ряд методов декомпозиции. Большинство из них генерируют поддающийся обработке класс, ограничивая ширину экземпляров. Ниже приведены методы декомпозиции, определенные для задач удовлетворения бинарных ограничений. Поскольку задачу можно сделать бинарной, переведя ее в ее двойственную задачу или используя скрытые переменные , эти методы можно косвенно использовать для предоставления древовидной декомпозиции для произвольных задач удовлетворения ограничений.
В теории графов разделяющая вершина — это узел графа, который «ломает» граф при удалении из него. Формально это узел, удаление которого из графа увеличивает число его связных компонент. Двусвязная компонента графа — это максимальный набор его узлов, чей индуцированный подграф связен и не имеет ни одной разделяющей вершины. Из теории графов известно, что двусвязные компоненты и разделяющие вершины графа образуют дерево. Это дерево можно построить следующим образом: его узлами являются двусвязные компоненты и разделяющие вершины графа; ребра соединяют двусвязную компоненту только с разделяющей вершиной, и в частности это происходит, если вершина содержится в компоненте. Можно доказать, что этот граф на самом деле является деревом.
Если ограничения задачи удовлетворения бинарных ограничений рассматривать как ребра графа, узлами которого являются переменные, то это дерево является декомпозицией задачи. Ширина декомпозиции — это максимальное число вершин в двусвязной компоненте.
Метод разложения цикла разделяет задачу на циклическую и ациклическую части. Хотя он не вписывается в определение других методов разложения, которые создают дерево, узлы которого помечены наборами узлов, его можно легко переформулировать в таких терминах.
Этот метод декомпозиции основан на идее, что после того, как некоторым переменным присвоено значение, то, что остается от проблемы после того, как эти переменные были устранены, может быть ацикличным. Формально, циклический разрез графа — это набор узлов, которые делают граф ацикличным, когда они из него удаляются. Аналогичное определение можно дать для задачи удовлетворения ограничений с использованием ее первичного графа. Ширина циклического разложения — это количество переменных в разрезе. Ширина задачи — это минимальная ширина ее циклических разрезов.
Такое разложение не вписывается в схему других разложений, поскольку результатом разложения является не дерево, а набор переменных (из разреза) и дерево (образованное переменными, не входящими в разрез). Однако дерево, подобное тем, что генерируются другими методами разложения, может быть получено из дерева, которое получается в результате удаления разреза; это делается путем выбора корня, добавления всех переменных разреза ко всем его узлам и переменных каждого узла ко всем его дочерним узлам. Это приводит к дереву, максимальное количество переменных, связанных с узлом, равно размеру разреза плюс два. Помимо добавления двух, это ширина разложения, которая определяется как количество переменных в рассматриваемом разрезе.
К сожалению, определение минимального набора для удаления является NP-трудной задачей .
Древовидная декомпозиция — хорошо известная концепция из теории графов. Переформулированная в терминах бинарных ограничений, древовидная декомпозиция — это дерево, узлы которого связаны с наборами переменных; область действия каждого ограничения содержится в наборе переменных некоторого узла, а поддерево узлов, связанных с каждой переменной, является связанным. Это наиболее общая форма декомпозиции для бинарных ограничений, которая следует схеме, описанной выше, поскольку условия, налагаемые на дерево, являются только теми, которые необходимы для гарантии эквивалентности исходной и новой задачи.
Ширина такого разложения — это максимальное число переменных, связанных с одним и тем же узлом, минус один. Ширина дерева задачи — это минимальная ширина ее древовидных разложений.
Исключение ведра можно переформулировать как алгоритм, работающий над конкретной декомпозицией дерева. В частности, при заданном порядке переменных каждая переменная связана с ведерком, содержащим все ограничения, таким образом, что переменная является наибольшей в их области действия. Исключение ведра соответствует декомпозиции дерева, которая имеет узел для каждого ведра. Этот узел связан со всеми его ограничениями и соответствует набору всех переменных этих ограничений. Родительский узел узла, связанного с ведерком , является узлом, связанным с ведерком , где — наибольший узел, который находится в ограничении с и предшествует в упорядочении.
Следующие методы могут быть использованы для перевода произвольной проблемы удовлетворения ограничений, как бинарной, так и иной. Поскольку они также могут быть использованы для бинарных задач, они также могут быть использованы для результата превращения ограничений в бинарные, либо путем перевода в двойственную задачу , либо с помощью скрытых переменных .
Некоторые из этих методов связывают ограничения с узлами дерева и определяют ширину с учетом количества ограничений, связанных с узлами. Это может уменьшить ширину некоторых задач. Например, разложение, в котором десять переменных связаны с каждым узлом, имеет ширину десять; однако, если каждый из этих наборов из десяти переменных является областью действия ограничения, каждый узел может быть связан с этим ограничением, что приведет к ширине один.
Двусвязное разложение произвольной проблемы удовлетворения ограничений является двусвязным разложением ее первичного графа. Каждое ограничение может быть применено к узлу дерева, поскольку каждое ограничение создает клику на своих переменных в первичном графе, а клика является либо двусвязным компонентом, либо подмножеством двусвязного компонента.
Древовидная декомпозиция произвольной проблемы удовлетворения ограничений — это древовидная декомпозиция ее первичного графа. Каждое ограничение может быть применено к узлу дерева, поскольку каждое ограничение создает клику на своих переменных на первичном графе, и для каждой древовидной декомпозиции переменные клики полностью содержатся в переменных некоторого узла.
Это тот же метод cycle cutset, использующий определение cutset для гиперграфов: cycle hypercutset гиперграфа — это набор ребер (а не вершин), который делает гиперграф ациклическим, когда все их вершины удалены. Разложение может быть получено путем группировки всех переменных hypercutset в одну. Это приводит к дереву, узлы которого являются наборами гиперребер. Ширина такого разложения — это максимальный размер наборов, связанных с узлами, который равен единице, если исходная задача ациклична, и размеру ее минимального hypercutset в противном случае. Ширина задачи — это минимальная ширина ее разложений.
Шарнир — это подмножество узлов гиперграфа, обладающее некоторыми свойствами, определенными ниже. Разложение шарнира основано на наборах переменных, которые являются минимальными шарнирами гиперграфа, узлы которого являются переменными задачи удовлетворения ограничений, а гиперребра — областями действия его ограничений.
Определение шарнира следующее. Пусть — набор гиперребер. Путь относительно — это последовательность ребер, такая, что пересечение каждого из них со следующим непусто и не содержится в узлах . Набор ребер связан относительно , если для каждой пары его ребер существует путь относительно , два узла которого являются первым и последним ребром. Связный компонент относительно — это максимальный набор связанных ребер относительно .
Шарниры определяются для редуцированных гиперграфов, которые являются гиперграфами, где ни одно гиперребро не содержится в другом. Набор из по крайней мере двух ребер является шарниром, если для каждого связанного компонента относительно , все узлы в , которые также находятся в , все содержатся в одном ребре .
Разложение шарнира основано на соответствии между задачами удовлетворения ограничений и гиперграфами. Гиперграф, связанный с задачей, имеет переменные задачи в качестве узлов, которые являются областями действия ограничений в качестве гиперребер. Разложение шарнира задачи удовлетворения ограничений представляет собой дерево, узлы которого являются некоторыми минимальными петлями гиперграфа, связанного с задачей, и такими, что выполняются некоторые другие условия. По соответствию задач гиперграфам шарнир представляет собой набор областей действия ограничений и, следовательно, может рассматриваться как набор ограничений. Дополнительных условий определения разложения шарнира три, из которых первые два гарантируют эквивалентность исходной задачи новой. Два условия эквивалентности таковы: область действия каждого ограничения содержится по крайней мере в одном узле дерева, а поддерево, индуцированное переменной исходной задачи, является связным. Дополнительное условие заключается в том, что если два узла соединены, то они разделяют ровно одно ограничение, и область действия этого ограничения содержит все переменные, общие для двух узлов.
Максимальное число ограничений узла одинаково для всех шарнирных декомпозиций одной и той же задачи. Это число называется степенью цикличности задачи или ее шарнирной шириной.
Древовидная кластеризация или кластеризация по дереву соединений основана на объединении ограничений таким образом, что результирующая задача имеет дерево соединений , это дерево соединений является результатом декомпозиции.
Дерево соединений задачи удовлетворения ограничений — это дерево, в котором каждый узел связан с ограничениями (и наоборот) и такое, что поддерево узлов, ограничение которых содержит переменную, связано. В результате создание дерева соединений можно рассматривать как особую форму декомпозиции, где каждый узел дерева связан с областью действия ограничения.
Не все проблемы удовлетворения ограничений имеют дерево соединений. Однако проблемы можно модифицировать, чтобы получить дерево соединений путем слияния ограничений. Древовидная кластеризация основана на том факте, что проблема имеет дерево соединений тогда и только тогда, когда ее первичный граф является хордовым и конформным с проблемой, последнее означает, что переменные каждой максимальной клики первичного графа являются областью действия ограничения и наоборот. Древовидная кластеризация модифицирует произвольную задачу таким образом, чтобы эти два условия были выполнены. Хордальность обеспечивается путем добавления новых бинарных ограничений. Конформность достигается путем слияния ограничений.
В частности, хордальность обеспечивается добавлением некоторых "поддельных" бинарных ограничений к задаче. Это бинарные ограничения, которым удовлетворяет любая пара значений, и они используются только для добавления ребер к первичному графу задачи. В частности, хордальность получается путем добавления ребер, производящих индуцированный граф первичного графа в соответствии с произвольным порядком. Эта процедура корректна, поскольку индуцированный граф всегда хордален и получается путем добавления ребер к исходному графу.
Конформность требует, чтобы максимальные клики первичного графа были в точности областью действия ограничений. Хотя областью действия каждого исходного ограничения является клика на первичном графе, эта клика не обязательно является максимальной. Более того, даже если она изначально была максимальной, обеспечение хордальности может создать большую клику. Конформность обеспечивается путем слияния ограничений. В частности, для каждой максимальной клики графа, полученной в результате обеспечения хордальности, создается новое ограничение с кликой в качестве области действия. Удовлетворяющие значения этого нового ограничения — это те, которые удовлетворяют всем исходным ограничениям, область действия которых содержится в клике. Благодаря этому преобразованию каждое исходное ограничение «включается» по крайней мере в одно новое ограничение. Действительно, областью действия каждого исходного ограничения является клика первичного графа. Эта клика остается кликой даже после обеспечения хордальности, поскольку этот процесс только вводит новые ребра. В результате эта клика либо является максимальной, либо содержится в максимальной клике.
Этот перевод требует идентификации максимальных клик хордального графа. Однако это можно легко сделать, используя тот же порядок, который используется для обеспечения хордальности. Поскольку родители каждого узла все соединены друг с другом, максимальные клики состоят из узла (максимального узла клики в порядке максимальной мощности) и всех его родителей. В результате эти максимальные клики можно обнаружить, рассматривая каждый узел с его родителями.
Проблема, которая возникает в результате этого процесса, имеет дерево соединения, и такое дерево соединения может быть получено путем повторного использования того же порядка переменных. Продвигаясь от последнего узла к первому, каждое ограничение связано с предыдущим ограничением, которое разделяет с ним больше переменных. Кластеризацию дерева соединения можно рассматривать как метод декомпозиции, в котором:
Ширина древовидной кластерной декомпозиции — это максимальное число переменных, связанных с каждым узлом дерева. Ширина задачи — это минимальная ширина ее древовидных кластерных декомпозиций.
Результат разложения шарнира можно еще больше упростить, разложив каждый шарнир с помощью кластеризации дерева. Другими словами, как только шарниры идентифицированы, создается кластеризация дерева каждого из них. С точки зрения полученного дерева, каждый узел, таким образом, заменяется деревом.
Декомпозиция запроса связывает набор переменных и набор ограничений с каждым узлом дерева; каждое ограничение связано с некоторым узлом, и поддерево, вызванное узлами, связанными с данной переменной или ограничением, связано. Точнее, для каждой переменной связано поддерево узлов, связанных с этой переменной или с ограничением, имеющим эту переменную в своей области действия. Ширина декомпозиции — это максимальное объединенное число переменных и ограничений, связанных с узлом.
Связывание ограничений с узлами, возможно, уменьшает ширину декомпозиций и экземпляров. С другой стороны, это определение ширины все еще позволяет решать задачи фиксированной ширины за полиномиальное время, если декомпозиция задана. В этом случае область новой переменной получается путем решения подзадачи, которая может быть полиномиально большой, но имеет фиксированное число ограничений. В результате эта область гарантированно будет иметь полиномиальный размер; ограничения новой задачи, будучи равенствами двух областей, также имеют полиномиальный размер.
Чистая декомпозиция запроса — это декомпозиция запроса, в которой узлы связаны только с ограничениями. Из декомпозиции запроса заданной ширины можно построить в логарифмическом пространстве чистую декомпозицию запроса той же ширины. Это получается путем замены переменных узла, которые не находятся в ограничениях узла, на некоторые ограничения, которые содержат эти переменные.
Недостатком этого метода декомпозиции является то, что проверка того, имеет ли экземпляр фиксированную ширину, в общем случае является NP-полной ; было доказано, что это имеет место для ширины 4.
Разложение гипердерева связывает набор переменных и набор ограничений с каждым узлом дерева. Оно расширяет разложение запроса, позволяя ограничениям узла содержать переменные, которые не используются при создании домена новой переменной, связанной с узлом. Помимо общих условий для метода разложения (область действия каждого ограничения находится по крайней мере в наборе переменных, связанных с узлом, и поддерево, вызванное исходной переменной, является связанным), должны выполняться следующие два условия:
Ширина разложения дерева — это максимальное количество ограничений, связанных с каждым узлом. Если эта ширина ограничена константой, то задача, эквивалентная исходной, может быть построена за полиномиальное время. Переменные, которые не связаны с узлом, но находятся в области действия ограничений узла, «проецируются» при построении этого экземпляра. Это можно сделать, сначала проецируя ограничения на переменные узла, а затем находя все решения этой подзадачи, или сначала решая подзадачу со всеми ограничениями, а затем удаляя лишние переменные.
Два требования выше не являются необходимыми для гарантии эквивалентности исходной и новой задачи. Они необходимы для гарантии того, что задачи ограниченной ширины могут быть решены за полиномиальное время.
Возможность связывания ограничения с узлом, в то время как некоторые из его переменных не связаны эффективно с узлом, может привести к ширине, которая меньше ширины запроса. Например, если узел связан с в декомпозиции запроса, и существует ограничение , декомпозиция гипердерева может связать тот же узел с ограничениями и переменными . Поскольку при проверке ширины вычисляются только ограничения, этот узел имеет ширину два. Тот же узел имеет ширину четыре при использовании декомпозиции запроса (одно ограничение и три переменные). Такое уменьшение ширины возможно, если две или более переменных можно заменить одним ограничением, даже если это ограничение содержит переменную, не связанную с узлом.
Обобщенные разложения гипердерева определяются как разложения гипердерева, но последнее требование опускается; это условие «переменные ограничений узла, которые не являются переменными узла, не встречаются в поддереве с корнем в узле». Задача может быть явно решена за полиномиальное время, если задано ее разложение фиксированной ширины. Однако ограничение на фиксированную ширину неизвестно, является ли оно поддающимся обработке, поскольку сложность нахождения разложения фиксированной ширины, даже если известно, что оно существует, неизвестна по состоянию на 2001 год [обновлять].
Ширина экземпляров является формой эффективности методов декомпозиции. Действительно, учитывая, что проблемы могут быть решены с помощью декомпозиций фиксированной ширины, чем меньше ширина согласно декомпозиции, тем больше экземпляров могут быть эффективно решены с использованием этой декомпозиции.
Некоторые разложения используют количество переменных узла (или аналогичное количество) в качестве ширины. Другие этого не делают: цикл hypercutset, разложение шарнира, разложение запроса, разложение гипердерева и обобщенное разложение гипердерева связывают ограничения (или их области действия в форме гиперребер) с узлами и включают количество ограничений, связанных с узлом, в ширину. Это может быть значительной экономией с точки зрения ширины. Действительно, проблемы с одним ограничением на переменные можно разложить только в дереве с одним узлом. Этот узел может быть связан с переменными или с одним ограничением. Подсчет количества переменных приводит к ширине , в то время как подсчет количества ограничений приводит к ширине .
Сравнение между всеми другими методами декомпозиции основано на обобщении и битве. Обобщение означает, что каждая проблема, имеющая ширину согласно методу, имеет ширину, ограниченную для фиксированного . Битва означает, что существуют классы задач, которые имеют фиксированную ширину согласно методу декомпозиции, но не согласно другому. Ниже приведены результаты для произвольных задач, где декомпозиция запроса не рассматривается:
Можно также показать, что ширина кластеризации дерева равна индуцированной ширине проблемы плюс один. Алгоритм адаптивной согласованности, который является полиномиальным для проблемы фиксированной индуцированной ширины, превращает проблемы в эквивалентные таким же образом, как и первый шаг кластеризации дерева.
Учитывая дерево разложения, решение может быть выполнено путем построения бинарной древовидной задачи, как описано выше, и ее решения. Это задача полиномиального времени, поскольку ее можно решить за полиномиальное время, используя, например, алгоритм для обеспечения согласованности направленной дуги .
Специализированный алгоритм для случая бинарных ациклических проблем, возникающих в результате разложения, описывается следующим образом. Он работает путем создания ограничений, которые передаются по ребрам дерева, от листьев к корню и обратно. Ограничение, передаваемое по ребру, «суммирует» эффекты всех ограничений части графа с одной стороны ребра на другую.
В дереве каждое ребро разбивает граф на две части. Ограничение, переданное по ребру, сообщает, как часть исходного конца ребра влияет на переменные конечного узла. Другими словами, ограничение, переданное от узла к узлу, сообщает, как узлы "на стороне " ограничивают переменные узла .
Если переменные этих двух узлов — и , то узлы на стороне не влияют на все переменные, а только на общие переменные . В результате влияние на узлов на стороне можно представить как ограничение на переменные . Такое ограничение можно рассматривать как «резюме» того, как набор узлов влияет на другой узел.
Алгоритм исходит из листьев дерева. В каждом узле собираются сводки его дочерних узлов (если таковые имеются). Эти сводки и ограничения узла используются для генерации сводки узла для его родителя. Когда достигается корень, процесс инвертируется: генерируется и отправляется сводка каждого узла для каждого дочернего узла. Когда достигаются все листья, алгоритм останавливается.
Набор переменных, разделяемый двумя узлами, называется их сепаратором . Поскольку сепаратор является пересечением двух наборов, связанных с узлами, его размер не может быть больше индуцированной ширины графика.
В то время как ширина графика влияет на время, необходимое для решения подзадач в каждом узле, размер разделителя влияет на размер ограничений, которые передаются между узлами. Действительно, эти ограничения имеют разделители в качестве области действия. В результате ограничение на разделитель размера может потребовать сохранения размера , если все переменные имеют область определения размера .
Алгоритм решения задачи из дерева декомпозиции включает две операции: решение подзадачи относительно узла и создание ограничения относительно общих переменных (разделителя) между двумя узлами. Для этих двух операций могут использоваться различные стратегии. В частности, создание ограничений на разделители может быть выполнено с помощью исключения переменных, что является формой вывода, в то время как подзадачи могут быть решены с помощью поиска (возврата и т. д.)
Проблема этого алгоритма в том, что ограничения, передаваемые между узлами, могут иметь размер, экспоненциальный по размеру разделителя. Требуемая для хранения этих ограничений память может быть уменьшена с помощью разложения дерева с небольшими разделителями. Однако такие деревья разложения могут иметь ширину (количество узлов в каждом узле) больше оптимальной.
Для заданного дерева декомпозиции фиксированный максимально допустимый размер разделителя может быть установлен путем объединения всех пар узлов, разделитель которых больше этого размера. Объединение двух узлов обычно создает узел с ассоциированным набором переменных, большим, чем у двух узлов. Это может увеличить ширину дерева. Однако это объединение не изменяет разделители дерева, за исключением удаления разделителя между двумя объединенными узлами.
Последнее является следствием ацикличности: два соединенных узла не могут быть соединены с одним и тем же другим узлом. Если и — два узла, которые должны быть объединены, а и — наборы узлов, соединенных с ними, то , так как в противном случае в дереве был бы цикл. В результате узел, полученный путем объединения и , будет соединен с каждым из узлов . В результате разделители этого объединенного узла являются в точности разделителями двух исходных узлов.
В результате слияние пары узлов, соединенных разделителем, не изменяет другие разделители. В результате фиксированный максимальный размер разделителя может быть принудительно установлен путем первого вычисления всех размеров разделителей, а затем итеративного слияния любой пары узлов, имеющих разделитель больше заданной величины, и размер разделителей не нужно пересчитывать во время выполнения.
Ограничение ширины метода декомпозиции константой создает структурное ограничение , то есть ограничивает возможные области действия ограничений, но не их отношения. Дополнительный способ получения поддающихся обработке подклассов удовлетворения ограничений заключается в размещении ограничения на отношениях ограничений; они называются реляционными ограничениями , а набор разрешенных отношений называется языком ограничений .
Если решение задач, имеющих ширину разложения, ограниченную константой, находится в P , разложение приводит к разрешимому структурному ограничению. Как объяснялось выше, разрешимость требует выполнения двух условий. Во-первых, если задача имеет ширину, ограниченную константой, то разложение ограниченной ширины может быть найдено за полиномиальное время. Во-вторых, задача, полученная путем преобразования исходной задачи в соответствии с разложением, не является сверхполиномиально большей исходной задачи, если разложение имеет фиксированную ширину.
В то время как большинство поддающихся обработке структурных ограничений вытекают из фиксации ширины метода разложения, были разработаны и другие. Некоторые из них можно переформулировать в терминах методов разложения: например, ограничение на бинарную ациклическую проблему можно переформулировать как проблему ширины дерева 1; ограничение индуцированной ширины (которое не определено в терминах разложения) можно переформулировать как кластеризацию дерева.
Раннее структурное ограничение (которое позже развилось в ограничение, основанное на индуцированной ширине) основано на ширине первичного графа задачи. При заданном порядке узлов графа ширина узла равна числу узлов, которые его соединяют и предшествуют ему в порядке. Однако ограничение только ширины не приводит к разрешимому ограничению: даже ограничивая эту ширину до 4, установление выполнимости остается NP-полным . Решаемость достигается путем ограничения отношений; в частности, если проблема имеет ширину и является строго -согласованной, она эффективно разрешима. Это ограничение не является ни структурным, ни реляционным, поскольку оно зависит как от областей действия, так и от отношений ограничений.
Вот несколько ссылок на онлайн-ресурсы по декомпозиции деревьев/гипердеревьев в целом.
