Многоуровневая декомпозиция гиперграфовых структур

10. Если M(v_i) = 0 и M(v_j) ≠ 0, т.е. вершина v_j уже входит в группу M(v_j), в таком случае пытаемся включить в эту же группу и вершину v_i

2. Если  , то переход на шаг 5

11. Если M(v_j) = 0 и M(v_i) ≠ 0, т.е. вершина v_i уже входит в группу M(v_i), в таком случае пытаемся включить в эту же группу и вершину v_j

2. Если  , то переход на шаг 5,

12. Если M(v_j) ≠ 0 и M(v_i) ≠ 0, то мы попытаемся перенести столько вершин из одной группы в другую, сколько возможно:

1. , это группа-акцептор.
2. , это группа-донор.
3. , это число показывает, сколько вершин мы можем перенести, ограничения два: размер группы-донора и количество вершин, которое может принять группа-акцептор до полного заполнения.

13. Случайным образом выбираем T вершин v, среди тех, для которых  , обозначим это множество вершин V_T.

14. Переход на шаг 5.

После того, как отработал  алгоритм пометки вершин, запускается  алгоритм построения загрубленного гиперграфа, входными данными которого являются исходный гиперграф H(V,E) и информация о пометках, т.е. отображение M.

Как видно из схемы работы, алгоритм пометки пытается сгруппировать  вершины графа путем создания новой группы и помещения туда двух вершин, которые до этого не входили в состав какой-либо группы (шаг 9), помещения вершины в уже  существующую группу (шаги 10 и 11), либо частичного слияния двух групп (шаг 12). При этом для алгоритма определено два критерия останова: первый –  достижение желаемого уровня загрубления (после применения построения загрубленного гиперграфа), второй – исчерпание ресурса алгоритма по дальнейшему объединению вершин в группы. Срабатывание второго критерия остановки обуславливается двумя факторами: наличием ограничения на максимальный размер группы и связностью гиперграфа. Так, например, вполне вероятна ситуация, когда очередную вершину нельзя включить ни в одну из групп, т.к. они достигли предельного размера, или когда гиперграф имеет низкую связность, и для какой-либо вершины нет другой вершины, характеризующейся хоть каким-то притяжением с данной.

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

9.2. Схема гиперреберного загрубления

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

1. Все гиперребра сортируются в порядке невозрастания веса, ребра с одинаковым весом сортируются в порядке неубывания размера.
2. Выбирается первое гиперребро, все принадлежащие ему вершины помечаются как включенные в группу для объединения.
3. Выбирается следующее гиперребро, если оно не содержит помеченных вершин, то все вершины, входящие в его состав, помечаются, как включенные в следующую группу для объединения.
4. Если есть еще непросмотренные ребра, то переход на шаг 3.
5. Запустить алгоритм построения загрубленного гиперграфа.

Работа алгоритма проиллюстрирована  на рисунке 31.

Рис. 31. Схема гиперреберного загрубления: исходный гиперграф (слева), множество попарно неинцидентных гиперребер (в центре), результат загрубления (справа).

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

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

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

Схема алгоритма:

1. Все гиперребра сортируются в порядке невозрастания веса, ребра с одинаковым весом сортируются в порядке неубывания размера.
2. Выбирается первое гиперребро, все принадлежащие ему вершины помечаются как включенные в группу для объединения.
3. Выбирается следующее гиперребро, если оно не содержит помеченных вершин, то все вершины, входящие в его состав, помечаются, как включенные в следующую группу для объединения.
4. Если есть еще непросмотренные ребра, то переход на шаг 3.
5. Выбирается второе ребро, все непомеченные вершины, входящие в его состав, помечаются, как включенные в следующую группу для объединения.
6. Выбирается следующее ребро, все непомеченные вершины, входящие в его состав, помечаются, как включенные в следующую группу для объединения.
7. Если есть еще непросмотренные ребра, непросмотренные на шагах 5 и 6, то переход на шаг 6.
8. Запустить алгоритм построения загрубленного гиперграфа.

Работа алгоритма проиллюстрирована  на рисунке 32.

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

9.3. Алгоритм построения  загрубленного гиперграфа

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

Итак, входной информацией  для алгоритма построения загрубленного гиперграфа является исходный гиперграф H(V,E,W), где V – множество вершин, E – множество гиперребер, W – веса вершин, и функция M(v_i), определяющая разбиение вершин по группам для объединения.

Схема работы следующая:

1. Разобьем множество вершин V на подмножества в соответствии с информацией о принадлежности к группам:

Все процедуры построения пометок гарантируют, что:

1. число непустых подмножеств такого рода конечно, а именно 
3. Формируем загрубленный гиперграф 

Не смотря на довольно сложную  математическую запись, семантика второго  шага довольно проста. Формирование загрубленного гиперграфа происходит следующим образом: все непомеченные вершины, т.е. вершины из V₀ переносятся во вновь формируемое множество вершин загрубленного гиперграфа без изменения, вес этих вершин также не меняется (что соответствует первой строке в записи пункта 2.3). Каждая группа помеченных вершин заменяется одной вершиной-конгломератом, ее вес равен суммарному весу вершин группы (вторая строчка в записи пункта 2.3). Для каждого гиперребра исходного гиперграфа строится новое ребро путем замены вершин исходного гиперграфа, которые попали в группы для объединения на соответствующие вершины-конгломераты. Если при этом получилось гиперребро, содержащее более одной вершины, то оно добавляется во множество ребер загрубленного гиперграфа. Фактически шаги 2.1 и 2.2 описывают ряд операций стягивания множества вершин. 

9.4. Алгоритмы поиска  начального разбиения

Поскольку размерность задачи-редуктанта самой большой глубины невелика, то ряд алгоритмов, способных получить начальное разбиение в многоуровневом алгоритме достаточно широк. В случае, когда самый загрубленный гиперграф содержит десяток вершин возможно применение переборных методов. Однако, в силу ограничений схем загрубления, редукция гиперграфов больших размеров (десятки и сотни тысяч) до размерностей в несколько десятков часто невозможна. Поэтому можно использовать менее ресурсоемкие алгоритмы, например, т.н. «region-growing» алгоритмы [CAAK1] или алгоритмы, строящие случайные разбиения [BKMP, BKLR1, BKLR2, BKLR3, BKLR4, BKLR5] с последующим их улучшением с помощью эвристик типа алгоритма Кернигана-Лина (Kernigan and Lin, KL) [BKSL], Фидуччиа-Мэтьюза (Fiduccia and Mattheyses, FM) [CFRM], спектральных методов [PCMS], табу-поиска [PKKW] или методов «simulated annealing» [SK], модифицированных для работы с гиперграфами или описанного ниже генетического улучшающего алгоритма. 

9.5. Фаза восстановления  решений

Решение задачи H₃ может быть спроецировано на задачу H₀, в этом состоит суть фазы восстановления решения. Поскольку вычислительная сложность алгоритмов загрубления, как правило, несравнимо меньше вычислительной сложности декомпозиционных алгоритмов, а размерность задачи-редуктанта самого высокого порядка на несколько порядков ниже размерности исходной задачи, такой подход дает существенный выигрыш по вычислительной сложности по сравнению с «классическими» декомпозиционными алгоритмами.