ИССЛЕДОВАНИЕ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ

Введение
Постановка задачи 6
2. Выбор средств разработки 7
3. Поиск минимального кликового покрытия ребер 8
3.1 Общая идея 8
3.2 Эвристический алгоритм Келлермана 9
3.3 Постпроцессинговая модификация Коу 10
3.4 Модификация Грэмма для эвристического алгоритма 11
3.1 Точный алгоритм Грэмма с использованием сокращения данных
4. Поиск максимальных клик 15
4.1 Общая идея 15
4.2 Алгоритм Брона-Кербоша 15
4.3 Модификация Томиты 16
4.4 Алгоритм Эпштайна 17
4.4.1 Оптимизация с использованием обновляемой структуры 19
5. Генерация графов с заданными параметрами 21
6. Эксперименты с алгоритмами 25
6.1 Эвристические алгоритмы поиска минимального кликового покрытия
6.2 Точный алгоритм поиска минимального кликового покрытия 34
6.3 Алгоритмы поиска максимальных клик 40
6.4 Дополнительные алгоритмы 45
6.5 Исследование точности эвристических алгоритмов 50
6.6 Исследование использования памяти алгоритмами 53
Заключение 56
Список литературы 57
Приложение А

Купить

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