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

8. Постановка задачи  и многоуровневая декомпозиция

В качестве задачи декомпозиции рассмотри проблему k-разбиения гиперграфа, которая состоит в распределении множества вершин V по k подмножествам V₁,…V_k, таким образом, чтобы удовлетворялся набор ограничений, называемых декомпозиционными ограничениями, а оптимизируемая функция (функция цели, критерий оптимальности, функционал), определенная над разбиением, принимала экстремальное значение. Распределение предполагает, что множества V₁,…V_k попарно не пересекаются и при объединении составляют исходное множество V:

(1)

Подмножества разбиения  определяют подграфы разбиения [AAZ]. Значение k фиксировано и задается как параметр задачи.

Определим декомпозиционные ограничения так, чтобы вес каждого подграфа разбиения  , лежал в следующих пределах:

, Li и Ui – минимальный и максимальный вершинные веса подграфов разбиения.

(2)

В ограничениях (2) константы L_i и U_i определяют пределы, в которых могут варьироваться веса подграфов разбиения.

Критерии оптимальности, как и декомпозиционные ограничения, определяются спецификой конкретной задачи. В исследовании [CAAK2] приведено обширное описание функций цели, встречающихся при проектировании РЭА. Один из наиболее часто используемых критериев – минимизация веса сечения. Вес сечения определяется суммой весов ребер, которые целиком не принадлежат ни одному подграфу разбиения:

(3)

Задачу (1)-(3) будем называть задачей k-разбиения гиперграфа. Возможны различные расширения проблемы (1)-(3). Например, задача может иметь несколько функций цели (многокритериальный случай), тогда решение состоит в нахождении парето-области решений.

Исследуемые задачи декомпозиции гиперграфа NP-трудны [DB1, DB2, DBDK, GL, HPSK, MGDD] и на практике, как правило, имеют  большие размерности. Алгоритмы, получающие точные решения таких задач, оказываются  неприменимыми в силу большой  вычислительной сложности. Известно множество  попыток сведения подобных задач  к менее сложным. Условно методы решения задач декомпозиции больших порядков можно разбить на две группы. В первую группу отнесем методы, которые осуществляют переход к более простым задачам, не используя понижение размерности задачи. Например, бисекционные алгоритмы [DBVK, DSBK, HSST, LG2, LG4, NS2] предполагают рекурсивную бисекцию графа до тех пор, пока не будет получено необходимое количество подграфов разбиения. Вторую группу составляют методы, которые сокращают вычислительную сложность за счет уменьшения размерности исходной задачи.

Методы второй группы, осуществляющие непосредственное k-разбиение, в целом получают более качественное решение. Например, показано [HSST], что решение, полученное рекурсивной бисекцией, может быть вплоть до O(log n), где n – размерность графа, хуже, чем решение алгоритма, осуществляющего непосредственное k-разбиение [AFNS, CAAK1, CAAK3, CYCC, DBNS1, DBNS2, GKVK1, GKVK5, KSGK, LS1, LS2, PCMS]. Такое положение вещей объясняется тем, что рекурсивный метод не позволяет напрямую оптимизировать функционалы, значение которых зависит от того, каким способом ребра распределены по подграфам разбиения. Второе существенное преимущество – в ходе работы алгоритм второго типа способен более жестко контролировать декомпозиционные ограничения, в то время как бисекционные алгоритмы должны иметь специальные фазы коррекции решения для удовлетворения этим ограничениям, что существенно ограничивает область поиска решения.

Рис. 27. Концептуальная схема работы многоуровневого алгоритма на примере задачи 3-разбиения гиперграфа. Слева закрашенные овалы отождествляются с гиперграфовыми структурами. Чем меньше площадь овала, тем большей редукции подвергся соответствующий гиперграф. Снизу указан вариант начального 3-разбиения редуцированного гиперграфа. Справа пунктиром указаны варианты восстановленных решений из разбиений гиперграфов с большей степенью редукции. На каждом шаге восстановления решения корректируются и оптимизируются при помощи техник локального улучшения.

