Диссертация (1149246), страница 4

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

Текст из файла (страница 4)

Эта оценка доказывала тот факт, что N P -сложную задачу можно решить быстрее, чем методомполного перебора.В работе Хука [44] изучалась взаимосвязь максимального независимого множества и специального класса двудольных графов. На основе этого был представлен способ определения начального решения для задачи о наибольшемнезависимом множестве.19Одним из наиболее успешных алгоритмов поиска наибольшей клики сталалгоритм Балаша (Balas). Он реализовал подход, отличающийся от другихалгоритмов того времени. Идея заключается в следующем.

Для начала находится индуцированный триангулированный подграф исследуемого графа. Внайденном подграфе определяется наибольшая клика. Эта клика представляетсобой потенциальное решение задачи о наибольшей клики, а так же обеспечивает нижнюю границу для других возможных решений. Далее используeтсяпроцедуру окраски с целью расширения найденного подграфа. Преимуществоподхода, предложенного Балашем, заключается в том, что он позволяет уменьшить количество подзадач, полученных от каждого узла дерева поиска, что всвою очередь позволяет уменьшить само дерево поиска. В результате сравненияс другими алгоритмами было установлено, что дерево поиска, порожденноеалгоритмом Балаша, действительно меньше, чем у других алгоритмов [57].Затем в 1986 году Робсон (Robson) [60] модифицировал рекурсивный алгоритм Тарьяна–Трояновски.

Его алгоритм стал намного компактнее своегопредшественника. Кроме этого Робсону удалось провести тщательную процедуру теоретической оценки сложности предложенного алгоритма. Согласно анализу рекуррентных соотношений, приведенных в [60], сложность его алгоритма:O(2 0.276n ). В основе этого алгоритма лежит соотношение:ms(G) = max(1 + ms(G − N (B)), ms(G − B)).Основная идея заключается в том, что любое максимальное независимое множество в графе G либо содержит некоторую вершину B (и, значит, не содержитсоседей этой вершины N (B)), либо нет (тогда поиск максимального независимого множества проводится в подграфе G−B).

Вся процедура поиска искомогомножества базируется на детальном рассмотрении конструкций максимальныхнезависимых множеств в зависимости от степени вершин графа.20В 1990 году Пардалос и Филлипс (Phillips) [56] представили алгоритм, основанный на постановке задачи поиска максимума клик в виде задачи глобальнойоптимизации.В 2001 году Робсон [61] несколько модифицировал свой алгоритм 86-го года,рассмотрев детально конструкции искомых множеств в зависимости от болеевысоких степеней (>3) вершин исследуемого графа.

Вслед за этим, Фоминв своей работе [36] 2006 года представил алгоритм, который базируется насоотношении, представляющим собой несколько модифицированное соотношение Робсона:mis(G) = max{mis(G − v − M (v)), 1 + mis(G − N [v])},где M (v) – это множество отражений вершины v. Ему, как и Робсону, удалосьпровести анализ теоретической оценки сложности разработанного алгоритма.Согласно расчетам Фомина оценка временной сложности его алгоритма:O(2 0.288n ).п.

1. Метод полного перебора и метод поиска свозвращением (алгоритм Брона-Кербоша)В силу того, что количество всевозможных вариантов подмножеств вершинграфа конечно, хоть и очень велико для графов больших размерностей, самымпростым и очевидным способом построения максимальных независимых множеств является метод полного перебора.Например, наибольшее независимое множество можно найти с помощьюследующего алгоритма [9]:Вход: граф G(V, E)Выход: наибольшее независимое множество Xm := 0 {наилучшее известное значение мощности искомогонезависимого множества}21construct S(V ) {множество всевозможных подмножеств V }for Y ∈ S(V ) doif Y : ∀ u, v ∈ Y (u, v) ∈/ E & |Y | > m thenm := |Y |; X := Y {наилучшее известное значение X}end ifend forВ случае нахождения всех максимальных независимых множеств каждоенайденное множество Y : ∀ u, v ∈ Y (u, v) ∈/ E, необходимо проверять намаксимальную независимость.

