Диссертация (1149246), страница 8
Текст из файла (страница 8)
Ниже приведены результаты тестирования.Зафиксировав плотность в пределах 10%, определили зависимость времяработы всех трех алгоритмов от размерности генерируемых графов. Как видноиз Рисунка 16 время работы полного перебора даже при небольших размерностях значительно превышает время работы двух других алгоритмов.При увеличении размерности до 17 (Рисунок 17) оно достигает значения50 секунд, в то время как алгоритму Брона-Кербоша и AllIS потребовалось небольше 0.6 секунд для обработки графов с плотностью 10%.Такая же картина наблюдается и при значении плотности p = 50%(Рисунок 18). Действительно, время работы полного перебора экспоненциально зависит от размерности обрабатываемого графа, при этом плотность графанезначительно влияет на скорость его работы (Рисунок 19), чего нельзя сказатьоб алгоритмах Брона-Кербоша и AllIS.Из-за значительной разницы в скорости работы полного перебора и двухдругих алгоритмов, на Рисунке 19 нельзя увидеть, как именно ведут себя алгоритмы Брона-Кербоша и AllIS при увеличении плотности, поэтому представимрезультаты их работы на отдельном графике (Рисунок 20).57Рис.
16: Зависимость времени работы алгоритмов от размерности графов при фиксированнойплотности p = 10%.Уже при размерности n = 12 можно заметить, что при значениях плотностиот 10% до 60% скорость работы AllIS превышает скорость работы алгоритмаБрона-Кербоша, при высокой плотности (p > 60%) их скорости практическисовпадают, а для разреженных графов (p < 10%) алгоритм AllIS работаетбыстрее Брона-Кербоша. При увеличении размерности графов разница в скорости работы алгоритмов при различных значениях плотности становится ещеболее заметной (Рисунок 21).Рассмотрим подробнее поведение алгоритмов при обработке разреженныхграфов.
На Рисунках 22 и 23 представлены графики зависимости времениработы алгоритмов от размерности графов при значении плотности p = 6%и p = 4% соответственно. Как и ожидалось, скорость роста времени работыалгоритма Брона-Кербоша намного выше скорости алгоритма AllIS.58Рис. 17: Зависимость времени работы алгоритмов от размерности графов при фиксированнойплотности p = 10%.Рис. 18: Зависимость времени работы алгоритмов от размерности графов при фиксированнойплотности p = 50%.59Рис. 19: Зависимость времени работы алгоритмов от плотности графов при фиксированнойразмерности n = 12.Рис.
20: Зависимость времени работы алгоритмов Брона-Кербоша и AllIS от плотностиграфов при фиксированной размерности n = 12.60Рис. 21: Зависимость времени работы алгоритмов Брона-Кербоша и AllIS от плотностиграфов при фиксированной размерности n = 20.Рис. 22: Зависимость времени работы алгоритмов Брона-Кербоша и AllIS от размерностиграфов при значении плотности p = 6%.61Рис.
23: Зависимость времени работы алгоритмов Брона-Кербоша и AllIS от размерностиграфов при значении плотности p = 4%.62ГЛАВА 3. АЛГОРИТМ MAXIS ПОИСКАНАИБОЛЬШЕГО НЕЗАВИСИМОГО МНОЖЕСТВА§1. Модификация алгоритма AllIS для решения задачи онаибольшем независимом множествеЧасто в задачах не требуется построить все максимальные независимыемножества, а только найти наибольшее из них. В данном случае, конечно,можно также воспользоваться алгоритмом AllIS для нахождения всех МНМ, азатем выбрать среди них множество наибольшей мощности.
Но так как числотаких множеств может быть очень велико и с ростом размерности их числоэкспоненциально увеличивается [52], то целесообразнее ввести дополнительныемеханизмы отсечения ветвей дерева поиска, которые не могут дать множествабольшей мощности чем то, что уже построено на текущий момент. Модификацию алгоритма AllIS, ориентированную на нахождение только наибольшегонезависимого множества, в дальнейшем будем называть алгоритмом MaxIS.procedure MaxIS (G = [V, SV,A ])begink := 0 //номер уровня дерева поискаQ := ∅ //текущее независимое множествоQmax := ∅ //текущее наибольшее независимое множествоα∗k−1 := (β∗k−1 , γ∗k−1 )ω[α∗k−1 ] := V //опорное множествоS[α∗k−1 ] := SV,A // множество несмежных пар в графе Gconstruct D[αk ], αk = (β k , γ k ), {β k , γ k } ∈ V , αk ∈ SV,Acontinue := truewhile continue=true doif S[α∗k−1 ] = ∅ thenif (ω[α∗k−1 ] ̸= ∅ and 2k + 1 > |Qmax |) then63Qmax := Q ∪ {δ}, δ ∈ ω[α∗k−1 ], ω[α∗k−1 ] := ∅end ifif k = 0 then continue:=falseelse Q := Q \ ({β∗k−1 , γ∗k−1 } ∪ r[α∗k−1 ]), k := k − 1end ifelse choose α∗k = (β∗k , γ∗k ) ∈ S[α∗k−1 ] : |D[α∗k ]| = maxαk ∈S[α∗k−1 ] |D[αk ]|r[α∗k ] := ∅if |D[α∗k ]| + 2k > |Qmax | thenR[α∗k ] := {(β k , γ k ) | D[αk ] ⊆ D[α∗k ], (β k , γ k ) ∈ S[α∗k−1 ] \ {α∗k }}Q := Q ∪ {β∗k , γ∗k }, ω[α∗k ] := D[α∗k ] \ {β∗k , γ∗k }if |ω[α∗k ]| = 0 then S[α∗k ] := ∅, Qmax := Qelif |ω[α∗k ]| = 1 then S[α∗k ] := ∅, Qmax := Q ∪ ω[α∗k ]elif |ω[α∗k ]| > 1 then S[α∗k ] := S[α∗k−1 ] ∩ (ω[α∗k ] × ω[α∗k ])if |S[α∗k ]| ̸= 0 and |S[α∗k ]| =|ω[α∗k ]|(|ω[α∗k ]|−1)2thenr[α∗k ] := ω[α∗k ], Q := Q ∪ r[α∗k ], Qmax := QS[α∗k ] := ∅, ω[α∗k ] := ∅elif |S[α∗k ]| ̸= 0 and |S[α∗k ]| =|ω[α∗k ]|(|ω[α∗k ]|−1)2− 1 thenif |D[α∗k ]| + 2k − 1 > |Qmax | thenchoose v ∈ ω[α∗k ] : ∃ p ∈ ω[α∗k ] : avp = 1r[α∗k ] := ω[α∗k ] \ {v}, Q := Q ∪ r[α∗k ], Qmax := Qend ifS[α∗k ] := ∅, ω[α∗k ] := ∅elif |S[α∗k ]| ̸= 0 and |S[α∗k ]| =|ω[α∗k ]|(|ω[α∗k ]|−1)2− 2 thenif |D[α∗k ]| + 2k − 1 > |Qmax | thenif ∃v ∈ ω[α∗k ] : ∃ p, q ∈ ω[α∗k ] : avp = 1 & avq = 1 thenr[α∗k ] := ω[α∗k ] \ {v}, Q := Q ∪ r[α∗k ], Qmax := Qelseif |D[α∗k ]| + 2k − 2 > |Qmax | thenchoose v, t ∈ ω[α∗k ] : ∃ p, q ∈ ω[α∗k ] : avp = 1 & atq = 164r[α∗k ] := ω[α∗k ] \ {v, t}, Q := Q ∪ r[α∗k ], Qmax := Qend ifend ifS[α∗k ] := ∅, ω[α∗k ] := ∅end ifend iffor all αk+1 ∈ S[α∗k ] construct D[αk+1 ] end doS[α∗k−1 ] := S[α∗k−1 ] \ (R[α∗k ] ∪ {α∗k }), k := k + 1else S[α∗k ] := ∅end ifend ifend doreturn Qmaxend {of MaxIS }§2.
Теоретическое обоснование алгоритма MaxISВ силу того, что алгоритм MaxIS является модификацией алгоритма AllIS,он опирается на те же теоремы, что и его предшественник. Не будем повторятьдоказательства корректности работы алгоритма, приведенного во второй главедля алгоритма AllIS, а рассмотрим только нововведения в работе алгоритмаMaxIS и обоснуем правомерность их использования.Основное изменение в алгоритме MaxIS – это введение отсечения ветвейдерева поиска, исходя из мощности базового множества выбранного узла. Докажем следующую теорему:Теорема 5. Если в некотором подграфе Gk ⊂ Gk−1 ⊂ . .
. ⊂ G0 для базовогомножества выбранного узла α∗k = (β∗k , γ∗k ) выполнено условие:|D[α∗k ]| + 2k ≤ |Qmax |,65тогда мощность любого максимального независимого множества, содержащего пару вершин β∗k , γ∗k , не превзойдет мощности текущего наибольшегонезависимого множества:|Q[α∗k ]| ≤ |Qmax |.Доказательство. Максимальное независимое множество Q[α∗k ] можно представить в следующем виде:Q[α∗k ] = {β∗0 , γ∗0 , β∗1 , γ∗1 , . . .
, β∗k−1 , γ∗k−1 } ∪ {β∗k , γ∗k } ∪ QGk+1 ,где Gk+1 = (ω[α∗k ], S[α∗k ]).Очевидно, что |QGk+1 | ≤ |ω[α∗k ]|. Следовательно,|Q[α∗k ]| ≤ |{β∗0 , γ∗0 , β∗1 , γ∗1 , . . . , β∗k−1 , γ∗k−1 }| + |{β∗k , γ∗k }| + |ω[α∗k ]|.По определению опорного множества ω[α∗k ] = D[α∗k ] \ {β∗k , γ∗k }, а значит,|ω[α∗k ]| + |{β∗k , γ∗k }| = |D[α∗k ]|.На каждом k-м уровне дерева поиска независимое множество расширяетсядвумя вершинами β∗k и γ∗k , поэтому|β∗0 , γ∗0 , β∗1 , γ∗1 , . . .
, β∗k−1 , γ∗k−1 | = 2k.Таким образом, получаем, что |Q[α∗k ]| ≤ 2k + |D[α∗k ]|. А значит, если|D[α∗k ]| + 2k ≤ |Qmax |, то и |Q[α∗k ]| ≤ |Qmax |, что и требовалось доказать.Следовательно, если для некоторого узла α∗k = (β∗k , γ∗k ), для которого базовоемножество имеет наибольшую мощность:|D[α∗k ]| =maxαk ∈S[α∗k−1 ]|D[αk ]|,выполняется условие теоремы 5, то этот узел исключается из множества S[α∗k−1 ],так как в этом случае не удастся построить МНМ большей мощности, чем то,что уже имеется.
Если же среди элементов S[α∗k−1 ] найдется узел αk :|D[αk ]| + 2k > |Qmax |,66тогда переходим к построению ветви дерева поиска, идущей из этого узла. Впротивном случае, возвращаемся на предыдущий уровень.Второе изменение в алгоритме MaxIS связано с отказом от использованияокрестностей. Покажем, что в отличие от алгоритма AllIS, для нахождениянаибольшего независимого множества использовать окрестность нецелесообразно.По алгоритму AllIS поиска всех максимальных независимых множеств длятого, чтобы исключить из рассмотрения на k-м уровне дерева поиска узел α∗k ,необходимо существование в окрестности этого узла МНМ Q[α∗k ] ∈ P [α∗k ]:jjQ[α∗k ] ≡ D[α∗k ] ∪ (∪k−1j=0 {β∗ , γ∗ }).Следовательно, |Q[α∗k ]| = |D[α∗k ]| + 2k.
Пусть мощность текущего наибольшего независимого множества |Qmax | = m, |Q[α∗k ]| = µ. Очевидно, µ ≤ m.Получаем, что|D[α∗k ]| + 2k = µ ≤ m = |Qmax |.Таким образом, узел α∗k удовлетворяет условию теоремы 3, а потому мощностьмаксимального независимого множество Q[α∗k ], которое можно построить, рассмотрев этот узел, не превысит мощность текущего наибольшего независимогомножества Qmax . По алгоритму MaxIS рассматриваются только те ведущиеэлементы α∗k , для которых выполняется условие: |D[α∗k ]| + 2k > |Qmax |, нодля таких узлов не имеет смысл строить окрестность, т.
к. в их окрестностиневозможно существование МНМ Q[α∗k ]:jjQ[α∗k ] ≡ D[α∗k ] ∪ (∪k−1j=0 {β∗ , γ∗ }).И наконец третья модификация. Каждый раз после принятия решения опостроении ветви дерева поиска, идущей из текущего выбранного узла α∗k ,необходимо подсчитать |S[α∗k ]|.Пусть |ω[α∗k ]| = m. Рассмотрим процесс построения максимальных независимых множеств в зависимости от мощности множества S[α∗k ].671) Если |S[α∗k ]| =m(m−1),2значит, текущее опорное множество ω[α∗k ] цели-ком представляет собой независимое множество (Рисунок 24). В этом случае,текущим наибольшим независимым множеством будет множество:Qmax = {β∗0 , γ∗0 , β∗1 , γ∗1 , ..., β∗k−1 , γ∗k−1 } ∪ ω[α∗k ].Рис. 24: Граф, индуцированный опорным множеством ω[α∗k ] = {δ1 , δ2 , δ3 , δ4 , δ5 } при значении|S[α]| =m(m−1).22) Условие |S[α∗k ]| =m(m−1)−12говорит о том, что среди элементов опорногомножества ω[α∗k ] только две вершины соединены ребром (Рисунок 25).Рис.
25: Граф, индуцированный опорным множеством ω[α∗k ] = {δ1 , δ2 , δ3 , δ4 , δ5 } при значении|S[α]| =m(m−1)2− 1.В случае выполнения условия |D[α∗k ]| + 2k − 1 > |Qmax |, в качестве новогонаибольшего независимого множества будет выступать множествоQmax = {β∗0 , γ∗0 , β∗1 , γ∗1 , ..., β∗k−1 , γ∗k−1 } ∪ (ω[α∗k ] \ {δ}),68где вершина δ – одна из пары вершин опорного множества ω[α∗k ], которыесоединены между собой ребром. В противном случае отказываемся от текущегоузла α∗k и переходим к выбору нового ведущего элемента на k-м уровне.3) В случае, когда |S[α∗k ]| =m(m−1)2− 2, некоторые вершины опорного мно-жества ω[α∗k ] соединены ребрами, причем количество ребер однозначно равнодвум, а количество вершин, инцидентных этим ребрам, может быть равно либотрем (Рисунок 26(а)), либо четырем (Рисунок 26(б)). В такой ситуации нужноопределить, сколько различных вершин участвует в образовании ребер.а)б)Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