В последнее время популярность приобрели так называемые многоуровневые алгоритмы [BHRL, CAAK2, CAAK3, GKVK1, GKVK2, GKVK3, GKVK4, GKVK5, GKVK6, NSGK, SBHS, SWEA]. Ключевая идея многоуровневого  алгоритма декомпозиции состоит  следующем: вместо того, чтобы строить k-разбиение непосредственно для  исходного гиперграфа, сначала строится ряд его приближений (загрублений). Каждое загрубление уменьшает (редуцирует) размерность исходной задачи. Процесс редукции продолжается до тех пор, пока порядок гиперграфа не снизится до сотен или даже десятков. На гиперграфе таких размерностей и отыскивается так называемое начальное разбиение. Полученное решение используется для построения решения для исходной задачи. Это достигается путем выполнения серии переносов решения задачи меньшей размерности на задачу большей размерности с последующим улучшением перенесенного решения. Таким образом, работу многоуровневого алгоритма можно разделить на три фазы: первая – фаза загрубления, когда производится ряд последовательных редукций размерности задачи, вторая – фаза поиска начального разбиения и третья – фаза восстановления решения, когда производится серия последовательных переносов решения задачи меньшей размерности на менее редуцированную задачу с последующим улучшением спроецированного решения. Работа алгоритма для задачи 3-декомпозиции схематично показана на рисунке 27.

Детально рассмотрим фазы многоуровневого алгоритма.

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

На рисунке 27 исходная задача 3-разбиения поставлена над гиперграфом H₀. В ходе фазы загрубления строится редуцированный гиперграф H₁, получаемый из H₀удалением избыточной информации, и над полученным гиперграфом ставится новая задача 3-декомпозиции. Удаление избыточной информации из гиперграфа и постановка новой задачи должно производиться таким образом, чтобы по решению новой задачи могло быть построено решение исходной задачи. Если это условие выполнено, то процесс удаления избыточной информации из гиперграфа назовем загрублением гиперграфа, а процесс построения загрубленного гиперграфа и постановки над ним новой декомпозиционной задачи назовем редуцированием задачи; построение решения исходной задачи по решению вновь построенной будем называть переносом (проекцией)решения; исходную задачу будем называть задачей-прообразом, а вновь полученную – задачей-редуктантом. Таким образом, на первом этапе фазы загрубления мы получили из задачи-прообраза, определенной над гиперграфом H₀, задачу-редуктант, определенную над загрубленным гиперграфом H₁, обладающую меньшей размерностью. В дальнейшем для простоты будем обозначать декомпозиционную задачу, определенную над гиперграфом H_m, «задача H_m».

На втором этапе повторим процесс редуцирования, используя  задачу H₁ в качестве задачи-прообраза, и получим задачу H₂. Следующий этап позволит получить задачуH₃, обладающую достаточно малой размерностью, чтобы для нее можно было отыскать разбиение.

Описанное выше условие редуцирования  задачи, при котором решение, полученное для задачи-редуктанта, может быть спроецировано на задачу-прообраз, позволяет утверждать, что решение задачи H_m может быть использовано для построения решения задачи H_n (n < m). Действительно, решение H_m можно спроецировать на H_m-1, затем, полученное решение H_m-1 спроецировать на H_m-2, и так далее до H_n. Таким образом, задача H_m, по сути, является задачей-редуктантом H_n, а H_n в свою очередь – задачей-прообразом H_m. Число m-n назовем глубиной редукции. Задачу H_m будем называть задачей-редуктантом задачи H_n глубины m-n. Очевидно, задача H_m является задачей-редуктантом исходной задачи глубины m. Так, к примеру, на рисунке 27 задача H₂ является задачей-редуктантом задачи H₀ глубины 2 и задачей-редуктантом глубины 1 дляH₁. Возможность построения решения исходной задачи по решению любой задачи-редуктанта позволяет говорить о решении задачи-редуктанта как о решении исходной задачи. Что позволяет ассоциировать процесс построения начального разбиения с процессом отыскания некоего начального решения исходной задачи.

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

