MaxCliqueDyn алгоритм максимального клика - MaxCliqueDyn maximum clique algorithm

Разработчики:	Insilab (Национальный институт химии Словении)
Статус разработки:	Активный
Написано на:	C ++
Тип:	теория графов, алгоритм максимальной клики, проблема клики
Лицензия:	Стандартная общественная лицензия GNU
Интернет сайт:	инсилаб.org/ maxclique/

В Алгоритм MaxCliqueDyn является алгоритм для поиска максимума клика в неориентированном графе. Он основан на базовом алгоритме (алгоритм MaxClique), который находит максимальную клику ограниченного размера. Граница находится с использованием улучшенного алгоритма раскраски. MaxCliqueDyn расширяет алгоритм MaxClique, чтобы включить динамически изменяющиеся границы. Этот алгоритм был разработан Янез Конц и описание было опубликовано в 2007 году. По сравнению с более ранними алгоритмами, описанными в опубликованной статье ^[1] алгоритм MaxCliqueDyn улучшен улучшенным алгоритмом приближенной окраски (Алгоритм ColorSort ) и применяя более жесткие, более затратные в вычислительном отношении верхние границы для части пространства поиска. Оба улучшения сокращают время на поиск максимального клика. Помимо сокращения времени улучшенный алгоритм раскраски также уменьшает количество шагов, необходимых для поиска максимального клика.

Алгоритм MaxClique

Алгоритм MaxClique ^[2] является основным алгоритмом алгоритма MaxCliqueDyn. Псевдокод алгоритма:

процедура MaxClique (R, C) является    Q = Ø; QМаксимум = Ø; пока R ≠ Ø делать        выберите вершину p максимального цвета C (p) из множества R; R: = R  {p}; если | Q | + C (p)> | QМаксимум| тогда            Q: = Q ⋃ {p}; если R ⋂ Γ (p) ≠ Ø тогда                получить раскраску вершин C 'группы G (R ⋂ Γ (p)); MaxClique (R ⋂ Γ (p), C '); иначе если | Q |> | QМаксимум| тогда QМаксимум: = Q; Q: = Q  {p}; еще            возвращаться    конец пока

куда Q - множество вершин растущей в данный момент клики, Q_{Максимум} - это набор вершин наибольшей найденной клики, R - это набор вершин-кандидатов, а C - соответствующий ему набор цветовых классов. Алгоритм MaxClique рекурсивно ищет максимальную клику, добавляя и удаляя вершины в и изQ.

Алгоритм раскраски (ColorSort)

В алгоритме MaxClique алгоритм приближенной раскраски ^[2] используется для получения набора цветовых классовC. Алгоритм ColorSort - это улучшенный алгоритм приближенного алгоритма раскраски. В алгоритме приближенной раскраски вершины раскрашиваются одна за другой в том же порядке, в каком они появляются в наборе вершин-кандидатов. р так что если следующая вершина п несмежно со всеми вершинами в некотором цветовом классе, он добавляется к этому классу, и если п смежна по крайней мере с одной вершиной в каждом из существующих цветовых классов, она помещается в новый цветовой класс.

Алгоритм MaxClique возвращает вершины р упорядочены по цвету. Глядя на алгоритм MaxClique, становится ясно, что вершины v ∈ р с цветами C(v) < |Q_{Максимум}| − |Q| +1 никогда не будет добавлен к текущей кликеQ. Следовательно, сортировка этих вершин по цвету бесполезна для алгоритма MaxClique.

Улучшенная раскраска с помощью алгоритма ColorSort учитывает вышеуказанное наблюдение. Каждой вершине присвоен цветовой класс C_k. Если k < |Q_{Максимум}| − |Q| + 1 вершина перемещена в р (за последней вершиной вр). Если k ≥ |Q_{Максимум}| − |Q| + 1, чем вершина остается в цветовом классе C_k и не копируется в наборр. В конце все вершины в цветовых классах C_k куда k ≥ |Q_{Максимум}| − |Q| + 1 добавляются к задней части набора р как они появляются в каждом цветовом классе C_k и в порядке возрастания по индексуk. В алгоритме Color Sort только этим вершинам назначаются цвета C(v) = k.

Алгоритм ColorSort ^[1]

