автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Алгоритмы поиска максимальных независимых множеств графа и экспериментальная оценка их эффективности

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи /)

ФИРЮЛИНА Оксана Сергеевна

АЛГОРИТМЫ ПОИСКА МАКСИМАЛЬНЫХ НЕЗАВИСИМЫХ МНОЖЕСТВ ГРАФА И ЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА ИХ ЭФФЕКТИВНОСТИ

05.13.18 — математическое моделирование, численные методы и комплексы

программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

I ' МАЙ лш

Санкт-Петербург — 2014

005549365

005549365

Работа выполнена на кафедре информационных систем факультета прикладной математики — процессов управления Санкт-Петербургского государственного университета

Научный руководитель: доктор физико-математических наук, доцент

Олемской Игорь Владимирович

Официальные оппоненты: доктор технических наук, старший научный

сотрудник Новиков Федор Александрович (Санкт-Петербургский государственный политехнический университет, профессор)

кандидат физико-математических наук, старший научный сотрудник Васильев Николай Николаевич (Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН, старший научный сотрудник)

Ведущая организация: Институт прикладных математических

исследований Карельского научного центра РАН

Защита состоится « 25 » июня 2014 г. в 15 ч. 00 мин. на заседании диссертационного совета Д.212.232.50 по защите диссертаций на соискание ученой степени кандидата наук, на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., д.35, ауд. 327.

Отзывы на автореферат в 2-х экземплярах просим направлять по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., д.35, ученому секретарю диссертационного совета Д 212.232.50 Г.И. Курбатовой.

С диссертацией можно ознакомиться в научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, г. Санкт-Петербург, Университетская наб., 7/9. Автореферат и диссертация размещены на сайге www.spbu.ru.

Автореферат разослан «¿О» с^-С 2014 г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук, профессор

Г. И. Курбатова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Роль теории графов в математическом моделировании трудно переоценить. Модели на, графах применяются в самых различных областях науки и техники: от социологии до компьютерных технологий. Это объясняется тем, что такие модели обладают высокой степенью наглядности и потому понятны и удобны в использовании.

Теория графов как один из важнейших разделов дискретной математики начала развиваться с 1930-х г. Развитие вычислительной техники позволило обрабатывать графы больших размерностей. Но, несмотря на это, в теории графов до сих пор остаются задачи, которые имеют репутацию «трудно вычислимых», даже с использованием самых современных компьютерных технологий. Речь идет о так называемых iVP-полных задачах. К таким задачам относят те, для которых в настоящее время не существует точных алгоритмов решения с полиномиальной оценкой сложности. Доказано существование нескольких сотен iVP-полных задач, но, к сожалению, ни одна из них пока не может быть решена за полиномиальное время. Создание полиномиального точного алгоритма хотя бы одной из них привело бы к разработке эффективных алгоритмов для всех остальных задач данного класса^ Это означало бы решение одной из основных проблем теории сложности - проблемы несовпадения сложностных классов Р ф NP. Эту проблему можно сформулировать следующим образом: можно ли все задачи, решение которых проверяется с полиномиальной сложностью решить за полиномиальное время? В настоящее время нет теоретических доказательств как возможности, так и невозможности существования подобных алгоритмов решения." Проблема Р ф NP неоднократно поднималась в работах разных авторов (например, С. Cook, JI. А. Левин, W. I. Gasarch, L. Fortnow). Согласно проведенному исследованию недавних публикаций 2001-2010 гг. (J. М. Robson, I. Koch, Р. R. J. Ostergard, F. V. Fomin, E. Tomita) проблема поиска эффективных точных алгоритмов

решения iVP-полных задач не прекращает привлекать к себе внимание исследователей всего мира и продолжает оставаться актуальной и в настоящее время.

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

Начиная с 50-х годов прошлого века было предложено много алгоритмов решения задач, связанных с поиском МНМ (например, в работах F. Нагагу, С. Вгоп и J. Kerbosch, R. Е. Tarjan, J. М. Robson, F. V. Fomin), но построить эффективный алгоритм, имеющий полиномиальную оценку сложности, никому до сих пор не удалось. Если для задачи о перечислении всех клик неориентированного графа разработка такого алгоритма представляется мало вероятной (в силу экспоненциальной зависимости количества клик от размерности графа), то для поиска одного наибольшего независимого множества невозможность построения подобного алгоритма остается недоказанной в силу нерешенной проблемы Р ф NP. Это вдохновляет исследователей всего мира на создание всё новых и новых точных алгоритмов решения задачи о наибольшей клике, в надежде на создание полиномиального алгоритма. Исходя из того, что все эти алгоритмы имеют экспоненциальную оценку сложности 0(2ап), разработчики стараются модифицировать свои алгоритмы с целью сокращения дерева поиска, что в свою очередь приводит к уменьшению показателя а.

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

