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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиФИРЮЛИНА Оксана СергеевнаАЛГОРИТМЫ ПОИСКА МАКСИМАЛЬНЫХНЕЗАВИСИМЫХ МНОЖЕСТВ ГРАФА ИЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА ИХЭФФЕКТИВНОСТИ05.13.18 — математическое моделирование, численные методы и комплексыпрограммАВТОРЕФЕРАТдиссертации на соискание ученой степеникандидата физико-математических наукСанкт-Петербург — 2014Работа выполнена на кафедре информационных систем факультетаприкладнойматематики – процессовуправленияСанкт-Петербургскогогосударственного университетаНаучный руководитель:доктор физико-математических наук, доцентОлемской Игорь ВладимировичОфициальные оппоненты:доктор технических наук, старший научныйсотрудник Новиков Федор Александрович(Санкт-Петербургский государственныйполитехнический университет, профессор)кандидат физико-математических наук, старшийнаучный сотрудник Васильев Николай Николаевич(Санкт-Петербургское отделение Математическогоинститута им.

В.А.Стеклова РАН, старшийнаучный сотрудник)Ведущая организация:Институт прикладных математическихисследований Карельского научного центра РАНЗащита состоится « 25 » июня 2014 г. в 15 ч. 00 мин. на заседаниидиссертационного совета Д.212.232.50 по защите диссертаций на соисканиеученой степени кандидата наук, на соискание ученой степени доктора наукприСанкт-Петербургскомгосударственномуниверситетепоадресу:198504, Санкт-Петербург, Петродворец, Университетский пр., д.35, ауд. 327.Отзывы на автореферат в 2-х экземплярах просим направлять по адресу:198504, Санкт-Петербург, Петродворец, Университетский пр., д.35, ученомусекретарю диссертационного совета Д 212.232.50 Г.И.

Курбатовой.С диссертацией можно ознакомиться в научной библиотеке им. М. ГорькогоСанкт-Петербургского государственного университета по адресу: 199034, г. СанктПетербург, Университетская наб., 7/9. Автореферат и диссертация размещены насайте www.spbu.ru.Автореферат разослан «___» ___________ 2014 г.Ученый секретарьдиссертационного совета,доктор физ.-мат. наук, профессорГ. И. КурбатоваОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫАктуальность темы. Роль теории графов в математическом моделировании трудно переоценить. Модели на графах применяются в самых различных областях науки и техники: от социологии до компьютерных технологий.Это объясняется тем, что такие модели обладают высокой степенью наглядности и потому понятны и удобны в использовании.Теория графов как один из важнейших разделов дискретной математикиначала развиваться с 1930-х г.

Развитие вычислительной техники позволилообрабатывать графы больших размерностей. Но, несмотря на это, в теорииграфов до сих пор остаются задачи, которые имеют репутацию «трудно вычислимых», даже с использованием самых современных компьютерных технологий. Речь идет о так называемых N P -полных задачах. К таким задачамотносят те, для которых в настоящее время не существует точных алгоритмоврешения с полиномиальной оценкой сложности.

Доказано существование нескольких сотен N P -полных задач, но, к сожалению, ни одна из них пока неможет быть решена за полиномиальное время. Создание полиномиальноготочного алгоритма хотя бы одной из них привело бы к разработке эффективных алгоритмов для всех остальных задач данного класса. Это означало бырешение одной из основных проблем теории сложности – проблемы несовпадения сложностных классов P ̸= N P .

Эту проблему можно сформулироватьследуюшим образом: можно ли все задачи, решение которых проверяется сполиномиальной сложностью решить за полиномиальное время? В настоящеевремя нет теоретических доказательств как возможности, так и невозможности существования подобных алгоритмов решения. Проблема P ̸= N Pнеоднократно поднималась в работах разных авторов (например, C. Cook,Л. A. Левин, W. I. Gasarch, L. Fortnow).

Согласно проведенному исследованиюнедавних публикаций 2001–2010 гг. (J. M. Robson, I. Koch, P. R. J. Ostergard,F. V. Fomin, E. Tomita) проблема поиска эффективных точных алгоритмов3решения N P -полных задач не прекращает привлекать к себе внимание исследователей всего мира и продолжает оставаться актуальной и в настоящеевремя.В диссертационной работе рассматривается решение одной из важнейшихN P -полной задачи дискретной математики, а именно, поиск максимальныхнезависимых множеств (МНМ) неориентированного графа.

