Диссертация (1149246), страница 2
Текст из файла (страница 2)
На тестируемом наборе матриц принизком значении плотности ребер алгоритм AllIS показал лучшие результаты,чем алгоритм Брона-Кербоша.В качестве оппонента для алгоритма MaxIS был выбран алгоритм Робсона.Выбор именно этого алгоритма объясняется тем, что1) он один из немногих среди большого количества существующих в настоящее время точных алгоритмов имеет теоретическую оценку сложности;2) согласно этой оценке O(2 0.276n ) алгоритм Робсона является одним изнаиболее эффективных для решения задачи о поиске наибольшего независимогомножества.Тестирование работы алгоритмов MaxIS и Робсона также проводилось наодинаковом наборе графов с различными значениями плотности ребер.
Экспериментальные результаты показали, что при высоком значении плотности обаалгоритма имеют одинаковый порядок роста времени работы, не превыщающийO(2 0.276n ).Принимая во внимание результаты исследования, проведенного в рамкахдиссертационной работы, можно заключить, что разработанные алгоритмы могут быть использованы для решения многочисленных задач из разных облас-8тей науки и техники, которые допускают сведение к задаче поиска клик (илимаксимальных независимых множеств) в специальном образом сформированной математической модели в виде неориентированного графа. С целью продемонстрировать практическое применение алгоритмов AllIS и MaxIS былирешены некоторые задачи из биоинформатики, а именно, задача поиска общейподструктуры органических веществ и определения потенциальных вторичных структур РНК. Результаты экспериментального исследования поведенияалгоритмов при различных значениях плотности ребер также могут быть использованы для проведения дальнейшего анализа разработанных алгоритмов сцелью сокращения дерева поиска и уменьшения порядка роста времени работыалгоритмов в зависимости от размеров обрабатываемых графов.Основные результаты, выносимые на защиту.1.
Алгоритм (AllIS ) построения всех максимальных независимых множеств и алгоритм (MaxIS ) поиска наибольшего независимого множества в произвольном неориентированном графе.2. Теоретическое обоснование корректности работы алгоритмов AllIS иMaxIS (теоремы 1-5).3. Модификация алгоритма Робсона для нахождения наибольшего независимого множества.4. Результаты вычислительных экспериментов, позволившие выявить особенности поведения разработанных алгоритмов на графах с различными значениями плотности ребер, а также результаты сравнения времени работы сдругими известными алгоритмами.5. Комплекс проблемно-ориентированных программ, предназначенный длярешения задачи о поиске максимальных независимых множеств.Основные результаты диссертационного исследования были представленына 40-й международной научной конференции аспирантов и студентов Процес”сы управления и устойчивость“ (Санкт-Петербург, 2009 г.), 41-й международнойнаучной конференции аспирантов и студентов Процессы управления и устой”9чивость“ (Санкт-Петербург, 2010 г.), всероссийской конференции, посвященной80-летию со дня рождения В.
И. Зубова Устойчивость и процессы управления“”(Санкт-Петербург, 2010 г.), 43-й международной научной конференции аспирантов и студентов Процессы управления и устойчивость“ (Санкт-Петербург,”2012 г.), XIII всероссийском симпозиуме по прикладной и промышленной математики (Петрозаводск, 2012 г.), 44-й международной научной конференцииаспирантов и студентов Процессы управления и устойчивость“ (Санкт-Петер”бург, 2013 г.).По теме диссертации опубликовано 8 работ ([13], [14], [15], [19], [20], [21], [22],[23]), в том числе две статьи [15], [23] в журнале, входящем в перечень изданий,рекомендованных ВАК РФ.Рассмотрим структуру диссертационной работы. В первой главе приведенапостановка задачи поиска максимальных независимых множеств неориентированного графа, а также обзор существующих методов ее решения. Кроме этогов заключительном параграфе главы представлена модификация известного алгоритма Робсона, которая была предложена автором, для формирования элементов наибольшего независимого множества, а не только мощности этого множества, как это было сделано в оригинальной работе Робсона.Вторая глава диссертации посвящена разработке нового алгоритма поискавсех максимальных независимых множеств – алгоритма AllIS.
В первом параграфе даны определения и базовые конструкции разработанного алгоритма.Обсуждение основных моментов его работы, а также псевдокод алгоритма,приведены во втором параграфе. В третьем параграфе доказываются теоремы,обеспечивающие теоретическое обоснование корректности работы алгоритма.Подробный пример использования алгоритма AllIS для решения задачи о поиске всех МНМ графа представлен в четвертом параграфе. Заключительныйпараграф главы посвящен тестированию программной реализации разработанного алгоритма. Приведены результаты сравнения работы алгоритма AllIS cизвестным алгоритмом Брона-Кербоша, а также методом полного перебора.10В третьей главе предложен новый алгоритм решения задачи о поиске наибольшего независимого множества в произвольном неориентированном графе –алгоритм MaxIS, псевдокод которого приведен в первом параграфе.
АлгоритмMaxIS является модификацией алгоритма AllIS, рассмотренного в предыдущейглаве. Обсуждение изменений, проведенных в алгоритме AllIS, а также доказательства теорем, обеспечивающих правомерность этих изменений, приведеныво втором параграфе. В третьем параграфе поиск наибольшего независимогомножества с использованием алгоритма MaxIS проиллюстрирован на примереобработки неориентированного десятивершинного графа. Как и в предыдущейглаве, заключительный параграф третьей главы посвящен тестированию программной реализации разработанного алгоритма.
Представлены результаты сравнения работы алгоритма MaxIS c алгоритмом Робсона, а также методом полногоперебора, несколько модифицированным для нахождения одного наибольшегонезависимого множества.Практическое применение разработанных алгоритмов продемонстрированов четвертой главе на примере решения некоторых задач из биоинформатики. В первом параграфе рассматривается задача поиска максимальной общейподструктуры органических соединений.
Строится модель угольной кислоты иглицина в виде молекулярных графов, для которых ищется подграф, изоморфный исследуемым графам. Проблема изоморфного вхождения сводится к задачепоиска наибольшей клики вспомогательного графа, для решения которой используется алгоритм MaxIS. Второй параграф посвящен проблеме определенияпотенциальных вторичных структур РНК, моделирование которых проводитсяс использованием неориентированного графа. В полученном графе с помощьюпрограммной реализации алгоритма AllIS организуется поиск всех клик, которые и соответствуют искомым структурам.В заключении диссертации представлены основные результаты, полученныев ходе исследования.11ГЛАВА 1.
ЗАДАЧА О ПОИСКЕ МАКСИМАЛЬНЫХНЕЗАВИСИМЫХ МНОЖЕСТВ§1. Основные определенияПрежде чем ввести основные определения, укажем список употребляемыхпонятий и обозначений общего характера. Определения и обозначения взятыиз [3], [9], [33].x ∈ A – элемент x принадлежит множеству A;x∈/ A – элемент x не принадлежит множеству A;A ⊆ B – множество A является подмножеством множества B;A ⊂ B – строгое подмножество (A ⊆ B и A ̸= B);∅ – пустое множество;|A| – количество элементов (мощность) множества A;A ∪ B – объединение множеств A и B;A ∩ B – пересечение множеств A и B;A \ B – разность множеств A и B (не обязательно B ⊆ A);S & R – S и R , конъюнкция высказываний S, R;B [2] = {(x, y) | x, y ∈ B & x ̸= y} – множество неупорядоченных пар различных элементов A.Далее в работе будем рассматривать исключительно числовые множества,элементами которых являются натуральные числа, поэтому для них можноввести операции (<, >, =) сравнения элементов. Неупорядоченные пары чиселдля удобства условимся записывать в виде (x, y), где x < y, но понимая, чтопорядок следования элементов в них не играет ни какой роли.Неориентированным графом (или просто графом) G = (V, E) называетсяупорядоченная пара множеств: конечного непустого V , элементы которого называются вершинами графа G, и подмножества E ⊆ V [2] , представляющегособой множество неупорядоченных пар различных вершин, элементы которогоназываются ребрами этого графа.12Отметим два крайних случая n-вершинных графов: безреберный графHn = (U, ∅) и полный граф Fn = (U, U [2] ), n = |U |.Граф G = (V, E), дополнительный к графу G = (V, E), имеет то же самоемножество вершин, а множество его ребер E = V [2] \ E состоит из всех технеупорядоченных пар различных вершин, которые не являются ребрами исходного графа G.Если в неориентированном графе между двумя вершинами x и y есть ребро,тогда эти вершины смежны, в противном случае – несмежны.
Ребро, соединяющее вершины x и y, инцидентно каждой из них (и наоборот, они обе инцидентныданному ребру).Степенью s(G, x) вершины x в графе G = (V, E) называется количество еговершин, смежных с x, или, что то же, число ребер, инцидентных этой вершине.Вершины x, для которых s(G, x) = 0, называются изолированными, а вершиныx со степенью s(G, x) = 1 – висячими.Граф G′ = (V ′ , E ′ ) называется подграфом графа G = (V, E), если V ′ ⊆ Vи E ′ = {(x, y) ∈ E | x, y ∈ V ′ }.
Иными словами, при образовании подграфаG′ из графа G удаляются все вершины множества Y = V \ V ′ и только теребра, которые инцидентны хотя бы одной удаляемой вершине. Поэтому длякраткости будем записывать G′ = G \ Y. Множество вершин V ′ ⊂ V таких, чтоG′ = (V ′ , E ′ ) является подграфом графа G = (V, E), будем называть индуцирующим множеством.Множество попарно смежных вершин графа G называется кликой (иногдакликой называют не столько множество вершин, сколько сам полный граф).Клика называется максимальной, если она не содержится ни в какой другойклике графа G. Клику наибольшей мощности будем называть наибольшей кликой, число вершин в которой есть плотность φ(G) графа G.Множество вершин графа G, индуцирующее его безреберный подграф, называется независимым. Будем называть такое множество максимальным независимым, если к этому множеству нельзя добавить никакую другую вершину13из графа G с сохранением независимости.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