процедура ColorSort (R, C) является    max_no: = 1; kмин : = | QМаксимум| - | Q | + 1; если kмин ≤ 0, тогда kмин : = 1; j: = 0; C1 : = Ø; C2 : = Ø; за i: = от 0 до | R | - 1 делать        p: = R [i]; {i-я вершина в R} k: = 1; пока Ck ⋂ Γ (p) ≠ Ø делать            к: = к + 1; если k> max_no тогда            max_no: = k; Cmax_no + 1 : = Ø; конец, если        Ck : = Ck ⋃ {p}; если к <кмин тогда            R [j]: = R [i]; j: = j + 1; конец, если    конец для    C [j-1]: = 0; за k: = kмин to max_no делать        за i: = от 1 до | Ck| делать            R [j]: = Ck[я]; C [j]: = k; j: = j + 1; конец для    конец для

Пример

Граф выше может быть описан как набор-кандидат вершин р = {7⁽⁵⁾, 1⁽⁴⁾, 4⁽⁴⁾, 2⁽³⁾, 3⁽³⁾, 6⁽³⁾, 5⁽²⁾, 8⁽²⁾}. Множество вершин р теперь можно использовать в качестве входных данных как для приблизительного алгоритма раскраски, так и для алгоритма ColorSort. С использованием любого из двух алгоритмов построена таблица ниже.

k	Ck
1	7^(5), 5^(2)
2	1^(4), 6^(3), 8^(2)
3	4^(4), 2^(3), 3^(3)

Алгоритм приближенной раскраски возвращает набор вершин R = {7⁽⁵⁾, 5⁽²⁾, 1⁽⁴⁾, 6⁽³⁾, 8⁽²⁾, 4⁽⁴⁾, 2⁽³⁾, 3⁽³⁾} и соответствующий ему набор цветовых классов C = {1,1,2,2,2,3,3,3}. Алгоритм ColorSort возвращает набор вершин р = {7⁽⁵⁾, 1⁽⁴⁾, 6⁽³⁾, 5⁽²⁾, 8⁽²⁾, 4⁽⁴⁾, 2⁽³⁾, 3⁽³⁾} и соответствующий ему набор цветовых классов C = {-, -, -, -, -, 3,3,3}, где - представляет неизвестный цветовой класс сk < 3.

Алгоритм MaxCliqueDyn

Алгоритм MaxCliqueDyn основан на базовом алгоритме MaxClique, который использует алгоритм ColorSort вместо алгоритма приблизительной окраски для определения классов цвета. На каждом шаге алгоритма MaxClique алгоритм также повторно вычисляет степени вершин в R относительно вершины, в которой находится алгоритм в данный момент. Эти вершины затем сортируются в порядке убывания их степеней в графе G (R). Затем алгоритм ColorSort рассматривает вершины в R, отсортированные по их степеням в индуцированном графе G (R), а не в G. Таким образом, количество шагов, необходимых для нахождения максимальной клики, сокращается до минимума. Даже в этом случае общее время работы алгоритма MaxClique не улучшается, поскольку затраты на вычисления O (| R |²) определения степеней и сортировки вершин в R остается прежним.

Алгоритм MaxCliqueDyn ^[1]

процедура MaxCliqueDyn (R, C, уровень) является    S [уровень]: = S [уровень] + S [уровень − 1] - SСтарый[уровень]; SСтарый[уровень]: = S [уровень -1]; пока R ≠ Ø делать        выбираем вершину p с максимальной C (p) (последней вершиной) из R; R: = R  {p}; если | Q | + C [индекс p в R]> | QМаксимум| тогда            Q: = Q ⋃ {p}; если R ⋂ Γ (p) ≠ Ø тогда                если S [уровень] / ВСЕ ШАГИ предел тогда                    вычислить степени вершин в G (R ⋂ Γ (p)); сортировать вершины в R ⋂ Γ (p) в порядке убывания их степеней; конец, если                ColorSort (R ⋂ Γ (p), C ') S [уровень]: = S [уровень] + 1; ВСЕ ШАГИ: = ВСЕ ШАГИ + 1; MaxCliqueDyn (R ⋂ Γ (p), C ', уровень + 1); иначе если | Q | > | QМаксимум| тогда QМаксимум : = Q; Q: = Q  {p}; еще            возвращаться    конец пока

Ценить Т_предел можно определить путем экспериментов на случайных графиках. В исходной статье было определено, что алгоритм лучше всего работает для Т_предел = 0.025.

Рекомендации

1. Янез Конц; Душанка Янезич (2007). «Улучшенный алгоритм ветвей и границ для задачи максимальной клики» (PDF). MATCH-коммуникации в математической и компьютерной химии. 58 (3): 569–590. Исходный код
2. Эцудзи Томита; Томокадзу Секи (2003). «Эффективный алгоритм ветвей и границ для поиска максимальной клики» (PDF).