Для этого нужно определять, является ли множество Y подмножеством какого-либо другого найденного независимого множества.С учетом того, что число всевозможных вариантов подмножеств множествавершин V графа G равно 2n , где n = |V |, вычислительная сложность полногоперебора есть O(2n ).Основным способом уменьшения количества рассматриваемых вариантовявляется поиск с возвращением, именно этот метод лежит в основе алгоритмаБрона-Кербоша [27]. Ниже представлен псевдокод этого алгоритма [9].Вход: граф G(V, E), заданный списками смежности H(v){∀v ∈ V H(v) = {r ∈ V | (v, r) ∈ E}}Выход: последовательность максимальных независимых множествk := 0 {количество элементов в текущем независимом множестве}S[k] := ∅ {S[k] – независимое множество из k вершин}Q− [k] := ∅ {Q− [k] – множество вершин, использованных длярасширения S[k]}Q+ [k] := V {Q+ [k] – множество вершин, которые можно использоватьдля расширения S[k]}M1 : {шаг вперед}select v ∈ Q+ [k] {расширяющая вершина}S[k + 1] := S[k] ∪ {v} {расширенное множество}22Q− [k + 1] := Q− [k] \ H(v) {вершина v использована для расширения}Q+ [k + 1] := Q+ [k] \ (H(v) ∪ {v}) {все вершины, смежные с v, не могутбыть использованы для расширения}k := k + 1M2 : {проверка}for u ∈ Q− [k] doif H(v) ∩ Q+ [k] = ∅ thengoto M3 {можно возвращаться}end ifend forif Q+ [k] = ∅ thenif Q− [k] = ∅ thenyield S[k] {множество S[k] максимально}end ifgoto M3 {можно возвращаться}elsegoto M1 {можно идти вперед}end ifM3 : {шаг назад}v = last(S[k]) {последний добавленный элемент}k := k − 1S[k] := S[k + 1] − {v}Q− [k] := Q− [k] ∪ {v} {вершина уже добавлялась}Q+ [k] := Q+ [k] \ {v}if k = 0 & Q+ [k] = ∅ thenstop {перебор завершен}elsegoto M2 {переход на проверку}end if23Программная реализация метода полного перебора для поиска наибольшегонезависимого множества и для перечисления всех максимальных независимыхмножеств представлена в приложении 1 и приложении 2.

