Диссертация (Алгоритмы поиска максимальных независимых множеств графа и экспериментальная оценка их эффективности)

САНКТ–ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиФИРЮЛИНА Оксана СергеевнаУДК 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].