Электронная библиотека
Тамбовского государственного университета им. Г.Р. Державина

     
?

Детальная информация
Карточка Таблица RUSMARC

ДЫРДИН, КИРИЛЛ ДМИТРИЕВИЧ. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ НА ГРАФАХ [Электронный ресурс]: бакалаврская работа: 01.03.02 Прикладная математика и информатика: Очная форма обучения / К. Д. ДЫРДИН; ТГУ им. Г. Р. Державина ; науч. рук. к. т. н., доцент, И. А. Соловьева. — Электрон. текстовые дан. (1 файл). — Тамбов, 2026. — Загл. с титул. экрана. — <URL:https://elibrary.tsutmb.ru/dl/docs/vkr20033.pdf>.

Дата создания записи: 30.06.2026

Тематика: теория графов; задача оптимизации на графах; кратчайший путь; минимальное остовное дерево; алгоритм; вычислительная сложность; программная реализация

Коллекции: Выпускные квалификационные работы (бакалавриат)

Разрешенные действия: –

Группа: Анонимные пользователи

Сеть: Интернет

Права на использование объекта хранения

Место доступа Группа пользователей Действие
Локальная сеть ФБ ТГУ МО Прочитать Печать Загрузить
Интернет МО Прочитать Печать Загрузить
Интернет Читатели Прочитать
-> Интернет Анонимные пользователи

