Конденсированный структурный граф

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

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

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

Упорядоченным разбиением множества называется декомпозиция в виде упорядоченной последовательности попарно непересекающихся непустых подмножеств, объединение которых – все множество .

Разбиение является фундаментальной задачей на графах. Одним из вари­антов этой задачи состоит в разбиении множества вершин на три мно­жества , такие, что и являются сбалансированными, т.е. ни одно из них не слишком мало, а невелико. Удаление вместе со всеми ребрами, инцидентными его вершинам, разбивает граф на два несвязных компонента. называется сепаратором. В общем случае задача разбиения гра­фа является NP-трудной. Поскольку задача разбиения графа является труд­ной, возникает необходимость разработки приближенных алгоритмов. По­пу­лярным алгорит­мом этого рода является MeTiS[9], имеющий хорошую бесплатную про­граммную реализацию.

A. Прямая часть

Рассмотрим вначале блок . Тогда

где и

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

и запоминании оптимальных локальных решений в виде функций окрест­ностей , т.е. .

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

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

B. Обратная часть.

Эта часть процедуры состоит в последовательном выборе ‑ оптимальных локальных решений из сохраненных в прямой части таблиц

.