1. Исследование проблемы поиска МНМ графа, а также существующих методов ее решения.

2. Разработка и формализация алгоритмов поиска МНМ графа, основанных на идеи расширения независимого множества на каждом уровне дерева поиска парой вершин.

3. Разработка комплекса проблемно-ориентированных программ, предназначенного для решения задачи поиска МНМ графа.

4. Проведение серии вычислительных экспериментов с целью сравнения качества работы предложенных алгоритмов с другими методами поиска МНМ.

5. Исследование области применения разработанных алгоритмов.

Методы исследования. В диссертационной работе используются аппарат теории графов, методы комбинаторного анализа, методы разработки эффективных алгоритмов и анализа их временной сложности.

Достоверность научных результатов обеспечивается строгостью доказательств, согласованностью с уже имеющимися результатами в данной и смежных областях.

Научная новизна. В ходе диссертационного исследования были разработаны новые алгоритмы решения задачи о поиске МНМ графа: алгоритм АIIIБ для построения всех максимальных независимых множеств и алгоритм Мах1Б для поиска наибольшего независимого множества. Эти алгоритмы для расширения МНМ на каждом уровне дерева поиска используют пару вершин, что позволяет сократить глубину этого дерева по сравнению с аналогичными алгоритмами, расширяющими МНМ одной вершиной на каждом шаге. Введенное в алгоритме /\IIIS понятие окрестности узла дерева поиска, а также критерии перспективности дальнейшего продвижения по ветви дерева поиска, порожденной этим узлом, дают возможность проводить отсечение

потенциальных ветвей, не дающих возможность сформировать МНМ, отличное от уже построенных. Таким образом, каждая ветвь дерева поиска, порожденного алгоритмами АШБ и Мах1Я, соответствует уникальному МНМ, что позволяет поставить эти алгоритмы в один ряд с такими методами, которые также не допускают повторной генерации уже сформированных МНМ. Формирование МНМ из множества несмежных пар графа позволяет уменьшить время работы алгоритмов для сильно разреженных графов, а также графов с высоким значением плотности ребер, по сравнению с другими алгоритмами, решающими аналогичную задачу.

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

Основные результаты, выносимые на защиту.

1. Алгоритм (/Ш/5) построения всех максимальных независимых множеств и алгоритм (МахШ) поиска наибольшего независимого множества в произвольном неориентированном графе.

2. Теоретическое обоснование корректности работы алгоритмов АШБ и МахШ (теоремы 1-5).

3. Модификация алгоритма Робсона для нахождения наибольшего независимого множества.

4. Результаты вычислительных экспериментов, позволившие выявить особенности поведения разработанных алгоритмов на графах с различными значениями плотности ребер, а также результаты сравнения времени работы с другими известными алгоритмами.

5. Комплекс проблемно-ориентированных программ, предназначенный для решения задачи о поиске максимальных независимых множеств.

Апробация результатов диссертации. Основные результаты диссертационного исследования были представлены на международной научной конференции аспирантов и студентов «Процессы управления и устойчивость» (Санкт-Петербург, 2009 г., 2010 г., 2012 г. и 2013 г.), всероссийской конференции, посвященной 80-летию со дня рождения В. И. Зубова «Устойчивость и процессы управления» (Санкт-Петербург, 2010 г.), XIII всероссийском симпозиуме по прикладной и промышленной математике (Петрозаводск, 2012 г.).

Публикации. По теме диссертации опубликовано 8 работ, в том числе две статьи в журнале, входящем в перечень изданий, рекомендованных ВАК.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, приложения и списка литературы, включающего 72 наименования. Общий объем работы составляет 101 страницу, не включая объем приложения, равный 48 страницам.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы исследования, степень ее разработанности, научная новизна, теоретическая и практическая значимость результатов, выносимых на защиту, а также приведено краткое содержание диссертационной работы.

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