Алгоритмы решения этой задачи используются в широких спектрах прикладных проблем,в том числе в социометрии, химии, компьютерных технологиях и биоинформатике. Это объясняется тем, что специальным образом представив объектисследования в виде модели на графе, множество задач из вышеуказанныхобластей науки можно свести к задаче поиска клики в неориентированномграфе, что в свою очередь легко трансформируется в задачу нахожденияМНМ графа.Начиная с 50-х годов прошлого века было предложено много алгоритмоврешения задач, связанных с поиском МНМ (например, в работах F.

Harary,C. Bron и J. Kerbosch, R. E. Tarjan, J. M. Robson, F. V. Fomin), но построитьэффективный алгоритм, имеющий полиномиальную оценку сложности, никому до сих пор не удалось. Если для задачи о перечислении всех клик неориентированного графа разработка такого алгоритма представляется маловероятной (в силу экспоненциальной зависимости количества клик от размерности графа), то для поиска одного наибольшего независимого множества невозможность построения подобного алгоритма остается недоказанной всилу нерешенной проблемы P ̸= N P . Это вдохновляет исследователей всего мира на создание всё новых и новых точных алгоритмов решения задачио наибольшей клике, в надежде на создание полиномиального алгоритма.Исходя из того, что все эти алгоритмы имеют экспоненциальную оценкусложности O(2αn ), разработчики стараются модифицировать свои алгоритмыс целью сокращения дерева поиска, что в свою очередь приводит к уменьшению показателя α.4Целью диссертационной работы является разработка эффективныхалгоритмов поиска МНМ неориентированного графа.

Для достижения целибыли поставлены следующие задачи:1. Исследование проблемы поиска МНМ графа, а также существующихметодов ее решения.2. Разработка и формализация алгоритмов поиска МНМ графа, основанных на идеи расширения независимого множества на каждом уровне деревапоиска парой вершин.3. Разработка комплекса проблемно-ориентированных программ, предназначенного для решения задачи поиска МНМ графа.4. Проведение серии вычислительных экспериментов с целью сравнениякачества работы предложенных алгоритмов с другими методами поиска МНМ.5. Исследование области применения разработанных алгоритмов.Методы исследования.

В диссертационной работе используются аппарат теории графов, методы комбинаторного анализа, методы разработкиэффективных алгоритмов и анализа их временно́й сложности.Достоверность научных результатов обеспечивается строгостью доказательств, согласованностью с уже имеющимися результатами в данной исмежных областях.Научная новизна. В ходе диссертационного исследования были разработаны новые алгоритмы решения задачи о поиске МНМ графа: алгоритмAllIS для построения всех максимальных независимых множеств и алгоритмMaxIS для поиска наибольшего независимого множества.

Эти алгоритмыдля расширения МНМ на каждом уровне дерева поиска используют парувершин, что позволяет сократить глубину этого дерева по сравнению с аналогичными алгоритмами, расширяющими МНМ одной вершиной на каждомшаге. Введенное в алгоритме AllIS понятие окрестности узла дерева поиска, атакже критерии перспективности дальнейшего продвижения по ветви деревапоиска, порожденной этим узлом, дают возможность проводить отсечение5потенциальных ветвей, не дающих возможность сформировать МНМ, отличное от уже построенных. Таким образом, каждая ветвь дерева поиска,порожденного алгоритмами AllIS и MaxIS, соответствует уникальному МНМ,что позволяет поставить эти алгоритмы в один ряд с такими методами, которые также не допускают повторной генерации уже сформированных МНМ.Формирование МНМ из множества несмежных пар графа позволяет уменьшить время работы алгоритмов для сильно разреженных графов, а такжеграфов с высоким значением плотности ребер, по сравнению с другими алгоритмами, решающими аналогичную задачу.Теоретическая и практическая значимость.

Принимая во вниманиерезультаты исследования, проведенного в рамках диссертацинной работы,можно заключить, что разработанные алгоритмы могут быть использованыдля решения многочисленных задач из разных областей науки и техники,которые допускают сведение к задаче поиска клик (или максимальных независимых множеств) в специальном образом сформированной математической модели в виде неориентированного графа. С целью продемонстироватьпрактическое применение алгоритмов AllIS и MaxIS были решены некоторыезадачи из биоинформатики, а именно, задача поиска общей подструктурыорганических веществ и определения потенциальных вторичных структурРНК.

Результаты экспериментального исследования поведения алгоритмовпри различных значениях плотности ребер графа также могут быть использованы для проведения дальнейшего анализа разработанных алгоритмов сцелью сокращения дерева поиска и уменьшения порядка роста времени работы алгоритмов в зависимости от размеров обрабатываемых графов.Основные результаты, выносимые на защиту.1. Алгоритм (AllIS ) построения всех максимальных независимых множеств и алгоритм (MaxIS ) поиска наибольшего независимого множества впроизвольном неориентированном графе.62. Теоретическое обоснование корректности работы алгоритмов AllIS иMaxIS (теоремы 1-5).3.

Модификация алгоритма Робсона для нахождения наибольшего независимого множества.4. Результаты вычислительных экспериментов, позволившие выявить особенности поведения разработанных алгоритмов на графах с различными значениями плотности ребер, а также результаты сравнения времени работы сдругими известными алгоритмами.5. Комплекс проблемно-ориентированных программ, предназначенный длярешения задачи о поиске максимальных независимых множеств.Апробация результатов диссертации. Основные результаты диссертационного исследования были представлены на международной научной конференции аспирантов и студентов «Процессы управления и устойчивость»(Санкт-Петербург, 2009 г., 2010 г., 2012 г.