Алгоритм MaxCliqueDyn

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

Алгоритм MaxCliqueDyn — это алгоритм поиска максимальной клики в неориентированном графе.

MaxCliqueDyn основан на алгоритме MaxClique, который находит максимальную клику ограниченного размера. Граница находится с помощью алгоритма раскраски . MaxCliqueDyn расширяет MaxClique, включая динамически изменяющиеся границы.

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

Алгоритм MaxClique

Алгоритм MaxClique ^[2] — это базовый алгоритм, на основе которого расширяется MaxCliqueDyn. Псевдокод : алгоритма

procedure MaxClique(R, C) is
    Q = Ø, Q_max = Ø

    while R ≠ Ø do
        choose a vertex p with a maximum color C(p) from set R
        R := R\{p}
        if |Q| + C(p)>|Q_max| then
            Q := Q ⋃ {p}
            if R ⋂ Γ(p) ≠ Ø then
                obtain a vertex-coloring C' of G(R ⋂ Γ(p))
                MaxClique(R ⋂ Γ(p), C')
            else if |Q|>|Q_max| then Q_max := Q
            Q := Q\{p}
        else
            return
    end while

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

Алгоритмы окраски

Примерный алгоритм окраски

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

Алгоритм MaxClique возвращает вершины R, упорядоченные по цветам. Вершины $v\in R$ с цветами $C(v)<{|Q_{max}|}-{|Q|}+1$ никогда не добавляются в текущую клику Q . Следовательно, сортировка этих вершин по цвету бесполезна для алгоритма MaxClique.

Цветовая сортировка

Алгоритм ColorSort улучшает алгоритм приблизительной раскраски, принимая во внимание приведенное выше наблюдение. Каждой вершине присвоен цветовой класс. $C_{k}$ . Если $k<{|Q_{max}|}-{|Q|}+1$ , вершина перемещается в множество R (за последней вершиной в R ). Если $k\geq {|Q_{max}|}-{|Q|}+1$ , то вершина остается в $C_{k}$ и не перемещается в R . В конце концов, все вершины, оставшиеся в $C_{k}$ (где $k\geq {|Q_{max}|}-{|Q|}+1$ ) добавляются в конец буквы R по мере их появления в каждом $C_{k}$ и в порядке возрастания по индексу $k$ . В алгоритме ColorSort только этим вершинам присваиваются цвета. $C(v)=k$ .

Псевдокод алгоритма ColorSort: ^[1]

procedure ColorSort(R, C) is
    max_no := 1;
    k_min := |Q_max| − |Q| + 1;
    if k_min ≤ 0 then k_min := 1;
    j := 0;
    C₁ := Ø; C₂ := Ø;

    for i := 0 to |R| − 1 do
        p := R[i]; {the i-th vertex in R}
        k := 1;
        while C_k ⋂ Γ(p) ≠ Ø do
            k := k+1;
        if k > max_no then
            max_no := k;
            C_{max_no+1} := Ø;
        end if
        C_k := C_k ⋃ {p};
        if k < k_min then
            R[j] := R[i];
            j := j+1;
        end if
    end for

    C[j−1] := 0;

    for k := k_min to max_no do
        for i := 1 to |C_k| do
            R[j] := C_k[i];
            C[j] := k;
            j := j+1;
        end for
    end for

Пример

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

к	С _к
1	7 ⁽⁵⁾, 5 ⁽²⁾
2	1 ⁽⁴⁾, 6 ⁽³⁾, 8 ⁽²⁾
3	4 ⁽⁴⁾, 2 ⁽³⁾, 3 ⁽³⁾

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

Алгоритм MaxCliqueDyn

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

Псевдокод алгоритма MaxCliqueDyn: ^[1]

procedure MaxCliqueDyn(R, C, level) is
    S[level] := S[level] + S[level−1] − S_old[level];
    S_old[level] := S[level−1];

    while R ≠ Ø do
        choose a vertex p with maximum C(p) (last vertex) from R;
        R := R\{p};
        if |Q| + C[index of p in R] > |Q_max| then
            Q := Q ⋃ {p};
            if R ⋂ Γ(p) ≠ Ø then
                if S[level]/ALL STEPS < T_limit then
                    calculate the degrees of vertices in G(R ⋂ Γ(p));
                    sort vertices in R ⋂ Γ(p) in a descending order
                    with respect to their degrees;
                end if
                ColorSort(R ⋂ Γ(p), C')
                S[level] := S[level] + 1;
                ALL STEPS := ALL STEPS + 1;
                MaxCliqueDyn(R ⋂ Γ(p), C', level + 1);
            else if |Q| > |Q_max| then Q_max := Q;
            Q := Q\{p};
        else
            return
    end while

значения T _Предел можно определить путем экспериментирования на случайных графиках. В оригинальной статье было определено, что алгоритм лучше всего работает при T _limit = 0,025.

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Янез Конц; Душанка Янезич (2007). «Улучшенный алгоритм ветвей и границ для задачи максимальной клики» (PDF) . МАТЧ-коммуникации в математической и компьютерной химии . 58 (3): 569–590. Исходный код
^ Перейти обратно: ^а ^б Томита, Эцудзи; Секи, Томокадзу (2003). «Эффективный алгоритм ветвей и границ для поиска максимальной клики» (PDF) . В Калуде, CS; Диннин, MJ; Вайновски, В. (ред.). ДМТСС 2003 . ЛНКС. стр. 278–289. См. также: Э. Томита; Т. Секи (2007). «Эффективный алгоритм ветвей и границ для поиска максимальной клики». Джей Глоб Оптим . 37 : 95–111. дои : 10.1007/s10898-006-9039-7 .

[Konc2007-1] Перейти обратно: ^а ^б ^с ^д Янез Конц; Душанка Янезич (2007). «Улучшенный алгоритм ветвей и границ для задачи максимальной клики» (PDF) . МАТЧ-коммуникации в математической и компьютерной химии . 58 (3): 569–590. Исходный код

[Tomita2003-2] Перейти обратно: ^а ^б Томита, Эцудзи; Секи, Томокадзу (2003). «Эффективный алгоритм ветвей и границ для поиска максимальной клики» (PDF) . В Калуде, CS; Диннин, MJ; Вайновски, В. (ред.). ДМТСС 2003 . ЛНКС. стр. 278–289. См. также: Э. Томита; Т. Секи (2007). «Эффективный алгоритм ветвей и границ для поиска максимальной клики». Джей Глоб Оптим . 37 : 95–111. дои : 10.1007/s10898-006-9039-7 .

[1]

[2]