Курсовая работа: Поиск кратчайших путей в графе методом динамического программирования

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ИНКЛЮЗИВНОГО ВЫСШЕГО ОБРАЗОВАНИЯ

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНО-ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ»

Факультет Цифровых технологий и кибербезопасности

Кафедра информационных технологий и кибербезопасности

Курсовая работа по дисциплине:

«Дискретная математика»

на тему: «Поиск кратчайших путей в графе методом динамического программирования»

Выполнил:

Студент группы ПИ-0221

Орехов С.В.

Проверил:

Ст. преп. Кафедры ЦТ

Труб Н. В.

Москва 2023

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ИНКЛЮЗИВНОГО ВЫСШЕГО ОБРАЗОВАНИЯ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ

ГУМАНИТАРНО-ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра Информационных технологий и кибербезопасности

ЗАДАНИЕ

на курсовую работу

по дисциплине «ДИСКРЕТНАЯ МАТЕМАТИКА»

Студенту 2 курса группы ПИ-0221

факультета «Цифровых технологий и кибербезопасности»

Орехову Савве Витальевичу

1. Тема _Поиск кратчайших путей в графе методом динамического программирования.

2. Исходные данные к работе ___В ориентированном взвешенном графе G=(V,E), вес рёбер которого может включать отрицательные веса и определяется весовой функцией , алгоритмы Дейкстры и Беллмана-Форда находят длины кратчайших путей между всеми вершинами взвешенного ориентированного графа. Целью данной работы является изучение этих алгоритмов, а также разработка программы, реализующей любой из них методом динамического программирования.

3. Содержание пояснительной записки (перечень подлежащих разработке вопросов) Рекомендуется следующий план работы.

1). Изучить такие основополагающие понятия теории графов, как орграф, ориентированный маршрут и орцепь.

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

3). Разобрать алгоритм Беллмана-Форда нахождения кратчайшего расстояния между всеми вершинами в графе.

4). Применить один из этих алгоритмов к представлению блок-схемой.

5). Разработать программу, реализующую этот алгоритм.

4. Перечень графического материала с точным указанием обязательных чертежей ___нет, только требуемые в качестве иллюстраций.

5. Литература, пособия:

1. Остин Оре Графы и их применение - М.: 2020. - 175 с.

2. Ф.Харари Теория графов. - Ленанд, 2019

3. Голицына О. Л., Попов И. И. Основы алгоритмизации и программирования: Учебное пособие, М.: ФОРУМ. 2017. 432 с.

4. Алгоритм Дейкстры

http://works.doklad.ru/view/Oikoq6JYpOY/all.html

5. "Библиотека алгоритмов на графах", http://urban-sanjoo.narod.ru/kruskal.html

6. Р. Седжвик. Фундаментальные алгоритмы на С++: Алгоритмы на графах / пер. с англ. - СПб.: Диасофт, 2019. - 496 с.

Содержание

Введение

Глава 1. Алгоритмы динамического программирования в теории графов

1.1 Основы теории графов

1.2 Алгоритмы Дейкстры

1.3 Алгоритм Беллмана-Форда

1.4 Сравнение алгоритмов Дейкстры и Беллмана-Форда

Глава 2. Реализация алгоритма Беллмана-Форда в задаче поиска наикратчайшего пути в графе

2.1 Описание IDE

2.2 Формулировка задачи. Представление графов в ЭВМ

2.3 Иллюстрация алгоритма на примере графа

2.4 Алгоритмизация задачи

2.5 Разработка программы

2.6 Тестирование и отладка

Заключение

Библиографический список

Блок-схема

Исходный код

Введение

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

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

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

Актуальность применения теории графов на сегодняшний день очень высока благодаря своей универсальности и широкому спектру применения.

теория графы алгоритм динамическое программирование

Глава 1. Алгоритмы динамического программирования в теории графов

1.1. Основы теории графов

