Использование графов для решения различных задач приобретает все большую актуальность с развитие информационных технологий и вычислительных мощностей процессоров. Задачи, связанные с обработкой данных на основе графовой модели, находят применение во многих областях, таких как вычислительные, коммуникационные и транспортные сети: протоколы маршрутизации в сети Интернет и организация эффективной работы сети межсоединений в многопроцессорных системах, логистика транспортных предприятий, - алгоритмические и электрические схемы: программные компиляторы, расположение элементов на печатной плате, - биологии и химии: сборка генома, биомолекулярные сети, описание структурных соединений и процессов химических реакций.
Многие задачи из теории графов являются труднорешаемыми, т.е. не имеющими решение за полиномиальное время - задачи класса NP полных. К таким задачам, например, относятся: задачи о раскраске, ранце, кликах, вершинном покрытии, дереве Штайнера и Гамильтоновом графе. Все эти задачи не имеют точного алгоритма решения за приемлемое полиномиальное время. Тем не менее, существуют подходы, позволяющие ускорить решение подобных задач, например, с помощью сокращения перебора решений - метод ветвей и границ, позволяющий существенно сократить поиск путем отсеивания бесперспективных вариантов при помощи оценочных методов и схемы одностороннего ветвления - разбиения дерева вариантов на непересекающиеся подмножества, часть которых может заведомо не содержать оптимальных решений. Таким образом, при использовании дополнительной информации в виде записей по ходу работы алгоритма становится возможным повысить эффективность перебора и формирование частичных решений. Другим эффективным методом является метод снижения требований - вместо оптимального решения ведется поиск приближенного решения эвристическими алгоритмами за приемлемое время. Такие алгоритмы используют некоторый набор разумных правил, но не опираются на строгое подтверждение оптимальности, полноты или точности решений. Таким образом, удается быстро найти достаточно хорошее приближенное или аппроксимированное решение для NP полных задач. Многие оптимизационные варианты задач также могут решаться с помощью методов динамического программирования - процесс пошагового решения задач от малых к большим с запоминанием решения. Таким задача сводится к классу более простых подзадач, решение которых формирует решение исходной задачи.
Одними из NP полных задач, имеющих большое практическое применение в различных областях, являются задачи, связанные с поиском клик - полных подграфов в первоначальном графе. Активное изучение клик в теории графов началось с работы Льюиса и Перри (1949), в которой они использовали полные подграфы для моделирования сообществ в социальных сетях. Масштабные исследования в области поиска клик в 1970-ые годы привели к созданию алгоритмов, ставших классическими. Дальнейшие модификации этих алгоритмов, а также применение новых подходов позволило улучшить эффективность решения задач на практике. Исследования возможных их улучшений ведется и сейчас. Последние научно-исследовательские работы, проведенные в 2000-ые годы, оказали существенное влияние на теоретические и практические достижения в области разработки алгоритмов, привели к формированию многих принципиально новых результатов о возможностях решения задач поиска клик. Такие задачи имеют применение в биоинформатике, вычислительной химии и геометрии, компиляторной оптимизации и статистике, оптимизации различных схем и аналитике сетей. Особенный интерес вызывают задачи поиска максимальных клик и кликовых покрытий. Так, например, поиска максимальных клик позволяет формировать клики максимальных размеров, тем самым выявляя в графе самые крупные максимально взаимосвязанные компоненты, а поиск минимального кликового покрытия ребер - задача, обозначаемая также как число пересечений графа, используется в биоинформатике для идентификации перекрывающихся белковых комплексов для сети двоичных белковых взаимодействий.
Задачей данной выпускной квалификационной работы является эффективная параллельная реализация и исследование алгоритмов поиска максимальных клик и минимального кликового покрытия ребер, а также дополнительных алгоритмов для генерации графов и оптимизационных процедур некоторых алгоритмов. Результатом исследования станет выявление сильных и слабых сторон алгоритмов в зависимости от различных критериев, таких как производительность, используемая память и точность на графах с разными параметрами количества вершин, плотности и размера клик. Будут сделаны выводы об эффективности различных оптимизационных решений. Также будет исследована возможность эффективного распараллеливания алгоритмов.
В рамках данной выпускной квалификационной работы были эффективно реализованы и распараллелены классические алгоритмы поиска максимальных клик и минимального кликового покрытия ребер с различными модификациями и оптимизационными решениями, а также дополнительные алгоритмы для генерации графов. Было проведено исследование алгоритмов по различным критериям. По результатам работы:
• подтверждена более высокая точность модификации Грэмма эвристического алгоритма Келлермана и существенное сокращение операций перебора всех клик,
• проанализирована эффективность точного алгоритма Грэмма в сравнении с эвристическими алгоритмами,
• подтверждены результаты исследования Грэмма границ отклонений производительности точного алгоритма,
• подтверждена относительно приемлемая сокрость работы точного алгоритма на разреженных графах,
• проанализирована точность эвристических алгоритмов в сравнении с точным алгоритмом,
• была исследована производительность алгоритмов поиска максимальных клик,
• была подтверждена сравнительно высокая эффективность алгоритмов Эпштайна на разреженных графах в сравнении с алгоритмами Брона-Кербоша и Томиты,
• выявлена эффективность использования библиотеки быстрой арифметики GMP для ускорения операций с множествами,
• была исследована возможность эффективного распараллеливания алгоритмов.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