На рисунке 28 показан пример гиперграфа, в котором выделены несколько  таких групп вершин. Вершины в  таких группах обладают «сильными» связями. Выделено 3 группы вершин, каждая из которых образует клику в терминах обычного графа. Это группы V₁={v₁,v₂,v₃,v₄}, V₂={v₅,v₆,v₇,v₈} и V₃={v₉,v₁₀,v₁₁}. Понятно, что, например, в случае построения трисекции этого гиперграфа мы определим каждую группу вершин в свою компоненту разбиения, в противном случае, т.е. если мы распределим вершины какой-либо из групп по двум или, тем более, трем компонентам разбиения, то ребра, связывающие вершины этой группы будут принадлежать сечению, что негативно скажется на его весе. На этом факте и построен процесс загрубления в многоуровневом алгоритме k-декомпозиции. Поскольку нет смысла рассматривать вершины такой группы как отдельные сущности, мы можем заменить всю группу на одну вершину. Таким образом, мы, очевидно, сократим как количество вершин, так и количество ребер, поскольку все ребра, «внутренние» по отношению к такой группе вершин так же будут отсутствовать после замены. Итак, применим операцию стягивания вершин к группам V₁, V₂ и V₃. В результате получим новый гиперграф на трех вершинах (см. рис. 28). Видно, что мы сократили количество вершин с 11 до 3, а количество ребер с 4 до 1. Теперь, если мы проведем на редуцированном гиперграфе 3-разбиение (при этом каждая из вершин попадет в свою компоненту разбиения) и перенесем это решение на исходный граф, то получим готовое решение для исходного гиперграфа, в котором каждая из выделенных групп вершин попадет в свою компоненту разбиения.

Рис. 28. Пример редукции гиперграфа.

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

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

Рассмотрим процесс поиска k-декомпозиции гиперграфа многоуровневым алгоритмом с точки зрения области поиска. На рисунке 29 показана эволюция ОП в процессе загрубления гиперграфа. Жирными линиями выделены области, доступные для поиска. В исходной задаче H₀ для поиска доступна вся ОП, затем, с каждой стадией загрубления, ОП уменьшается – отсеиваются бесперспективные направления.

Рис. 29. Изменения в области поиска в процессе загрубления гиперграфа.

9. Алгоритмическое обеспечение

9.1. Алгоритм реберного загрубления

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

, где w(e_k) – вес ребра e_k, E – множество гиперребер.

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

Рис. 30. Гиперграф (слева) и его граф притяжений (справа).

После определения притяжения каждой пары вершин запускается алгоритм пометки вершин, который формирует  группы вершин для объединения. Входными данными алгоритма являются степень  загрубления R, представляющая собой разницу количества вершин исходного и загрубленного гиперграфов, максимальный размер группы для объединения S_max и граф притяжений G(V,E,W), где W – веса ребер, т.е. характеристики притяжения вершин исходного гиперграфа. Приведем алгоритм реберного загрубления. 

 

 

 

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

1. m:=1
2. Определим «черный список» вершин  .
3. Определим отображение M:V→Z, так, что , эта функция представляет собой пометку каждой вершины о принадлежности какой-либо группе. При этом каждая группа ассоциирована с целым числом и M(v_i)=x означает, что вершина v_i принадлежит группе, ассоциированной с числом x.
4. Определим отображение S:Z→Z, так что S(x):=1, этак функция представляет информацию о размерах групп вершин, S(x)=y означает, что группа, ассоциированная с числом x, имеет в текущий момент работы алгоритма размер y, т.е. содержит y вершин.
5. Если R = 0 или B=V, то конец алгоритма.
6. Из множества вершин V случайно выбираем вершину v_i.
7. Выбираем вершину v_j, имеющую наибольшее притяжение с v_i: 
8. Если  =0, то помещаем вершины в «черный список»   и переходим на шаг 5.
9. Если M(v_i) = 0 и M(v_j) = 0, т.е. обе вершины не принадлежат ни одной группе, тогда они обе помещаются в группу m