Вторая глава диссертации посвящена разработке нового алгоритма поиска всех МНМ графа - алгоритма АШБ. В первом параграфе даны основные определения и базовые конструкции разработанного алгоритма. Объектом исследования является неориентированный п-вершинный граф С? = (V, Е), заданный матрицей смежности А = :

Г 1, (г,;/) 6 Е, { 0, (г,3) £ Е.

Для использования алгоритма АШБ граф в представляется в виде С = [V, <5\/;л], где V = {1,2,..., п} — множество вершин графа, = {(р, д) | (р, (¡) € У'2' & арл — 0} — множество всех несмежных пар различных вершин графа С7. Любая пара несмежных вершин (/3,7) € называется узлом и обозначается а = (/3,7). Базовым множеством для некоторого узла а — (/?, 7) € 5у;л графа С7 назовем множество

Аг[а] = {сг е V | /3) е & Ц 7) 6 ЗД и {0, 7}.

Опорным множеством для этого же узла называется множество иа[а] = 1>сМ\{/*,7}-

Независимое множество вершин в графе С? обозначается ¿¿о, независимое множество, в котором содержатся две вершины /3 и 7 - <3с[а], множество всех вершин, имеющих ребро с каждой вершиной рассматриваемого графа -Дс[<*], множество всех МНМ графа - М((?).

Процесс построения МНМ графа можно представить в виде дерева поиска, в котором каждый k-Pi уровень отвечает рассмотрению некоторого подграфа

Gk с Gk-1 с ... с = G.

Подграф Gk+1 С Gk будем задавать в следующем виде:

Gk+1 = M,S[a% a^GSlat

Для компактной формализации алгоритма введем узел отрицательного уровня с вершинами, не имеющими ребра ни с одной вершиной графа G, и обозначим его а"1 = (Д^.ТГ1): ^ЬГ1] = S^cC1] = Sv,a-

Базовое множество D[ak+1] для узла ak+l = (/3k+l, 7fc+1) € 5[ajf] графа Gk+1 представим как

D[ak+1] = {de u[ak] | (d,pk+1) € 5[ai]&(dl7*+1) 6 S[a*]} U {Pk+l ,-yk+l}.

Опорное множество для узла ak+i = 6 S[ak] графа Gk+1

определяем по правилу

w[aj;+1] = £>[ai+1]\{^+1,7i+1}.

Множество S[a*+1] несмежных пар в графе, индуцированном множеством вершин w[a»+1] :

S[ak+l} = {(p,g) | (p,q) G u[ak+lfhaVtq = 0}.

Находим множество A[aJ+1] по правилу

дП = шГ]\иМй1„;+1|{м}.

Множество P[a,+1], сформированное согласно правилу

РН+1\ = {QWl} G Р[ак] | {Pkt+\lk,+l} С Q[ai]}, Pia:1} = 0,

будем называть окрестностью узла ak+1.

Обсуждение основных моментов работы алгоритма, а также его псевдокод, приведены во втором параграфе. В третьем параграфе доказываются теоремы, обеспечивающие теоретическое обоснование корректности работы алгоритма.

Теорема 1. Любое максимальное независимое множество QgM содержится в базовом множестве, соответствующем паре а — (/3,7):

Qa[a] С DG[a}.

Теорема 2. Пусть Qq[o\ ~ i-e МНМ графа G, содержащее вершины /3 и 7, т - количество всех таких множеств. Тогда

АзМ Xu^QbM = 0.

Согласно теореме 1 и теореме 2, для того чтобы построить максимальные независимые множества, содержащие в себе некоторую пару элементов а = (/3,7), необходимо использовать элементы базового множества для ука--, занной пары.

На основе следующей группы теорем (теорема 3 и теорема 4) формулируются критерии, по которым узлы рассматриваются как «неперспективные» для продолжения построения максимальных независимых множеств.

Теорема 3. Если Dq[o\ Q Dg[oi*], тогда для любого МНМ Qg[c] Я Dg[o\ найдется МНМ Qg\°<*] Я. Аз [а*] такое что Qg[c**] = <3gH (другими словами, любое МНМ, содержащее вершины /3 и 7, будет являться множеством, содержащим вершины /3* и j*).

Теорема 4. Если в некотором подграфе Gk С Gk~l С ... С G0 для выбранного узла aJ = (/8^,7*) найдется множество Q € :

Q \ {Pi 7,°, Pi 7*1 ■ ■ •, Pt~\7*"1} = D[a%

тогда независимое множество

J= {Pi 7°, Phi---, Pk-\ikr1} и i = q. 10

В процессе работы алгоритма на каждом к-м уровне дерева поиска происходит выбор пары вершин = {Риспользуемых в дальнейшем для расширения независимого множества 3. Выбранный узел а* должен удовлетворять двум условиям:

1) |£>[аг*]| - тахаке3[ак]\0[ак]\ (для того чтобы как можно больше пар вершин можно было исключить из дерева поиска после построения всех <2[а«]);

2) не должно существовать множества <2 из окрестности Р[о£], удовлетворяющего условию теоремы 4 (в противном случае, рассмотрение этого узла приводит к формированию максимального независимого множества, которое уже было построено ранее).

Подробный пример использования алгоритма АШБ для решения задачи о поиске всех МНМ приведен в четвертом параграфе. Заключительный параграф главы посвящен тестированию программной реализации разработанного алгоритма. Представлены результаты сравнения алгоритма АШБ с известным алгоритмом Брона-Кербоша, а также методом полного перебора. Согласно результатам исследования время работы алгоритмов АШБ и Брона-Кербоша существенно зависит от плотности ребер графа. На тестируемом наборе матриц при низком значении плотности ребер алгоритм АШБ показал лучшие результаты, чем алгоритм Брона-Кербоша (Рисунки 1, 2).

В третьей главе предложен новый алгоритм решения задачи о поиске наибольшего независимого множества в произвольном неориентированном графе - алгоритм Мах1Б, псевдокод которого приведен в первом параграфе. Алгоритм Мах1Б является модификацией алгоритма АШБ, рассмотренного в предыдущей главе. Обсуждение изменений, проведенных в алгоритме АШБ, а также доказательства теорем, обеспечивающих правомерность этих изменений, приведены во втором параграфе. Основное изменение в алгоритме Мах1Б - это введение отсечения ветвей дерева поиска, исходя из мощности базового множества выбранного узла.

I, с

————— ВгопКегЬозИ

________ дциз

Рис. 1: Зависимость времени работы алгоритмов Брона-Кербоша и АШв от плотности ребер графов при фиксированной размерности.

а) б)

Рис. 2: Зависимость времени работы алгоритмов Брона-Кербоша и AIIIS от размерности графов при значении плотности ребер р = 6% (а) и р = 4% (б).

Справедлива следующая теорема:

Теорема 5. Если в некотором подграфе Gk С Gk~l С ... С G0 для базового множества выбранного узла = выполнено условие:

max 11

тогда мощность независимого множества, содержащего пару вершин /3,, 7*, не превзойдет мощности текущего наибольшего независимого множества:

ЮШ < \Qmax\-

Второе изменение в алгоритме МахШ - это отказ от использования окрестностей. Доказывается, что в отличие от алгоритма АШБ, для нахождения наибольшего независимого множества использовать окрестность нецелесообразно. И наконец, третье изменение связано с подсчетом количества элементов множества 5[а,] после принятия решения о построении ветви дерева поиска, идущей из текущего выбранного узла а*. Пусть = т.

1) Если |5[а£]| = т("~1), значит, опорное множество целиком пред-

ставляет собой независимое множество. В этом случае, текущим наибольшим независимым множеством будет множество

Отах = {/3?, 7?, 7,\ /Г V7Г1} и

2) Условие |5[а»]| = - 1 говорит о том, что среди элементов опорного

множества и)[а£] только две вершины соединены ребром. В случае выполнения условия \0[а^]\+2к-1 > |<2тах|, в качестве нового наибольшего независимого множества будет выступать множество

О™* = {/М,/«, ..../ЗГлГ1} и Ма*] \ {6}),

где вершина 5 - одна из пары вершин опорного множества и;[а£], которые соединены между собой ребром.

3) В случае, когда |5[а^]| = т("~1) - 2, некоторые вершины опорного множества соединены ребрами, причем количество ребер однозначно

равно двум, а количество вершин, инцидентных этим ребрам, может быть равно либо трем, либо четырем. В такой ситуации нужно определить сколько различных вершин участвует в образовании ребер.

Если количество различных вершин равно трем, значит, необходимо проверить условие:

тах | •

В случае его выполнения

Ягпа:г = {/£, 7?, 7,\ Ч*"1} и М^] \ {?}),

где вершина 5 инцидентна обоим ребрам.

Если же количество различных вершин равно четырем, то при выполнении условия |£>[а^]| +2к — 2 > \Ятах\ наибольшим независимым множеством будет

Ятах = {А°,7и И «Я \ где вершины ¿1 и ¿2 инцидентны разным ребрам.

В третьем параграфе поиск наибольшего независимого множества по алгоритму Мах1Б проиллюстрирован на примере обработки неориентированного 10-вершинного графа. Как и в предыдущей главе, заключительный параграф третьей главы посвящен тестированию программной реализации разработанного алгоритма. Представлены результаты сравнения работы алгоритма Мах1Б с алгоритмом Робсона, а также методом полного перебора, несколько модифицированным для нахождения одного наибольшего независимого множества.

Тестирование работы алгоритмов МахШ и Робсона проводилось на одинаковом наборе графов с различными значениями плотности ребер. Экспериментальные результаты показали (Рисунки 3, 4), что при значении плотности больше 70% оба алгоритма имеют практически одинаковый порядок роста времени работы, не превышающий 0(2°'276п).

Практическое применение разработанных алгоритмов продемонстрировано в четвертой главе на примере решения некоторых задач из биоинформатики. В первом параграфе рассматривается задача поиска максимальной общей подструктуры органических соединений. Строится модель угольной кислоты и глицина в виде молекулярных графов, для которых ищется подграф, изоморфный исследуемым графам. Проблема изоморфного вхождения сводится к задаче поиска наибольшей клики вспомогательного графа, для

20 40 СО СО 100

л

■ Robspn Maxis

- 2*n

—2*(0. 27В п|

Рпс. 3: Зависимость Бремени работы алгоритмов Робсоиа и MaxIS от размерности графов пои фиксированной плотности р = 70%.

I. С I, с

а) б)

Рис. 4: Зависимость времени работы алгоритмов Робсона и МахН от размерности графов при значении плотности р — 85% (а) и р = 95% (б).

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

В заключении диссертации представлены основные результаты, полученные в ходе исследования.

/С

Список публикаций по теме диссертации

1. Фирюлина О. С.. Олемской И. В., Нечипорук А. А. Алгоритм нахождения наибольшего независимого множества // Процессы управления и устойчивость: Труды 40-й межд. научи, копф. аспирантов и студентов/ Под ред. Н.В. Смирнова, Г. Ш. Тамасяна - СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2009. С. 73-78.

2. Фирюлина О. С. Метод построения максимальных независимых множеств // Процессы управления и устойчивость: Труды 41-й межд. научн. копф. аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2010. С. 68-72.

3. Фирюлина О. С., Олемской И. В. Алгоритм решения задачи о наибольшем независимом множестве // Устойчивость и процессы управления: Всероссийская копф., посвящ. 80-летию со дня рождения В. И. Зубова. Санкт-Петербург, 1-2 июля 2010 г. - С.-Петербург: ВВМ, 2010. С. 212.

4. Фирюлина О. С. Вычисление неплотности квадратных (0,1)-матриц // Процессы управления н устойчивость: Труды 43-й межд. паучн. копф. аспирантов и студентов /' Под ред. А. С. Ерёмина, Н. В. Смирнова. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2012. С. 55-60.

5. Олемской И. В., Фирюлина О. С. Алгоритм вычисления наибольшего независимого множества // Обозрение прикладной и промышленной математики. 2012. Т. 19, Вып. 3. С. 10.

0. Фирюлина О. С. Нахождение всех максимальных независимых множеств неориентированного графа // Вестп. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика. процессы управления. 2013. Вып. 1. С. 63-69.

7. Олшской И. В., Фирюлина О. С. Решение задачи о поиске максимальной общей подструктуры в молекулярных графах // Процессы управления и устойчивость: Труды 44-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Т. Б. Смирновой. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2013. С. 355-360.

8. Олемской И. В., Фирюлина О. С. Алгоритм поиска наибольшего независимого множества // Всстн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. 2014. Вып. 1. С. 81-91.

Подписано к печати 04.04.14. Формат 60 х 84 'Лб.

Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 1,00. Тираж 100 экз. Заказ 6014.

Отпечатано в Отделе оперативной полиграфии химического факультета СПиГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043, 428-6919

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

04201458947 На правах рукописи

ФИРЮЛИНА Оксана Сергеевна

УДК 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. Алгоритм AUIS построения всех максимальных независимых множеств

графа.................................................................................................................32

§3. Теоретическое обоснование алгоритма AUIS...........................................35

§4. Пример построения максимальных независимых множеств...................49

§5. Тестирование программной реализации..................................................55

ГЛАВА 3. АЛГОРИТМ MAXIS ПОИСКА НАИБОЛЬШЕГО НЕЗАВИСИМОГО МНОЖЕСТВА

§1. Модификация алгоритма А IIIS для решения задачи о наибольшем независимом множестве...........................................................................................62

§2. Теоретическое обоснование алгоритма MaxIS........................................64

§3. Пример построения наибольшего независимого множества...................69

§4. Тестирование программной реализации.................................................77

ГЛАВА 4. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ АЛГОРИТМОВ MAXIS И ALLIS

§1. Поиск максимальной общей подструктуры органических соединений....83

§2. Построение потенциальных вторичных структур РНК..........................88

ЗАКЛЮЧЕНИЕ.......................................................................................92

СПИСОК ЛИТЕРАТУРЫ.....................................................................94

ПРИЛОЖЕНИЕ 1. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДА ПОЛНОГО ПЕРЕВОРА ДЛЯ ПОИСКА НАИБОЛЬШЕГО НЕЗАВИСИМОГО МНОЖЕСТВА...................................................................102

ПРИЛОЖЕНИЕ 2. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДА ПОЛНОГО ПЕРЕБОРА ДЛЯ ПОСТРОЕНИЯ ВСЕХ МАКСИМАЛЬНЫХ НЕЗАВИСИМЫХ МНОЖЕСТВ.................................................105

ПРИЛОЖЕНИЕ 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА БРОНА-КЕРБОША...........................................................................108

ПРИЛОЖЕНИЕ 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА РОБСОНА.............................................................................................110

ПРИЛОЖЕНИЕ 5. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ALLIS......................................................................................................135

ПРИЛОЖЕНИЕ 6. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА MAXIS....................................................................................................142

ВВЕДЕНИЕ

Роль теории графов в математическом моделировании трудно переоценить. Модели на графах применяются в самых различных областях науки и техники: от социологии до компьютерных технологий. Это объясняется тем, что такие модели обладают высокой степенью наглядности и потому понятны и удобны в использовании.

Теория графов как один из важнейших разделов дискретной математики начала развиваться с 1930-х г [16]. Развитие вычислительной техники позволило обрабатывать графы больших размерностей. Но, несмотря на это, в теории графов до сих пор остаются задачи, которые имеют репутацию «трудно вычислимых», даже с использованием самых современных компьютерных технологий. Речь идет о так называемых ЫР-полных задачах. К таким задачам относят те, для которых в настоящее время не существует точных алгоритмов решения с полиномиальной оценкой сложности. Доказано существование несколько сотен А^Р-полных задач [2], но, к сожалению, ни одна из них пока не может быть решена за полиномиальное время. Создание полиномиального точного алгоритма хотя бы одной из них привело бы к разработке эффективных алгоритмов для всех остальных задач данного класса. Это означало бы решение одной из основных проблем теории сложности, проблемы несовпадения слож-ностпых классов Р ф ЫР [6]. Эту проблему можно сформулировать следующим образом: можно ли все задачи, решение которых проверяется с полиномиальной сложностью решить за полиномиальное время? В настоящее время нет теоретических доказательств как возможности, так и невозможности существования подобных алгоритмов решения. Проблема Р ^ ЫР неоднократно поднималась в работах разных авторов [7], [32], [37], [38]. Согласно проведенному исследованию публикаций последних лет (2001-2010гг.): [31], [34], [35], [36], [47], [55], [61], [70], [71], проблема поиска эффективных точных алгоритмов решения А^Р-полных задач не прекращает привлекать к себе внимание

исследователей всего мира и продолжает оставаться актуальной и в настоящее время.

В диссертационной работе рассматривается решение одной из важнейших Л^Р-полной задачи дискретной математики, а именно, поиск максимальных независимых множеств (МНМ) неориентированного графа. Алгоритмы решения этой задачи используются в широких спектрах прикладных проблем, в том числе в социометрии [40], химии [29], [59], [72], компьютерных технологиях [43], [58], [64], [65] и биоинформатике [17], [26], [30], [42], [62], [67], [68]. Это объясняется тем, что специальным образом представив объект исследования в виде модели на графе, множество задач из выше указанных областей науки можно свести к задаче поиска клики в неориентированном графе, что в свою очередь легко трансформируется в задачу нахождения максимальных независимых множеств графа.

Начиная с 50-х годов прошлого века было предложено много точных алгоритмов для решения задач, связанных с поиском максимальных независимых множеств, например, [27], [36], [40], [60], [66], но построить эффективный алгоритм, имеющий полиномиальную оценку сложности, никому до сих пор не удалось. Если для задачи о перечислении всех клик графа разработка такого алгоритма представляется мало вероятной (в силу экспоненциальной зависимости количества клик от размерности графа [52]), то для поиска одного наибольшего независимого множества невозможность построения подобного алгоритма остается недоказанной в силу нерешенной проблемы Р ф N Р. Это вдохновляет исследователей всего мира на создание всё новых и новых точных алгоритмов решения задачи о наибольшей клике, в надежде на создание полиномиального алгоритма. Исходя из того, что все эти алгоритмы имеют экспоненциальную оценку сложности 0(2ап), разработчики стараются модифицировать свои алгоритмы с целью сокращения дерева поиска, что в свою очередь приводит к уменьшению показателя а.

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

1. Исследование проблемы поиска МНМ графа, а также существующих методов ее решения.

2. Разработка и формализация алгоритмов поиска МНМ графа, основанных на идеи расширения независимого множества на каждом уровне дерева поиска парой вершин.

3. Разработка комплекса проблемно-ориентированных программ, предназначенного для решения задачи поиска МНМ графа.

4. Проведение серии вычислительных экспериментов с целью сравнения качества работы предложенных алгоритмов с другими методами поиска МНМ.

5. Исследование области применения разработанных алгоритмов.

В работе используются аппарат теории графов, методы комбинаторного анализа, методы разработки эффективных алгоритмов и анализа их временной сложности.

Достоверность научных результатов обеспечивается строгостью доказательств, согласованностью с уже имеющимися результатами в данной и смежных областях.

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

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

При тестировании алгоритм AUIS сравнивался с известным алгоритмом Брона-Керрбоша для перечисления всех максимальных независимых множеств в неориентированном графе, который до сих пор является одним из наиболее эффективных для решения этой задачи [42]. На тестируемом наборе матриц при низком значении плотности ребер алгоритм AUIS показал лучшие результаты, чем алгоритм Брона-Кербоша.

В качестве оппонента для алгоритма MaxIS был выбран алгоритм Робсона. Выбор именно этого алгоритма объясняется тем, что

1) он один из немногих среди большого количества существующих в настоящее время точных алгоритмов имеет теоретическую оценку сложности;

2) согласно этой оценке О(20-276п) алгоритм Робсона является одним из наиболее эффективных для решения задачи о поиске наибольшего независимого множества.

Тестирование работы алгоритмов MaxIS и Робсона также проводилось на одинаковом наборе графов с различными значениями плотности ребер. Экспериментальные результаты показали, что при высоком значении плотности оба алгоритма имеют одинаковый порядок роста времени работы, не превышающий 0( 2°-276п).

Принимая во внимание результаты исследования, проведенного в рамках диссертационной работы, можно заключить, что разработанные алгоритмы могут быть использованы для решения многочисленных задач из разных облас-

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

Основные результаты, выносимые на защиту.

1. Алгоритм (AUIS) построения всех максимальных независимых множеств и алгоритм {MaxIS) поиска наибольшего независимого множества в произвольном неориентированном графе.

2. Теоретическое обоснование корректности работы алгоритмов AIIIS и MaxIS (теоремы 1-5).

3. Модификация алгоритма Робсона для нахождения наибольшего независимого множества.

4. Результаты вычислительных экспериментов, позволившие выявить особенности поведения разработанных алгоритмов на графах с различными значениями плотности ребер, а также результаты сравнения времени работы с другими известными алгоритмами.

5. Комплекс проблемно-ориентированных программ, предназначенный для решения задачи о поиске максимальных независимых множеств.

Основные результаты диссертационного исследования были представлены на 40-й международной научной конференции аспирантов и студентов „Процессы управления и устойчивость" (Санкт-Петербург, 2009 г.), 41-й международной научной конференции аспирантов и студентов „Процессы управления и устой-

чивость" (Санкт-Петербург, 2010 г.), всероссийской конференции, посвященной 80-летию со дня рождения В. И. Зубова „Устойчивость и процессы управления" (Санкт-Петербург, 2010 г.), 43-й международной научной конференции аспирантов и студентов „Процессы управления и устойчивость" (Санкт-Петербург, 2012 г.), XIII всероссийском симпозиуме по прикладной и промышленной математики (Петрозаводск, 2012 г.), 44-й международной научной конференции аспирантов и студентов „ Процессы управления и устойчивость" (Санкт-Петербург, 2013 г.).

По теме диссертации опубликовано 8 работ ([13], [14], [15], [19], [20], [21], [22], [23]), в том числе две статьи [15], [23] в журнале, входящем в перечень изданий, рекомендованных ВАК РФ.

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

Вторая глава диссертации посвящена разработке нового алгоритма поиска всех максимальных независимых множеств - алгоритма АШЯ. В первом параграфе даны определения и базовые конструкции разработанного алгоритма. Обсуждение основных моментов его работы, а также псевдокод алгоритма, приведены во втором параграфе. В третьем параграфе доказываются теоремы, обеспечивающие теоретическое обоснование корректности работы алгоритма. Подробный пример использования алгоритма АШБ для решения задачи о поиске всех МНМ графа представлен в четвертом параграфе. Заключительный параграф главы посвящен тестированию программной реализации разработанного алгоритма. Приведены результаты сравнения работы алгоритма АШЯ с известным алгоритмом Брона-Кербоша, а также методом полного перебора.

В третьей главе предложен новый алгоритм решения задачи о поиске наибольшего независимого множества в произвольном неориентированном графе -алгоритм Мах1Б, псевдокод которого приведен в первом параграфе. Алгоритм Мах1в является модификацией алгоритма ЛШЯ, рассмотренного в предыдущей главе. Обсуждение изменений, проведенных в алгоритме АШ8, а также доказательства теорем, обеспечивающих правомерность этих изменений, приведены во втором параграфе. В третьем параграфе поиск наибольшего независимого множества с использованием алгоритма Мах1в проиллюстрирован на примере обработки неориентированного десятивершиниого графа. Как и в предыдущей главе, заключительный параграф третьей главы посвящен тестированию программной реализации разработанного алгоритма. Представлены результаты сравнения работы алгоритма Мах!Я с алгоритмом Робсона, а также методом полного перебора, несколько модифицированным для нахождения одного наибольшего независимого множества.

Практическое применение разработанных алгоритмов продемонстрировано в четвертой главе на примере решения некоторых задач из биоинформатики. В первом параграфе рассматривается задача поиска максимальной общей подструктуры органических соединений. Строится модель угольной кислоты и глицина в виде молекулярных графов, для которых ищется подграф, изоморфный исследуемым графам. Проблема изоморфного вхождения сводится к задаче поиска наибольшей клики вспомогательного графа, для решения которой используется алгоритм Мах18. Второй параграф посвящен проблеме определения потенциальных вторичных структур РНК, моделирование которых проводится с использованием неориентированного графа. В полученном графе с помощью программной реализации алгоритма АШБ организуется поиск всех клик, которые и соответствуют искомым структурам.

В заключении диссертации представлены основные результаты, полученные в ходе исследования.

ГЛАВА 1. ЗАДАЧА О ПОИСКЕ МАКСИМАЛЬНЫХ НЕЗАВИСИМЫХ МНОЖЕСТВ

§1. Основные определения

Прежде чем ввести основные определения, укажем список употребляемых понятий и обозначений общего характера. Определения и обозначения взяты ИЗ [3], [9], [33].

х Е А - элемент х принадлежит множеству А; х ^ А - элемент х не принадлежит множеству А; АС В - множество А является подмножеством множества В\ А С В - строгое подмножество (А С В и А ф В