Диссертация (1149246)
Текст из файла
САНКТ–ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиФИРЮЛИНА Оксана СергеевнаУДК 519.157, 519.161, 519.163АЛГОРИТМЫ ПОИСКА МАКСИМАЛЬНЫХНЕЗАВИСИМЫХ МНОЖЕСТВ ГРАФА ИЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА ИХЭФФЕКТИВНОСТИ05.13.18 – Математическое моделирование, численные методы и комплексыпрограммДИССЕРТАЦИЯна соискание ученой степени кандидатафизико - математических наукСАНКТ–ПЕТЕРБУРГ2014ОГЛАВЛЕНИЕВВЕДЕНИЕ .................................................................................................4ГЛАВА 1. ЗАДАЧА О ПОИСКЕ МАКСИМАЛЬНЫХ НЕЗАВИСИМЫХ МНОЖЕСТВ§1. Основные определения .............................................................................11§2.
Постановка задачи о поиске максимальных независимых множеств ........14§3. Алгоритмы поиска максимальных независимых множеств в неориентированном графе ......................................................................................................16п. 1. Метод полного перебора и метод поиска с возвращением (алгоритмБрона-Кербоша) .................................................................................................20п.
2. Алгоритм Робсона и его модификация ..............................................23ГЛАВА 2. АЛГОРИТМ ALLIS ПОСТРОЕНИЯ ВСЕХ МАКСИМАЛЬНЫХ НЕЗАВИСИМЫХ МНОЖЕСТВ НЕОРИЕНТИРОВАННОГО ГРАФА§1. Основные определения ............................................................................30§2. Алгоритм AllIS построения всех максимальных независимых множествграфа ................................................................................................................. 32§3. Теоретическое обоснование алгоритма AllIS ...........................................35§4. Пример построения максимальных независимых множеств ...................49§5. Тестирование программной реализации ..................................................55ГЛАВА 3. АЛГОРИТМ MAXIS ПОИСКА НАИБОЛЬШЕГО НЕЗАВИСИМОГО МНОЖЕСТВА§1.
Модификация алгоритма AllIS для решения задачи о наибольшем независимом множестве ...........................................................................................62§2. Теоретическое обоснование алгоритма MaxIS ........................................64§3. Пример построения наибольшего независимого множества ...................693§4. Тестирование программной реализации .................................................77ГЛАВА 4.
ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ АЛГОРИТМОВMAXIS И ALLIS§1. Поиск максимальной общей подструктуры органических соединений....83§2. Построение потенциальных вторичных структур РНК ..........................88ЗАКЛЮЧЕНИЕ.......................................................................................92СПИСОК ЛИТЕРАТУРЫ.....................................................................94ПРИЛОЖЕНИЕ 1. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДАПОЛНОГО ПЕРЕБОРА ДЛЯ ПОИСКА НАИБОЛЬШЕГО НЕЗАВИСИМОГО МНОЖЕСТВА...................................................................102ПРИЛОЖЕНИЕ 2.
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДАПОЛНОГО ПЕРЕБОРА ДЛЯ ПОСТРОЕНИЯ ВСЕХ МАКСИМАЛЬНЫХ НЕЗАВИСИМЫХ МНОЖЕСТВ.................................................105ПРИЛОЖЕНИЕ 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА БРОНА-КЕРБОША...........................................................................108ПРИЛОЖЕНИЕ 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА РОБСОНА.............................................................................................110ПРИЛОЖЕНИЕ 5. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ALLIS......................................................................................................135ПРИЛОЖЕНИЕ 6. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА MAXIS....................................................................................................1424ВВЕДЕНИЕРоль теории графов в математическом моделировании трудно переоценить.Модели на графах применяются в самых различных областях науки и техники:от социологии до компьютерных технологий.
Это объясняется тем, что такиемодели обладают высокой степенью наглядности и потому понятны и удобны виспользовании.Теория графов как один из важнейших разделов дискретной математикиначала развиваться с 1930-х г [16]. Развитие вычислительной техники позволилообрабатывать графы больших размерностей. Но, несмотря на это, в теории графов до сих пор остаются задачи, которые имеют репутацию «трудно вычислимых», даже с использованием самых современных компьютерных технологий.Речь идет о так называемых N P -полных задачах.
К таким задачам относят те,для которых в настоящее время не существует точных алгоритмов решения сполиномиальной оценкой сложности. Доказано существование несколько сотенN P -полных задач [2], но, к сожалению, ни одна из них пока не может бытьрешена за полиномиальное время. Создание полиномиального точного алгоритма хотя бы одной из них привело бы к разработке эффективных алгоритмов для всех остальных задач данного класса. Это означало бы решениеодной из основных проблем теории сложности, проблемы несовпадения сложностных классов P ̸= N P [6].
Эту проблему можно сформулировать следуюшим образом: можно ли все задачи, решение которых проверяется с полиномиальной сложностью решить за полиномиальное время? В настоящее времянет теоретических доказательств как возможности, так и невозможности существования подобных алгоритмов решения. Проблема P ̸= N P неоднократноподнималась в работах разных авторов [7], [32], [37], [38]. Согласно проведенному исследованию публикаций последних лет (2001–2010 гг.): [31], [34], [35],[36], [47], [55], [61], [70], [71], проблема поиска эффективных точных алгоритмов решения N P -полных задач не прекращает привлекать к себе внимание5исследователей всего мира и продолжает оставаться актуальной и в настоящеевремя.В диссертационной работе рассматривается решение одной из важнейшихN P -полной задачи дискретной математики, а именно, поиск максимальныхнезависимых множеств (МНМ) неориентированного графа.
Алгоритмы решенияэтой задачи используются в широких спектрах прикладных проблем, в томчисле в социометрии [40], химии [29], [59], [72], компьютерных технологиях[43], [58], [64], [65] и биоинформатике [17], [26], [30], [42], [62], [67], [68]. Этообъясняется тем, что специальным образом представив объект исследования ввиде модели на графе, множество задач из выше указанных областей наукиможно свести к задаче поиска клики в неориентированном графе, что в своюочередь легко трансформируется в задачу нахождения максимальных независимых множеств графа.Начиная с 50-х годов прошлого века было предложено много точных алгоритмов для решения задач, связанных с поиском максимальных независимых множеств, например, [27], [36], [40], [60], [66], но построить эффективныйалгоритм, имеющий полиномиальную оценку сложности, никому до сих пор неудалось.
Если для задачи о перечислении всех клик графа разработка такого алгоритма представляется мало вероятной (в силу экспоненциальной зависимостиколичества клик от размерности графа [52]), то для поиска одного наибольшего независимого множества невозможность построения подобного алгоритмаостается недоказанной в силу нерешенной проблемы P ̸= N P .
Это вдохновляетисследователей всего мира на создание всё новых и новых точных алгоритмоврешения задачи о наибольшей клике, в надежде на создание полиномиального алгоритма. Исходя из того, что все эти алгоритмы имеют экспоненциальную оценку сложности O(2 αn ), разработчики стараются модифицировать своиалгоритмы с целью сокращения дерева поиска, что в свою очередь приводит куменьшению показателя α.6Целью диссертационной работы является разработка эффективных алгоритмов поиска МНМ неориентированного графа.
Для достижения цели былипоставлены следующие задачи:1. Исследование проблемы поиска МНМ графа, а также существующихметодов ее решения.2. Разработка и формализация алгоритмов поиска МНМ графа, основанных на идеи расширения независимого множества на каждом уровне деревапоиска парой вершин.3. Разработка комплекса проблемно-ориентированных программ, предназначенного для решения задачи поиска МНМ графа.4. Проведение серии вычислительных экспериментов с целью сравнениякачества работы предложенных алгоритмов с другими методами поиска МНМ.5. Исследование области применения разработанных алгоритмов.В работе используются аппарат теории графов, методы комбинаторногоанализа, методы разработки эффективных алгоритмов и анализа их временно́йсложности.Достоверность научных результатов обеспечивается строгостью доказательств, согласованностью с уже имеющимися результатами в данной и смежных областях.В ходе диссертационного исследования были разработаны новые алгоритмы решения задачи о поиске МНМ графа: алгоритм AllIS для построениявсех максимальных независимых множеств и алгоритм MaxIS для поиска наибольшего независимого множества.
Эти алгоритмы для расширения МНМ накаждом уровне дерева поиска используют пару вершин, что позволяет сократить глубину этого дерева по сравнению с аналогичными алгоритмами, расширяющими МНМ одной вершиной на каждом шаге. Введенное в алгоритме AllISпонятие окрестности узла дерева поиска, а также критерии перспективностидальнейшего продвижения по ветви дерева поиска, порожденной этим узлом,дают возможность проводить отсечение потенциальных ветвей, не дающих воз-7можность сформировать МНМ, отличное от уже построенных.
Таким образом,каждая ветвь дерева поиска, порожденного алгоритмами AllIS и MaxIS, соответствует уникальному МНМ, что позволяет поставить эти алгоритмы в одинряд с такими методами, которые также не допускают повторной генерации ужесформированных МНМ. Формирование МНМ из множества несмежных парграфа позволяет уменьшить время работы алгоритмов для сильно разреженныхграфов, а также графов с высоким значением плотности ребер, по сравнению сдругими алгоритмами, решающими аналогичную задачу.При тестировании алгоритм AllIS сравнивался с известным алгоритмомБрона-Керрбоша для перечисления всех максимальных независимых множествв неориентированном графе, который до сих пор является одним из наиболееэффективных для решения этой задачи [42].
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
