Диссертация (1149246), страница 10
Текст из файла (страница 10)
Искомое максимальное независимое множествоQmax = {3, 4, 5, 6, 8, 10}.§4. Тестирование программной реализацииАлгоритм MaxIS сравнивался при тестировании с методом Робсона. Согласно теоретической оценке сложности алгоритм Робсона является наиболее эффективным для решения задачи о ННМ, именно этот факт объясняет выбор егов качестве оппонента для алгоритма MaxIS. Для тестирования генерировалисьграфы с различными значениями плотности. В процессе тестирования графоводной и той же плотности были рассмотрены графы размерности n ∈ [10, 100] cшагом равным единице.
Количество графов для каждого значения размерностиравнялось 10. Таким образом, каждый график, приведенный в данном параграфе, отражает результат обработки 910 графов. Исключение составляют толькографики, показывающие зависимость времени работы алгоритмов от плотностиграфов в рамках фиксированной размерности. В данном случае было обработано 1010 графов, так как рассматривались графы со значением плотностиp ∈ [0%, 100%] с шагом равным 1%. Количество графов для каждого значения плотности так же равнялось 10. В качестве результирующего времениработы выбиралось среднее арифметическое значение времени для графов содинаковыми характеристиками [n, p].
В результате тестирования были получены зависимости времени t (с) поиска решения от размерности n графа прификсированной плотности p (%) и от плотности графа в рамках фиксированнойразмерности. Ниже приведены результаты тестирования.НаРисунке28представленыграфикидляалгоритмаРобсона,MaxIS и полного перебора, несколько модифицированного для поиска наибольшего независимого множества.78Рис. 28: Зависимость времени работы алгоритмов от плотности графов при фиксированнойразмерности n = 12.В данном варианте алгоритма полного перебора отсутствует проверка намаксимальную независимость полученного независимого множества.
Каждыйраз он в качестве ННМ сохраняет текущее независимое множество, имеющеебольшую мощность среди всех найденных к этому моменту. Независимое множество наибольшей мощности, очевидно, будет являться и наибольшим максимальным независимым множеством. Это небольшое изменение в алгоритменемногим улучшило время его работы. В дальнейшем сравнение с алгоритмомполного перебора проводиться не будет.Конечно, на фоне полного перебора разница в скорости работы алгоритмаРобсона и MaxIS едва заметна. Рассмотрим результаты их тестирования наотдельном графике (Рисунок 29).Из этого графика видно, что при значении плотности p < 60% время работыалгоритма MaxIS превосходит время работы алгоритма Робсона, но при увеличении плотности p > 60% время работы алгоритма MaxIS уменьшается ипрактически становится равным времени работы алгоритма Робсона.79Рис.
29: Зависимость времени работы алгоритмов Робcона и MaxIS от размерности графовпри фиксированной размерности n = 12.Для того чтобы определить порядок временнòго роста алгоритмовMaxIS и Робсона при различных значениях плотности, представим результатыих тестирования в логарифмической шкале. Для этого переведем значения времени t в секундах в миллисекунды, а затем по оси OY отметим значения log2 (t),а по оси OX – размерности n. Выбор логарифмической шкалы относительностепеней 2 объясняется тем фактом, что точного алгоритма, решающего задачуо построении наибольшего независимого множества и имеющего полиномиальную оценку сложности, не существует, а определение теоретической сложностиалгоритмов сводится к вычисления показателя α степенной функцииf (n) = 2αn .
Теоретической оценке сложности полного перебора соответствуеткривая f (n) = 2n , а алгоритму Робсона – f (n) = 2(0.276n) .Как видно из Рисунка 30 порядок роста алгоритма MaxISприp = 50% выше, чем у алгоритма Робсона, но при этом очень близок к функцииf (n) = 20.276n .Но уже при значении плотности p = 70% степень роста алгоритма MaxISснижается, и становится меньше, чем 2 0.276n (Рисунок 31).
Уверенно снижая80Рис. 30: Зависимость времени работы алгоритмов Робcона и MaxIS от размерности графовпри фиксированной плотности p = 50%.порядок временного роста при увеличении плотности графа, алгоритм MaxISпрактически сливается“ с алгоритмом Робсона при p = 85% (Рисунок 32). А”при значении p = 95% кривая, соответствующая алгоритму MaxIS, проходитнамного ниже кривой для алгоритма Робсона, при этом порядок роста этих двухалгоритмов совпадает, так как кривые идут параллельно друг другу (Рисунок 33).81Рис. 31: Зависимость времени работы алгоритмов Робcона и MaxIS от размерности графовпри фиксированной плотности p = 70%.Рис.
32: Зависимость времени работы алгоритмов Робcона и MaxIS от размерности графовпри фиксированной плотности p = 85%.82Рис. 33: Зависимость времени работы алгоритмов Робcона и MaxIS от размерности графовпри фиксированной плотности p = 95%.83ГЛАВА 4. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕАЛГОРИТМОВ MAXIS И ALLIS§1. Поиск максимальной общей подструктурыорганических соединенийПри исследовании органических соединений нередко приходится определять их общую химическую структуру, например, с целью поиска веществ, обладающих определенными свойствами. Каждому веществу можно поставитьв соответствие некоторый молекулярный граф – взвешенный граф, вершиныкоторого отвечают атомам, а ребра – связям между ними. Задачу поиска общейподструктуры молекул можно сформулировать как задачу определения общегоподграфа молекулярных графов, которая в свою очередь сводится к проблемепоиска клик в неориентированном графе [3].Рассмотрим два химических вещества: угольную кислоту (H2 CO3 ) и глицин(C2 H5 N O2 ).
На Рисунках 34, 35 даны их графические представления.б)а)Рис. 34: Масштабная модель (а) и структурная формула (б) угольной кислоты.Задача состоит в том, чтобы определить, содержит ли молекула глицинанекоторую исследуемую подструктуру молекулы угольной кислоты. На Рисунке 34 выделена часть химической структуры угольной кислоты, наличие84б)а)Рис. 35: Шаростержневая модель (а) и структурная формула (б) глицина.которой в глицине необходимо установить.
Для этого достаточно определить,содержит ли m-вершинный молекулярный граф глицина подграф, изоморфный n-вершинному (n ≤ m) молекулярному графу исследуемой подструктуры.Проблема изоморфного вхождения сводится к нахождению наибольшей кликивспомогательного графа с s вершинами (s ≤ n · m), точнее, к установлению,равна ли мощность этой клики n.Рассмотрим подробнее процесс моделирования молекулы угольной кислоты с использованием неориентированного взвешенного графа G1 .
Количествовершин V1 графа G1 соответствует общему количеству k атомов в молекуле.Вершины графа обозначаются kразличными натуральными числамиV1 = {1, 2, 3, 4, 5, 6}, в то время как в молекуле все атомы не обязательноразличные. С учетом этого факта каждой вершине графа G1 ставится в соответствие некоторое «свойство», в данном случае, это «вид атома». Все свойствавершинмоделируемогографахранятсявспециальноммножествеP1 = {H, O, C, O, H, O}.
Множество ребер E1 = {(1, 2), (2, 3), (3, 4), (4, 5), (3, 6)}.Для каждого ребра в графе G1 так же соответствует одно из двух свойств,хранимых во множестве R1 = {I, I, I, I, II}, где свойство ребра «I» соответст-85вует одинарной связи между атомами в молекуле угольной кислоты, а «II» —двойной. Исследуемой подструктуре , наличие которой необходимо установить вглицине, соответствует подграф G′1 ⊂ G1 : G′1 = (V1′ , E1′ ), где множество вершинV1′ = {3, 4, 5, 6}, со свойствами вершин P1′ = {C, O, H, O}, множество реберE1′ = {(3, 4), (4, 5), (3, 6)} со свойствами ребер R1′ = {I, I, II}.Сформируем подобные множества для графа G2 :– множество вершин графа V2 = {7, 8, 9, 10, 11, 12, 13, 14, 15, 16};– свойства вершин P2 = {H, C, H, N, C, O, O, H, H, H};– множество ребер:E2 = {(7, 8), (8, 9), (8, 10), (10, 15), (10, 16), (8, 11), (11, 12), (11, 13), (13, 14)};– свойства ребер R2 = {I, I, I, I, I, I, II, I, I}.На Рисунке 36 изображены модели изучаемых веществ в виде молекулярныхграфов.
Все вершины графов G1 и G2 , обладающие свойством «H», изображеныв виде квадратика, свойством «O»– кружочка, свойством «C» – треугольничка,свойством «N» – ромбика.а)б)Рис. 36: Молекулярные графы для угольной кислоты (а) и глицина (б).Далее из двух молекулярных графов G′1 и G2 необходимо составить вспомогательный граф A = (U, Z), представляющий собой несколько видоизменнуюконструкцию Визинга [3]. Каждая вершина такого графа соответствует некоторой паре вершин, сформированной из одной вершины графа G′1 и одной86вершины графа G2 , обладающих одним и тем же свойством. Например, вершина3 графа G′1 и вершина 8 графа G2 обладают свойством «C», следовательно,пара вершин (3,8) является вершиной u1 = (3, 8) вспомогательного графа A.
Всвою очередь пара (3,9) не образует вершину графа A, так как вершины 3 и 9обладают разными свойствами. В Таблице 6 указаны все пары вершин графовG′1 и G2 , образующие множество U = {u1 , u2 , ..., u11 } вершин вспомогательногографа. В итоге имеем 11-вершинный граф (Рисунок 37). Для того чтобы указатьребра этого графа необходимо исследовать все возможные пары его вершин.Всего таких пар будет τ ∗ (τ − 1)/2, где τ — количество вершин в графе.Для графа A нужно исследовать 55 пар вершин. Не будем давать подробногоанализа всех 55 сочетаний, приведем пример построения только некоторыхребер вспомогательного графа.Таблица 6.HHHV2HHHHHHV1′HH7389u16u51213u3u414 15 16u24510 11u6u7 u8 u9u10 u11Рассмотрим следующую пару вершин: u1 = (3, 8) и u8 = (5, 15). Вершиныu1 и u8 являются смежными в графе A, так как обе пары вершин (3, 5) и (8, 15)не образуют ребер в графе G′1 и G2 соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