Алгоритм БронаКербоша реализован без goto и явной рекурсии, с ним можно ознакомитьсяв приложении 3.п. 2. Алгоритм Робсона и его модификацияВ своей работе [60] Робсон представил алгоритм, предназначенный для вычисления мощности наибольшего независимого множества. Псевдокод алгоритма содержит комментарии, используя которые можно модифицировать этоталгоритм для нахождения наибольшего независимого множества, а не толькоего мощности. В представленном ниже алгоритме Робсона цифрами отмеченыстрочки, которые необходимо изменить.Рассмотрим основные обозначения в алгоритме:– d(v) – степень вершины v;– N (v) – множество соседей вершины v (соседями называются смежныевершины);– N (v) = N (v) + v;– N 2 (v) – множество соседей вершин из N (v), за исключением самой вершины v;– вершина A доминирует над вершиной B, если N (A) ⊂ N (B).Основная функция ms(G):function ms(G : graph) : integer;beginif not connected (G) thenbeginC := smallest connected component of G;(1) return ms(G − C) + (if |C| ≤ 2 then 1 else ms(C))24end;(2) if |G| ≤ 1 then return |G|;choose A, B vertices of G such that(i) d(A) is minimal and(ii) (A, B) is an edge of G and d(B) is maximal over all neighbors ofvertices with degree d(A);(3) if d(A) = 1 then return 1 + ms(G − N (A));if d(A) = 2 thenbeginB ′ := N (A) − B; {the other neighbor of A}(4) if edge(B, B ′ ) then return 1 + ms(G − N (A));(5) return max(2 + ms(G − N (B) − N (B ′ )), 1 + ms2 (G − N (A), N 2 (A)))end;(6) if d(A) = 3 then return max(ms2 (G − A, N (A)), 1 + ms(G − N (A)))if A dominates B then return ms(G − B);(7) return max(ms(G − B), 1 + ms(G − N (B)))end;Вспомогательная функция ms1 (G, S):function ms1 (G : graph; S : vertexset): integer;{S = {s1 , s2 | d(s1 ) ≤ d(s2 )}}beginif d(s1 ) ≤ 1 then return ms(G);if edge(s1 , s2 ) thenif d(s1 ) ≤ 3 then return ms(G)(8) else return max(ms(G − N (s1 )), ms(G − N (s2 ))) + 1;if N (s1 ) ∩ N (s2 ) ̸= ∅ then return ms1 (G − N (s1 ) ∩ N (s2 ), S);if d(s2 ) = 2 thenbegin25E, F :=the elements of N (s1 );{independent sets to be considered contains s1 or (s2 , E and F )}(9) if edge(E, F ) then return 1 + ms(G − N (s1 ));(10) if N (E) + N (F ) − s1 ⊂ N (s2 )then return 3 + ms(G − N (s1 ) − N (s2 )){N (s1 ) + N (s2 ) has no 4 element independent set containing s1 or s2and [E, F, s2 ] dominates every other 3 element independent set}(11) elsereturn max(1 + ms(G − N (s1 )), 3 + ms(G − N (E) − N (F ) − N (s2 )))end;(12) return max(ms(G − N (s2 )), ms2 (G − N (s1 − s2 , N (s2 ))) + 1{independent set contains s2 or (s1 and two element of N (s2 ))}end {of ms1 };Вспомогательная функция ms2 (G, S)function ms2 (G : graph; S : vertexset): integer;begin {ms2 .

The elements of S are s1 , s2 , . . . with d(si ) ≤ d(si+1 )}(13) if |S| ≤ 1 then return 0;(14) if |S| = 2 then if edge(s1 , s2 ) then return 0(15) else return 2 + ms(G − N (s1 ) − N (s2 ));if |S| = 3 thenbegin(16) if d(s1 ) = 0 then return 1 + ms1 (G − s1 , S − s1 );(17) if edge(s1 , s2 ) and edge(s2 , s3 ) and edge(s3 , s1 ) then return 0;if edge(si , sj ) and edge(si , sk ) (j ̸= k) then(18) return 2 + ms(G − N (sj ) − N (sk ));if edge(si , sj ) then(19) return 1 + ms1 (G − N (sk ), [si , sj ])(i ̸= k ̸= j) :{independent set cannot contain si and sj and so contains one26of them and sk .}if vertex v ∈ N (si ) ∩ N (sj )(i ̸= j) then return ms2 (G − v, S);{independent set contains si and sj and so not v.}(20) if d(s1 ) = 1 then return 1 + ms1 (G − N (s1 ), S − s1 );(21) returnmax(1 + ms1 (G − N (s1 ), S − s1 ), 2 + ms2 (G − N (s2 ) − N (s3 ) − s1 , N (s1 )))end {|S| = 3};if |S| = 4 thenif G has a vertex of degree ≤ 3 then return ms(G)(22) else return max(1 + ms(G − N (s1 )), ms2 (G − s1 , S − s1 ));return ms(G)end {of ms2 }Ниже представлен модифицированный алгоритм Робсона, позволяющий определить элементы наибольшего независимого множества, а не только его мощность.

Приведены только измененные строки псевдокода.Основная функция ms(G : graph) : vertexset(1) return ms(G − C) ∪ (if |C| ≤ 2 then {v | v ∈ C} else ms(C));В случае, если наименьшая компонента связности C состоит из двух и менеевершин, в независимое множество включается одна любая вершина v ∈ C.(2) if |G| ≤ 1 then return {G};(3) if d(A) = 1 then return {A} ∪ ms(G − N (A));Мощность независимого множества увеличивается на единицу за счет добавления к нему вершины A.

Дальнейший поиск максимального независимогомножества осуществляется в графе G − N (A).(4) if edge(B, B ′ ) then return {A} ∪ ms(G − N (A));(5) max1 := 2 + |ms(G − N (B) − N (B ′ ))|;max2 := 1 + |ms2 (G − N (A), N 2 (A))|;if max(max1 , max2 ) = max127then return {B, B ′ } ∪ ms(G − N (B) − N (B ′ ));else return {A} ∪ ms2 (G − N (A), N 2 (A));(6) if d(A) = 3 then max1 := |ms2 (G − A, N (A))|;max2 := 1 + |ms(G − N (A))|;if max(max1 , max2 ) = max1 then return ms2 (G − A, N (A));else return {A} ∪ ms(G − N (A))(7) max1 := |ms(G − B)|; max2 := 1 + |ms(G − N (B))|;if max(max1 , max2 ) = max1 then return ms(G − B);else return {B} ∪ ms(G − N (B));end {of ms}Вспомогательная функция ms1 (G : graph, S : vertexset) : vertexset(8) else max1 := |ms(G − N (s1 ))|; max2 := |ms(G − N (s2 ))|;if max(max1 , max2 ) = max1 then return {s1 } ∪ ms(G − N (s1 ));else return {s2 } ∪ ms(G − N (s2 ));(9) if edge(E, F ) then return {s1 } ∪ ms(G − N (s1 ));(10) if N (E) + N (F ) − s1 ⊂ N (s2 )then return {E, F, s2 } ∪ ms(G − N (s1 ) − N (s2 ));(11) max1 := 1 + |ms(G − N (s1 ))|;max2 := 3 + |ms(G − N (E) − N (F ) − N (s2 ))|;if max(max1 , max2 ) = max1 then return {s1 } ∪ ms(G − N (s1 ));else return {E, F, s2 } ∪ ms(G − N (E) − N (F ) − N (s2 ));(12) max1 := |ms(G − N (s2 ))|;max2 := |ms2 (G − N (s1 ) − s2 , N (s2 ))|;if max(max1 , max2 ) = max1 then return {s2 } ∪ ms(G − N (s2 ));else return {s1 } ∪ ms2 (G − N (s1 ) − s2 , N (s2 ));end {of ms1 }Вспомогательная функция ms2 (G : graph, S : vertexset) : vertexsetbegin {ms2 .

Характеристики

Список файлов диссертации