📄Работа №115864
Тема: Сравнительный анализ алгоритмов поиска максимального потока
Тип работы
Бакалаврская работа
Предмет
информатика
Объем:
43 листов
Год:
2021
Просмотров:
88
4275
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение
Исследование предметной области 6
1.1 Граф 6
1.2 Сеть и поток 8
1.3 Остаточный граф 9
1.4 Увеличивающий путь 11
1.5 Разрыв сети 12
1.6 Задача о максимальном потоке 13
1.7 Теорема Форда-Фалкерсона 15
2 Программная реализация алгоритмов 19
2.1 Алгоритм Форда-Фалкерсона 19
2.2 Алгоритм Эдмондса-Карпа 25
2.3 Алгоритм Диница 28
3 Тестирование программы и анализ результатов 31
3.1 Описание программных средств 31
3.2 Сравнительный анализ результатов 32
Заключение 38
Список используемой литературы 39
Приложение А Алгоритм Форда-Фалкерсона 41
Приложение Б Алгоритм Эдмондса-Карпа 42
Приложение В Алгоритм Диница
Исследование предметной области 6
1.1 Граф 6
1.2 Сеть и поток 8
1.3 Остаточный граф 9
1.4 Увеличивающий путь 11
1.5 Разрыв сети 12
1.6 Задача о максимальном потоке 13
1.7 Теорема Форда-Фалкерсона 15
2 Программная реализация алгоритмов 19
2.1 Алгоритм Форда-Фалкерсона 19
2.2 Алгоритм Эдмондса-Карпа 25
2.3 Алгоритм Диница 28
3 Тестирование программы и анализ результатов 31
3.1 Описание программных средств 31
3.2 Сравнительный анализ результатов 32
Заключение 38
Список используемой литературы 39
Приложение А Алгоритм Форда-Фалкерсона 41
Приложение Б Алгоритм Эдмондса-Карпа 42
Приложение В Алгоритм Диница
📖 Введение
В повседневной жизни нас окружает множество различных типов сетей, включая электрические, телефонные, кабельные, автомобильные, железнодорожные, производственные и компьютерные. Сеть состоит из узлов и соединяющих их звеньев, по которым движется определенный объект. Процесс происходит в условиях определенных ограничений на каждом участке. Для достижения наиболее эффективного использования подобных сетей, необходимо решить задачу нахождения максимального потока, что позволит с максимально возможной нагрузкой эксплуатировать сеть и следовательно, получать максимально возможный результат.
Задача нахождения максимального потока в транспортной сети не теряет своей актуальности в современном мире. При проектировании сети в реальном пространстве, необходимо проведение анализа свойств будущего объекта.
В качестве объекта исследования выступает задача о поиске максимального потока. Предметом исследования являются алгоритмы для нахождения максимального потока.
Целью данной работы является разработка и программная реализация алгоритмов решения задачи о максимальном потоке на языке Python и дополнительной библиотеки pydot. А также проведение сравнительного анализа на основе полученных результатов.
Для достижения поставленной цели необходимо решить ряд задач:
1. Изучить область объекта исследования;
2. Исследовать основные алгоритмы для решения задачи о максимальном потоке;
3. Реализовать исследованные алгоритмы на языке Python;
4. Провести анализ результатов;
5. Сделать вывод о проведенной работе.
Задача нахождения максимального потока в транспортной сети не теряет своей актуальности в современном мире. При проектировании сети в реальном пространстве, необходимо проведение анализа свойств будущего объекта.
В качестве объекта исследования выступает задача о поиске максимального потока. Предметом исследования являются алгоритмы для нахождения максимального потока.
Целью данной работы является разработка и программная реализация алгоритмов решения задачи о максимальном потоке на языке Python и дополнительной библиотеки pydot. А также проведение сравнительного анализа на основе полученных результатов.
Для достижения поставленной цели необходимо решить ряд задач:
1. Изучить область объекта исследования;
2. Исследовать основные алгоритмы для решения задачи о максимальном потоке;
3. Реализовать исследованные алгоритмы на языке Python;
4. Провести анализ результатов;
5. Сделать вывод о проведенной работе.
✅ Заключение
В процессе выполнения задания были исследованы методы поиска максимального потока в транспортных сетях.
После изучения необходимых источников литературы, были реализованы алгоритмы для решения задачи о поиске максимального потока. Во время этого процесса были пополнены знания о возможностях языка программирования Python и его дополнительной библиотеке pydot.
В ходе работы был выполнен ряд поставленных в начале работы задач:
1. Изучена область объекта исследования;
2. Разобрана теорема о максимальном потоке и минимальном разрезе
3. Исследованы алгоритмы поиска максимального потока;
4. Выполнена реализация программы;
5. Проведен сравнительный анализ полученных результатов;
6. Сформирован вывод о проведенной работе.
Для проведения сравнительного анализа полученных результатов, был выполнен поиск максимального потока на основе различных входящих данных графа, представленных в виде матриц смежности.
Рассматриваемые матрицы отличались по количеству ребер и вершин. Это потребовалось для достижения необходимого результата и формирования понимания о недостатках одних и преимуществ других алгоритмов в различных ситуациях. Граф сети был представлен в виде матрицы смежности, в ячейках которой были указаны пропускные способности каждого из ребер.
В исследуемых алгоритмах, для обхода узлов сети были использованы алгоритм поиска в глубину и алгоритм поиска в ширину.
Все поставленные задачи были выполнены. Созданная программа позволяет определить максимальный поток в сети на основе входящих данных.
После изучения необходимых источников литературы, были реализованы алгоритмы для решения задачи о поиске максимального потока. Во время этого процесса были пополнены знания о возможностях языка программирования Python и его дополнительной библиотеке pydot.
В ходе работы был выполнен ряд поставленных в начале работы задач:
1. Изучена область объекта исследования;
2. Разобрана теорема о максимальном потоке и минимальном разрезе
3. Исследованы алгоритмы поиска максимального потока;
4. Выполнена реализация программы;
5. Проведен сравнительный анализ полученных результатов;
6. Сформирован вывод о проведенной работе.
Для проведения сравнительного анализа полученных результатов, был выполнен поиск максимального потока на основе различных входящих данных графа, представленных в виде матриц смежности.
Рассматриваемые матрицы отличались по количеству ребер и вершин. Это потребовалось для достижения необходимого результата и формирования понимания о недостатках одних и преимуществ других алгоритмов в различных ситуациях. Граф сети был представлен в виде матрицы смежности, в ячейках которой были указаны пропускные способности каждого из ребер.
В исследуемых алгоритмах, для обхода узлов сети были использованы алгоритм поиска в глубину и алгоритм поиска в ширину.
Все поставленные задачи были выполнены. Созданная программа позволяет определить максимальный поток в сети на основе входящих данных.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.