Оглавление

  • ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ
  • ВВЕДЕНИЕ
  • 1 ОБЗОР ЛИТЕРАТУРЫ
    • 1.1 Основные понятия теории графов и постановки задач оптимизации
    • 1.2 Задача поиска кратчайших путей и её разновидности
      • 1.2.1 Single-Source Shortest Paths (SSSP)
      • 1.2.2 Single-Pair Shortest Path (SPSP)
      • 1.2.3 All-Pairs Shortest Paths (APSP)
      • 1.2.4 Особые случаи весов
    • 1.3 Алгоритм Дейкстры и его модификации
      • 1.3.1 Псевдокод алгоритма Дейкстры
      • 1.3.2 Реализация за O(V²)
      • 1.3.3 Реализация на бинарной куче
      • 1.3.4 Реализация на сбалансированном множестве
      • 1.3.5 Дейкстра на дереве отрезков
      • 1.3.6 Пример работы алгоритма
    • 1.4 Алгоритмы для графов с отрицательными весами
      • 1.4.1 Алгоритм Беллмана – Форда
      • 1.4.2 Алгоритм Беллмана – Форда – Мура (SPFA)
      • 1.4.3 Сравнение алгоритмов для SSSP
    • 1.5 Алгоритмы поиска всех пар кратчайших путей
      • 1.5.1 Алгоритм Флойда – Уоршалла
      • 1.5.2 Алгоритм Джонсона
    • 1.6 Специализированные алгоритмы: 0-1 BFS, k-BFS, A*
      • 1.6.1 Алгоритм 0-1 BFS
      • 1.6.2 Алгоритм k-BFS
      • 1.6.3 Алгоритм A*
    • 1.7 Алгоритмы поиска нескольких путей: Суурбалле и Эппштейна
      • 1.7.1 Алгоритм Суурбалле
      • 1.7.2 Алгоритм Эппштейна
    • 1.8 Задача о минимальном остовном дереве
    • 1.9 Алгоритмы Краскала, Прима и Борувки
      • 1.9.1 Алгоритм Краскала
      • 1.9.2 Алгоритм Прима
      • 1.9.3 Алгоритм Борувки
      • 1.9.4 Сравнение алгоритмов MST
    • 1.10 Обобщения задачи MST
      • 1.10.1 Minimum Diameter Spanning Tree (MDST)
      • 1.10.2 Steiner Tree Problem (задача Штейнера на графах)
      • 1.10.3 Manhattan MST
    • 1.11 Теоретические основы корректности алгоритмов
      • 1.11.1 Свойство оптимальной подструктуры для кратчайших путей
      • 1.11.2 Доказательство корректности алгоритма Дейкстры
      • Замечание 1.1. Условие неотрицательности весов в теореме существенно: при наличии отрицательного ребра алгоритм Дейкстры может выбрать вершину, чьё значение dist ещё подлежит уменьшению из-за релаксации через необработанную вершину с отрицательным исх...
      • 1.11.3 Доказательство корректности алгоритмов MST
      • 1.11.4 О роли структуры данных в эффективности
    • 1.12 Историческая перспектива и развитие алгоритмов на графах
    • 1.13 О применимости рассмотренных алгоритмов в смежных задачах
  • 2 МЕТОДОЛОГИЧЕСКАЯ И РЕСУРСНАЯ БАЗЫ РАБОТЫ
    • 2.1 Обоснование выбора языка и среды разработки
    • 2.2 Используемые библиотеки и структуры данных
      • 2.2.1 Стандартная библиотека Python
      • 2.2.2 Внешние библиотеки
      • 2.2.3 Структуры данных
    • 2.3 Методика проведения эксперимента
    • 2.4 Класс моделей и варьируемые параметры
      • 2.4.1 Разреженный случайный связный граф
      • 2.4.2 Плотный случайный граф
      • 2.4.3 Граф Эрдёша – Реньи G(n, p)
      • 2.4.4 Граф Барабаши – Альберта
      • 2.4.5 Регулярная сетка
      • 2.4.6 Случайное множество точек
  • 3 ПРЕДПРОЕКТНОЕ ИССЛЕДОВАНИЕ
    • 3.1 Обзор существующих программных решений
      • 3.1.1 NetworkX
      • 3.1.2 igraph
      • 3.1.3 graph-tool
      • 3.1.4 LEMON
      • 3.1.5 Boost Graph Library (BGL)
      • 3.1.6 Сравнение с разрабатываемым модулем
    • 3.2 Сравнительный анализ функциональности существующих библиотек
    • 3.3 Сводный анализ сложности рассмотренных алгоритмов
      • 3.3.1 Сравнительная характеристика алгоритмов SSSP
      • 3.3.2 Сравнительная характеристика алгоритмов APSP
      • Как показано в таблице 3.2, единственным алгоритмом, способным превзойти кубическую сложность Флойда–Уоршалла, является метод Сейделя, ориентированный на невзвешенные графы. Он использует быстрое умножение матриц и достигает времени O(,𝑽-𝝎. log V) с...
      • 3.3.3 Сравнительная характеристика алгоритмов MST
      • Данные таблицы 3.3 показывают, что алгоритм Карджера–Клейна–Тарьяна достигает линейного времени O(V+E) в среднем, оставаясь линейным и в худшем случае (с оговоркой на большую константу в детерминированной версии). Однако из‑за сложности реализации он ...
      • 3.3.4 Замечание о константных множителях
    • 3.4 Углублённый анализ специализированных алгоритмов
      • 3.4.1 Теоретические свойства алгоритма A*
      • 3.4.2 Подробнее об алгоритме Суурбалле
      • 3.4.3 Подробнее об алгоритме Эппштейна
      • 3.4.4 Подробнее о задаче Штейнера
      • 3.4.5 Manhattan MST: тонкости реализации
  • 4 РЕЗУЛЬТАТЫ ПРОЕКТИРОВАНИЯ
    • 4.1 Архитектура программной системы
    • 4.2 Реализация алгоритмов кратчайших путей
      • 4.2.1 Реализация алгоритма Дейкстры
      • 4.2.2 Реализация Беллмана – Форда и SPFA
      • 4.2.3 Реализация Флойда – Уоршалла и Джонсона
    • 4.3 Реализация алгоритмов построения остовного дерева
      • 4.3.1 Класс DSU
      • 4.3.2 Реализация Краскала
      • 4.3.3 Реализация Прима
      • 4.3.4 Реализация Борувки
      • 4.3.5 Реализация Manhattan MST
    • 4.4 Демонстрация интерфейса и возможностей
    • 4.5 Тестирование и валидация реализаций
      • 4.5.1 Сравнение с эталонными реализациями
      • 4.5.2 Проверка инвариантов
      • 4.5.3 Граничные случаи
      • 4.5.4 Корректность Суурбалле и Эппштейна
    • 4.6 Профилирование и оптимизация производительности
      • 4.6.1 Использование cProfile
      • 4.6.2 Микробенчмарки
      • 4.6.3 Ограничения интерпретатора Python
  • 5 ВЫВОДЫ И ОБСУЖДЕНИЕ
    • 5.1 Эксперимент 1. Кратчайшие пути на разреженных графах
    • 5.2 Эксперимент 2. Кратчайшие пути на плотных графах
    • 5.3 Эксперимент 3. Сравнение алгоритмов «все пары»
    • 5.4 Эксперимент 4. A* против Дейкстры на сетке
    • 5.5 Эксперименты 5–6. Алгоритмы MST
      • 5.5.1 MST на разреженных графах
      • 5.5.2 MST на плотных графах
    • 5.6 Эксперимент 7. Зависимость от топологии графа
    • 5.7 Эксперимент 8. Manhattan MST
    • 5.8 Сводный анализ и рекомендации
    • 5.9 Углублённый анализ: масштабирование и теоретические предсказания
      • 5.9.1 Проверка оценки O(V²) для Дейкстры на плотных графах
      • 5.9.2 Проверка оценки O((V+E) log V) для Дейкстры на куче
      • 5.9.3 Проверка оценки O(V³) для Флойда – Уоршалла
      • 5.9.4 Проверка модели для алгоритма Джонсона
    • 5.10 Влияние реализации интерпретатора
    • 5.11 Сравнение с библиотечной реализацией NetworkX
    • 5.12 Дополнительный эксперимент: реальные графы
      • 5.12.1 Граф «социальной сети»
      • 5.12.2 Граф «дорожной сети»
      • 5.12.3 Граф зависимостей программных пакетов
    • 5.13 Обсуждение применимости результатов
      • 5.13.1 Маршрутизация в компьютерных сетях
      • 5.13.2 Транспортные и логистические задачи
      • 5.13.3 Проектирование сетей связи
      • 5.13.4 Биоинформатика
      • 5.13.5 Анализ программного кода
      • 5.13.6 Социальные сети
    • 5.14 Анализ ошибок и численной устойчивости
    • 5.15 Оценка применимости разработанного модуля
      • 5.15.1 Сильные стороны
      • 5.15.2 Ограничения
      • 5.15.3 Перспективы развития
  • ЗАКЛЮЧЕНИЕ
  • СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
  • ПРИЛОЖЕНИЕ А
    • А.1 Модуль shortest_paths.py – алгоритмы кратчайших путей
    • А.2 Модуль mst.py – алгоритмы построения остовного дерева
    • А.3 Модуль generators.py – генераторы тестовых графов
    • А.4 Модуль run_experiments.py – запуск вычислительного эксперимента
    • А.5 Модуль make_plots.py – построение графиков по результатам

Статистика использования

stat Количество обращений: 0
За последние 30 дней: 0
Подробная статистика