Граф - математический объект, состоящий из двух множеств. Одно из них - любое конечное множество, его элементы называются вершинами графа. Другое множество состоит из пар вершин, эти пары называются ребрами графа. Рис. 1.

Рис. 1. Изображение графа.

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

Стоит отметить, что в графе может быть не более одного ребра, соединяющего две вершины. Ребро типа (a, a), т.е. соединяющее вершину с ней же самой, называют петлей. Иногда петли разрешаются, иногда запрещаются. В последнем случае говорят, что рассматриваются графы без петель.

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

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

Если в графе есть ребро (a, b), то говорят, что вершины a и b в нем смежны. Ребро e = (a, b) называют инцидентным каждой из вершин a и b, а каждая из этих вершин инцидентна ребру e.

Множество вершин, смежных с данной вершиной x в некотором графе, называется окрестностью этой вершины и обозначается через N(x). Число вершин в N(x) называется степенью вершины x.

1.2. Алгоритмы Дейкстры

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

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

1.3 Алгоритм Беллмана-Форда

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

1.4 Сравнение алгоритмов Дейкстры и Беллмана-Форда

Алгоритм Дейкстры и алгоритм Беллмана-Форда являются алгоритмами поиска наикратчайшего пути в графе. Однако, они имеют свои отличительные черты.

Алгоритм Дейкстры является алгоритмом расчетливой оптимизации и решает задачу только для графов без циклов с отрицательными весами. Он начинает с заданной вершины и строит дерево кратчайших путей. В каждом шаге алгоритма выбирается следующая вершина с минимальной длиной пути до нее и обновляются пути через эту вершину. Алгоритм Дейкстры обладает усредненной временной сложностью O(E*log(V)), а наихудшая временная сложность - О(V²).

Алгоритм Беллмана-Форда способен решать более широкий класс задач. Он также может обрабатывать графы с отрицательными весовыми ребрами, но при этом обладает более высокой сложностью. Алгоритм Беллмана-Форда начинается с заданной вершины и выполняет релаксацию для каждого ребра графа V-1 раз, где V - число вершин в графе. После этого он проводит проверку на наличие отрицательных циклов. Если такой цикл существует, то алгоритм оповещает о невозможности вычисления наикратчайшего пути. Временная сложность алгоритма Беллмана-Форда равна O(V*E).

Таким образом, если граф не содержит отрицательных весовых ребер, то алгоритм Дейкстры является более эффективным. Если же граф содержит отрицательные весовые ребра, то алгоритм Беллмана-Форда может решить задачу поиска наикратчайшего пути, но при этом является менее эффективным, чем алгоритм Дейкстры.

Глава 2. Реализация алгоритма Беллмана-Форда в задаче поиска наикратчайшего пути в графе

2.1 Описание IDE

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

2.2 Формулировка задачи

Задача о поиске наикратчайшего пути в связном графе заключается в поиске самого короткого пути между двумя точками, в которой минимизируется сумма весов ребер (или их количество), составляющих путь. Эта задача является одной из важнейших классических задач в теории графов. Практические применения решений задач представлены в GPS-навигаторах, в проектировании сетей, городской инфраструктуры и д. р.

В ЭВМ существует два основных способа представления графов:

1. Матрица смежности вершин: при помощи двумерного массива, где каждый узел графа представлен строкой и столбцом в массиве. Если узлы i и j связаны, то значение в ячейке [i][j] и [j][i] будет равно 1 (или весу ребра), а если узлы не связаны, то значение будет равно 0.

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

При решении задачи поиска наикратчайшего пути будет использоваться модифицированный алгоритм Беллмана-Форда.

Задача: дан взвешенный, ориентированный граф G = (V, E) включающий ребра с отрицательными весами. Необходимо найти кратчайшие путь между двумя вершинами, заданными пользователем. При наличии отрицательного цикла вывести соответствующее сообщение.

Рис. 2. Исходный граф.

Таб. 1. Матрица смежности вершин для графа G.